Setara besar O untuk LINQ pilih

10

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 Baruntuk bekerja dengan."

Pertanyaan saya adalah ini : Apakah menggunakan pilihan LINQ mengurangi kompleksitas Big O?


sumber
3
Akan menarik untuk membandingkan IL yang diproduksi oleh kompiler untuk masing-masingnya.
Dan Pichelman
@DanPichelman - Berhenti nerd-sniping me! Ya, saya setuju bahwa akan menarik untuk mencari tahu. Apakah mereka setara atau tidak?
Mungkinkah menghemat waktu untuk mengulang bardan memfilter bar.PropZ.HasValueterlebih dahulu, jika Anda mengharapkan lebih dari jumlah kecil untuk menilai false? Tidak benar-benar menjawab pertanyaan Anda, saya hanya meninjau kode Anda.
1
Apakah kedua loop ini bahkan melakukan hal yang sama, khususnya dalam kasus di mana foo.PropA == bar.PropAberlaku untuk banyak entri barList? Sunting: pasti bukan yang kedua akan melempar NullReferenceExceptionketika pilih kembali null.
Philip Kendall
1
Saya kira itu .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.
Mike Nakis

Jawaban:

14

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 Wheremetode tidak memindai seluruh daftar segera tetapi penilai menciptakan iterator malas. The FirstOrDefaultMetode 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 breakdalam sampel pertama, kedua kode akan secara semantik setara, dan yang pertama akan lebih cepat karena lebih sedikit overhead.)

JacquesB
sumber
"solusi berbasis LINQ lebih cepat" Siapa yang tahu? LINQ memiliki overhead faktor konstan yang dapat dengan mudah melebihi 2x.
usr
@ usr: Anda benar, itu tergantung pada frekuensi kecocokan daripada ukuran daftar. Semakin tinggi frekuensi kecocokan, semakin besar keunggulan relatif dari solusi berbasis linq.
JacquesB
5

Tidak ada perbedaan dalam kompleksitas, keduanya adalah O (n²) karena Linq's Where is O (n).
Penggunaan FirstOrDefault setara dengan melakukan ini:

if(foo.PropA == bar.PropA && bar.PropZ.HasValue) 
{
    foo.PropC = foo.PropB * bar.PropZ;
    break;
}

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:

    public void myFunc(List<Foo> fooList, List<Bar> barList)
    {
        var rows = fooList.Join(
                        barList, 
                        f => f.PropA, 
                        b => b.PropA, 
                        (f, b) => new { Foo = f, Bar = b }
                   );

        foreach (var row in rows)
        {
            if (row.Bar.PropZ.HasValue)
                row.Foo.PropC = row.Foo.PropB * row.Bar.PropZ.Value;
        }
    }

Ini harus dijalankan di O (n log (n))

Cyril Gandon
sumber
Bisakah Anda menjelaskan mengapa itu akan menjalankan O (n log (n))? Mengikuti kode sumber, tampaknya membuat Lookup(Of TKey, TElement), mengulangi barList, mendapatkan Groupinguntuk setiap item, dan menambahkan item ke Grouping. Itu kemudian beralih fooList, mendapatkan Grouping, dan mengembalikan setiap elemen dalam pengelompokan. Dari mana asal `log (n)?
Zach Mierzejewski