Saya mencoba untuk menentukan apakah ada perubahan dalam kesetaraan Big O dari loop bersarang ketika saya menggunakan pilih LINQ sebagai gantinya.
public void myFunc(List<Foo> fooList, List<Bar> barList)
{
foreach(Foo foo in fooList)
{
foreach(Bar bar in barList)
{
if(foo.PropA == bar.PropA && bar.PropZ.HasValue)
foo.PropC = foo.PropB * bar.PropZ;
}
}
}
Saya percaya contoh loop bersarang ini adalah O (n ^ 2) untuk kompleksitas.
Saya mengganti nested loop dengan pilihan LINQ seperti ini:
public void myFunc(List<Foo> fooList, List<Bar> barList)
{
foreach(Foo foo in fooList)
{
Bar bar = (from b in barList
where foo.PropA == b.PropA
select b).FirstOrDefault();
if(bar.PropZ.HasValue)
foo.PropC = foo.PropB * bar.PropZ;
}
}
Jika tidak ada yang lain, kode itu tampaknya sedikit lebih bersih untuk dibaca karena secara eksplisit menyatakan "kami sedang mencari ini Bar
untuk bekerja dengan."
Pertanyaan saya adalah ini : Apakah menggunakan pilihan LINQ mengurangi kompleksitas Big O?
bar
dan memfilterbar.PropZ.HasValue
terlebih dahulu, jika Anda mengharapkan lebih dari jumlah kecil untuk menilai false? Tidak benar-benar menjawab pertanyaan Anda, saya hanya meninjau kode Anda.foo.PropA == bar.PropA
berlaku untuk banyak entribarList
? Sunting: pasti bukan yang kedua akan melemparNullReferenceException
ketika pilih kembalinull
..FirstOrDefault()
akan membuat loop linq keluar lebih awal jika kecocokan ditemukan, sedangkan loop bersarang bodoh Anda tidak keluar lebih awal, jadi ya, saya akan berpikir bahwa linq akan memiliki big-oh yang lebih baik. Tapi saya tidak yakin, karena itu komentar dan bukan jawaban.Jawaban:
Big O sama, karena kedua kode akan (dalam kasus terburuk) harus melakukan perbandingan untuk setiap kombinasi item dari kedua daftar. Misalnya, jika tidak ada kecocokan antara daftar, tidak ada optimasi dalam implementasi Linq akan menghindari harus memeriksa semua item.
Tapi hei, kamu tidak benar-benar ingin tahu tentang O-besar, kan? Anda ingin tahu apakah yang kedua lebih cepat . Jawabannya adalah ya, solusi berbasis linq lebih cepat (asalkan cukup besar) karena hanya perlu melakukan pemeriksaan sampai kecocokan pertama dalam daftar ditemukan, sedangkan solusi bersarang-untuk selalu harus mengunjungi semua item . The
Where
metode tidak memindai seluruh daftar segera tetapi penilai menciptakan iterator malas. TheFirstOrDefault
Metode kemudian mengeksekusi iterator sampai pertandingan pertama ditemukan, yang berarti bahwa dalam kasus umum itu tidak harus melintasi seluruh daftar. Tentu saja ada beberapa overhead dalam solusi Linq, jadi jika n cukup rendah loop bersarang-untuk akan lebih cepat.Anda dapat memeriksa sendiri sumbernya: https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Enumerable.cs
(Tetapi jika Anda menambahkan
break
dalam sampel pertama, kedua kode akan secara semantik setara, dan yang pertama akan lebih cepat karena lebih sedikit overhead.)sumber
Tidak ada perbedaan dalam kompleksitas, keduanya adalah O (n²) karena Linq's Where is O (n).
Penggunaan FirstOrDefault setara dengan melakukan ini:
Ini merupakan peningkatan pada waktu perhitungan, tetapi tidak pada kompleksitasnya.
Anda dapat melakukan lebih baik dengan menggunakan Hashmap untuk salah satu dari dua daftar itu.
The Bergabunglah dengan Linq ini Operator akan membuat Hashmap untuk salah satu dari 2 daftar, sehingga Anda akan mendapatkan kinerja ketika mencari dua elemen yang cocok:
Ini harus dijalankan di O (n log (n))
sumber
Lookup(Of TKey, TElement)
, mengulangibarList
, mendapatkanGrouping
untuk setiap item, dan menambahkan item keGrouping
. Itu kemudian beralihfooList
, mendapatkanGrouping
, dan mengembalikan setiap elemen dalam pengelompokan. Dari mana asal `log (n)?