Apa penalti kinerja yang dapat saya harapkan jika saya menggunakan Daftar di atas Array untuk menyelesaikan Urutan Peningkatan Terpanjang?

Akankah sifat dinamis Daftar meningkatkan kinerja rata-rata karena kami tidak berurusan dengan ukuran yang sebenarnya tidak akan kami gunakan?

PS: Adakah kiat untuk meningkatkan kinerja sambil tetap mempertahankan keterbacaan?

   public static int Run(int[] nums)
    {
        var length = nums.Length;

        List<List<int>> candidates = new List<List<int>>();

        candidates.Add(new List<int> { nums[0] });

        for (int i = 1; i < length; i++)
        {
            var valueFromArray = nums[i];

            var potentialReplacements = candidates.Where(t => t[t.Count-1] > valueFromArray);

            foreach (var collection in potentialReplacements)
            {
                var collectionCount = collection.Count;

                if ((collection.Count > 1 && collection[collectionCount - 2] < valueFromArray) || (collectionCount == 1))
                {
                    collection.RemoveAt(collectionCount - 1);
                    collection.Add(valueFromArray);
                }
            }

            if (!candidates.Any(t => t[t.Count - 1] >= valueFromArray))
            {
                var newList = new List<int>();

                foreach(var value in candidates[candidates.Count - 1])
                {
                    newList.Add(value);
                }

                newList.Add(nums[i]);
                candidates.Add(newList);
            }
        }

        return candidates[candidates.Count - 1].Count;
    }
-2
devadviser 21 Oktober 2017, 23:19
Hal ini sepele untuk menulis algoritma dua arah; melakukannya, ukur kinerja keduanya, dan kemudian Anda akan memiliki bukti empiris mana yang lebih baik.
 – 
Eric Lippert
22 Oktober 2017, 01:13
Di sisi lain, mengapa Anda tertarik pada peningkatan kecil seperti itu ketika solusi Anda jauh dari efisien? Saya sarankan Anda untuk membaca stackoverflow.com/questions/2631726/… atau stackoverflow.com/questions/6129682/…
 – 
Raudel Ravelo
24 Oktober 2017, 07:13
Ini pada dasarnya adalah solusi O(N log N) tanpa penyortiran biner. Juga, pertanyaannya bukan untuk meningkatkan implementasi khusus ini. Ini lebih tentang mencoba mencari tahu apakah Daftar Generik lebih disukai daripada array untuk jenis masalah ini (menghilangkan masalah dengan batas array, membatasi konsumsi memori, keterbacaan bawaan)
 – 
devadviser
24 Oktober 2017, 13:39

1 menjawab

Jawaban Terbaik

Tergantung pada solusi, hasilnya mungkin berbeda. Array lebih cepat jika dibandingkan dengan daftar dengan ukuran yang sama. Seberapa cepat? Mari kita lihat solusi c# di bawah ini. Ini adalah solusi O(n^2) sederhana. Saya mengkodekan versi dengan array saja dan satu lagi dengan daftar saja. Saya menjalankannya 1000 kali dan merekam nilai untuk keduanya. Kemudian saya hanya mencetak peningkatan rata-rata dari versi array di atas versi daftar. Saya mendapatkan peningkatan lebih dari 50% pada komputer saya. Perhatikan bahwa solusi ini selalu menggunakan array dan daftar dengan ukuran yang sama. Daripada berarti saya tidak pernah membuat array yang lebih besar dari ukuran daftar yang akan tumbuh dalam versi daftar. Setelah Anda mulai membuat array dengan ukuran Max yang mungkin tidak terisi, perbandingan berhenti untuk bersikap adil. kode C# di bawah ini:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace hashExample
{
    class Program
    {
        static int RunArray(int[] array)
        {
            int[] dp = new int[array.Length];
            dp[0] = 1;
            for (int i = 1; i < array.Length; i++)
            {
                dp[i] = 1;
                for (int j = 0; j < i; j++)
                    if (array[i] > array[j] && dp[i] < dp[j] + 1)
                            dp[i] = dp[j] + 1;
            }
            return dp.Max();
        }

        static int RunList(List<int> array)
        {
            List<int> dp = new List<int>(array.Count);
            dp.Add(1);
            for (int i = 1; i < array.Count; i++)
            {
                dp.Add(1);
                for (int j = 0; j < i; j++)
                    if (array[i] > array[j] && dp[i] < dp[j] + 1)
                        dp[i] = dp[j] + 1;
            }
            return dp.Max();
        }

        static void Main(string[] args)
        {
            int arrayLen = 1000;
            Random r = new Random();
            List<double> values = new List<double>();
            Stopwatch clock = new Stopwatch();
            Console.WriteLine("Running...");
            for (int i = 0; i < 100; i++)
            {
                List<int> list = new List<int>();
                int[] array = new int[arrayLen];
                for (int j = 0; j < arrayLen;j++)
                {
                    int e = r.Next();
                    array[j] = e;
                    list.Add(e);
                }

                clock.Restart();
                RunArray(array);
                clock.Stop();
                double timeArray = clock.ElapsedMilliseconds;
                clock.Restart();
                RunList(list);
                clock.Stop();
                double timeList = clock.ElapsedMilliseconds;
                //Console.WriteLine(Math.Round(timeArray/timeList*100,2) + "%");
                values.Add(timeArray / timeList);
            }
            Console.WriteLine("Arrays are " + Math.Round(values.Average()*100,1) + "% faster");
            Console.WriteLine("Done");
        }



    }
}
1
Raudel Ravelo 22 Oktober 2017, 00:32
Terimakasih atas tanggapan Anda. Peningkatan kinerja semacam itu diimbangi oleh keterbacaan (dan kemudahan penggunaan) Daftar. Namun, pertanyaan saya tentang 'menggunakan ukuran array yang tidak akan pernah Anda gunakan' sebenarnya tentang berbagai ukuran dan jumlah array 'kandidat' yang digunakan dalam implementasi tertentu.
 – 
devadviser
23 Oktober 2017, 16:17
Untuk implementasi khusus Anda, saya akan mengatakan bahwa bahkan ketika kandidat array akan berukuran num.Length, Anda dapat membuatnya di awal dan kemudian melacak ukuran sebenarnya dari masing-masing untuk tidak membuang waktu pergi ke tempat yang hanya ada nol. Tetapi seperti yang dikomentari @EricLippert, ubah dan coba.
 – 
Raudel Ravelo
24 Oktober 2017, 07:09
Maaf, tapi Anda melenceng. Itulah tepatnya yang saya maksudkan, kami mengalokasikan memori yang tidak akan pernah benar-benar kami gunakan karena kami perlu membuat array yang cukup besar untuk menyelesaikan jalur kasus terburuk.
 – 
devadviser
24 Oktober 2017, 13:41