Saya punya kelas, seperti ini:

public class MyClass
{
    public int Value { get; set; }
    public bool IsValid { get; set; }
}

_{Sebenarnya itu jauh lebih besar, tetapi ini menciptakan kembali masalah (keanehan).}

Saya ingin mendapatkan jumlah dari Value, di mana instance itu valid. Sejauh ini, saya telah menemukan dua solusi untuk ini.

Yang pertama adalah ini:

int result = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();

Namun, yang kedua adalah ini:

int result = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();

Saya ingin mendapatkan metode yang paling efisien. Saya, pada awalnya, berpikir bahwa yang kedua akan lebih efisien. Kemudian bagian teoretis saya mulai berjalan "Ya, satu adalah O (n + m + m), yang lain adalah O (n + n). Yang pertama harus bekerja lebih baik dengan lebih banyak cacat, sedangkan yang kedua harus berkinerja lebih baik dengan kurang ". Saya pikir mereka akan tampil setara. EDIT: Dan kemudian @Martin menunjukkan bahwa Di mana dan Pilih digabungkan, jadi itu seharusnya benar-benar O (m + n). Namun, jika Anda melihat di bawah, sepertinya ini tidak terkait.

Jadi saya mengujinya.

_{(Lebih dari 100 baris, jadi saya pikir lebih baik mempostingnya sebagai Intisari.)}
Hasilnya ... menarik.

_{Dengan toleransi dasi 0%:}

Timbangan ini mendukung Selectdan Where, sekitar ~ 30 poin.

How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where + Select: 65
Select: 36


_{Dengan toleransi dasi 2%:}

Itu sama, kecuali bahwa untuk beberapa mereka berada dalam 2%. Saya akan mengatakan itu margin kesalahan minimum. Selectdan Wheresekarang hanya memiliki ~ 20 poin.

How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 6
Where + Select: 58
Select: 37


_{Dengan toleransi dasi 5%:}

Inilah yang saya katakan sebagai margin of error maksimum saya. Itu membuatnya sedikit lebih baik untuk Select, tetapi tidak banyak.

How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 17
Where + Select: 53
Select: 31


_{Dengan toleransi dasi 10%:}

Ini jalan keluar dari batas kesalahan saya, tetapi saya masih tertarik dengan hasilnya. Karena itu memberi Selectdan Wheredua puluh poin memimpin itu untuk sementara waktu sekarang.

How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 36
Where + Select: 44
Select: 21


_{Dengan toleransi dasi 25%:}

Ini cara, jalan keluar dari batas kesalahan saya, tetapi saya masih tertarik dengan hasilnya, karena Selectdan Where masih (hampir) mempertahankan keunggulan 20 poin mereka. Sepertinya itu mengungguli dalam beberapa yang berbeda, dan itulah yang memberinya keunggulan.

How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where + Select: 16
Select: 0


Sekarang, aku menebak bahwa memimpin 20 poin berasal dari tengah-tengah, di mana mereka berdua terikat untuk mendapatkan sekitar kinerja yang sama. Saya bisa mencoba dan mencatatnya, tetapi itu akan menjadi seluruh informasi untuk diterima. Grafik akan lebih baik, saya kira.

Jadi itulah yang saya lakukan.

Ini menunjukkan bahwa Selectgaris tetap stabil (diharapkan) dan Select + Wheregaris naik (diharapkan). Namun, apa yang membingungkan saya adalah mengapa itu tidak sesuai dengan Selectpada 50 atau lebih awal: sebenarnya saya mengharapkan lebih awal dari 50, karena pencacah ekstra harus dibuat untuk Selectdan Where. Maksud saya, ini menunjukkan 20 poin memimpin, tetapi itu tidak menjelaskan mengapa. Ini, saya kira, adalah poin utama dari pertanyaan saya.

Kenapa berperilaku seperti ini? Haruskah saya mempercayainya? Jika tidak, haruskah saya menggunakan yang lain atau yang ini?

Seperti @KingKong disebutkan dalam komentar, Anda juga dapat menggunakan Sumkelebihan yang membutuhkan lambda. Jadi dua opsi saya sekarang diubah menjadi ini:

Pertama:

int result = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);

Kedua:

int result = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);

Saya akan membuatnya sedikit lebih pendek, tetapi:

How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where: 60
Sum: 41
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 8
Where: 55
Sum: 38
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 21
Where: 49
Sum: 31
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 39
Where: 41
Sum: 21
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where: 16
Sum: 0


Keunggulan dua puluh poin masih ada, artinya itu tidak ada hubungannya dengan Wheredan Selectkombinasi yang ditunjukkan oleh @Marcin dalam komentar.

_{Terima kasih telah membaca dinding teks saya! Juga, jika Anda tertarik, ini versi modifikasi yang mencatat CSV yang digunakan Excel.}

Selectiterates sekali atas seluruh set dan, untuk setiap item, melakukan cabang bersyarat (memeriksa validitas) dan +operasi.

Where+Selectmenciptakan iterator yang melompati elemen yang tidak valid (bukankah yieldmereka), melakukan +hanya pada item yang valid.

Jadi, biaya untuk Selectadalah:

t(s) = n * ( cost(check valid) + cost(+) )

Dan untuk Where+Select:

t(ws) = n * ( cost(check valid) + p(valid) * (cost(yield) + cost(+)) )

Dimana:

• p(valid) adalah probabilitas suatu item dalam daftar valid.
• cost(check valid) adalah biaya cabang yang memeriksa validitas
• cost(yield)adalah biaya membangun keadaan baru whereiterator, yang lebih kompleks daripada iterator sederhana yang Selectdigunakan versi.

Seperti yang Anda lihat, untuk yang diberikan n, Selectversi adalah konstanta, sedangkan Where+Selectversi adalah persamaan linear dengan p(valid)sebagai variabel. Nilai aktual dari biaya menentukan titik persimpangan dari dua garis, dan karena cost(yield)dapat berbeda dari cost(+), mereka tidak harus berpotongan pada p(valid)= 0,5.

Berikut adalah penjelasan mendalam tentang apa yang menyebabkan perbedaan waktu.

The Sum()fungsi untuk IEnumerable<int>terlihat seperti ini:

public static int Sum(this IEnumerable<int> source)
{
    int sum = 0;
    foreach(int item in source)
    {
        sum += item;
    }
    return sum;
}

Dalam C #, foreachitu hanya gula sintaksis untuk versi iterator .Net, (jangan dikelirukan dengan ) . Jadi kode di atas sebenarnya diterjemahkan ke ini:IEnumerator<T> IEnumerable<T>

public static int Sum(this IEnumerable<int> source)
{
    int sum = 0;

    IEnumerator<int> iterator = source.GetEnumerator();
    while(iterator.MoveNext())
    {
        int item = iterator.Current;
        sum += item;
    }
    return sum;
}

Ingat, dua baris kode yang Anda bandingkan adalah sebagai berikut

int result1 = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);
int result2 = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);

Sekarang inilah kickernya:

LINQ menggunakan eksekusi yang ditangguhkan . Dengan demikian, sementara itu mungkin tampak bahwa result1iterates atas koleksi dua kali, itu sebenarnya hanya iterates atas sekali. The Where()kondisi sebenarnya diterapkan selama Sum(), dalam panggilan untuk MoveNext() (Hal ini dimungkinkan berkat keajaiban yield return) .

Ini berarti, untuk result1, kode di dalam whileloop,

{
    int item = iterator.Current;
    sum += item;
}

hanya dieksekusi satu kali untuk setiap item dengan mc.IsValid == true. Sebagai perbandingan, result2akan menjalankan kode itu untuk setiap item dalam koleksi. Itu sebabnya result1umumnya lebih cepat.

(Meskipun, perhatikan bahwa memanggil Where()kondisi di dalam MoveNext()masih memiliki beberapa overhead kecil, jadi jika sebagian besar / semua item memiliki mc.IsValid == true, result2sebenarnya akan lebih cepat!)

Semoga sekarang sudah jelas kenapa result2biasanya lebih lambat. Sekarang saya ingin menjelaskan mengapa saya menyatakan dalam komentar bahwa perbandingan kinerja LINQ ini tidak masalah .

Membuat ekspresi LINQ itu murah. Memanggil fungsi delegasi itu murah. Mengalokasikan dan mengulangi iterator itu murah. Tetapi bahkan lebih murah untuk tidak melakukan hal-hal ini. Jadi, jika Anda menemukan bahwa pernyataan LINQ adalah hambatan dalam program Anda, menurut pengalaman saya menulis ulang tanpa LINQ akan selalu membuatnya lebih cepat daripada berbagai metode LINQ lainnya.

Jadi, alur kerja LINQ Anda akan terlihat seperti ini:

1. Gunakan LINQ di mana-mana.
2. Profil.
3. Jika profiler mengatakan LINQ adalah penyebab kemacetan, tulis ulang potongan kode itu tanpa LINQ.

Untungnya, kemacetan LINQ jarang terjadi. Heck, bottleneck jarang terjadi. Saya telah menulis ratusan pernyataan LINQ dalam beberapa tahun terakhir, dan akhirnya mengganti <1%. Dan kebanyakan dari mereka adalah karena LINQ2EF optimasi SQL 's miskin, bukannya kesalahan LINQ ini.

Jadi, seperti biasa, tulis kode yang jelas dan masuk akal terlebih dahulu, dan tunggu sampai setelah Anda diprofilkan untuk mengkhawatirkan optimasi mikro.

Hal yang lucu. Apakah Anda tahu bagaimana Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)didefinisikan? Itu menggunakan Selectmetode!

public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector)
{
    return source.Select(selector).Sum();
}

Jadi sebenarnya, semuanya harus bekerja hampir sama. Saya melakukan riset cepat sendiri, dan berikut hasilnya:

Where -- mod: 1 result: 0, time: 371 ms
WhereSelect -- mod: 1  result: 0, time: 356 ms
Select -- mod: 1  result 0, time: 366 ms
Sum -- mod: 1  result: 0, time: 363 ms
-------------
Where -- mod: 2 result: 4999999, time: 469 ms
WhereSelect -- mod: 2  result: 4999999, time: 429 ms
Select -- mod: 2  result 4999999, time: 362 ms
Sum -- mod: 2  result: 4999999, time: 358 ms
-------------
Where -- mod: 3 result: 9999999, time: 441 ms
WhereSelect -- mod: 3  result: 9999999, time: 452 ms
Select -- mod: 3  result 9999999, time: 371 ms
Sum -- mod: 3  result: 9999999, time: 380 ms
-------------
Where -- mod: 4 result: 7500000, time: 571 ms
WhereSelect -- mod: 4  result: 7500000, time: 501 ms
Select -- mod: 4  result 7500000, time: 406 ms
Sum -- mod: 4  result: 7500000, time: 397 ms
-------------
Where -- mod: 5 result: 7999999, time: 490 ms
WhereSelect -- mod: 5  result: 7999999, time: 477 ms
Select -- mod: 5  result 7999999, time: 397 ms
Sum -- mod: 5  result: 7999999, time: 394 ms
-------------
Where -- mod: 6 result: 9999999, time: 488 ms
WhereSelect -- mod: 6  result: 9999999, time: 480 ms
Select -- mod: 6  result 9999999, time: 391 ms
Sum -- mod: 6  result: 9999999, time: 387 ms
-------------
Where -- mod: 7 result: 8571428, time: 489 ms
WhereSelect -- mod: 7  result: 8571428, time: 486 ms
Select -- mod: 7  result 8571428, time: 384 ms
Sum -- mod: 7  result: 8571428, time: 381 ms
-------------
Where -- mod: 8 result: 8749999, time: 494 ms
WhereSelect -- mod: 8  result: 8749999, time: 488 ms
Select -- mod: 8  result 8749999, time: 386 ms
Sum -- mod: 8  result: 8749999, time: 373 ms
-------------
Where -- mod: 9 result: 9999999, time: 497 ms
WhereSelect -- mod: 9  result: 9999999, time: 494 ms
Select -- mod: 9  result 9999999, time: 386 ms
Sum -- mod: 9  result: 9999999, time: 371 ms

Untuk implementasi berikut:

result = source.Where(x => x.IsValid).Sum(x => x.Value);
result = source.Select(x => x.IsValid ? x.Value : 0).Sum();
result = source.Sum(x => x.IsValid ? x.Value : 0);
result = source.Where(x => x.IsValid).Select(x => x.Value).Sum();

modberarti: setiap 1 dari moditem tidak valid: untuk mod == 1setiap item tidak valid, untuk mod == 2item aneh tidak valid, dll. Koleksi berisi 10000000item.

Dan hasil untuk koleksi dengan 100000000item:

Seperti yang Anda lihat, Selectdan Sumhasilnya cukup konsisten di semua modnilai. Namun wheredan where+select tidak.

Dugaan saya adalah bahwa versi dengan Di mana menyaring 0s dan mereka bukan subjek untuk Sum (yaitu Anda tidak menjalankan penambahan). Ini tentu saja suatu dugaan karena saya tidak dapat menjelaskan bagaimana mengeksekusi ekspresi lambda tambahan dan memanggil beberapa metode mengungguli penambahan sederhana dari 0.

Seorang teman saya menyarankan bahwa fakta bahwa 0 dalam penjumlahan dapat menyebabkan penalti kinerja yang parah karena pemeriksaan melimpah. Akan menarik untuk melihat bagaimana ini akan tampil dalam konteks yang tidak dicentang.

Menjalankan sampel berikut, menjadi jelas bagi saya bahwa satu-satunya waktu Di mana + Pilih dapat mengungguli Pilih sebenarnya ketika itu membuang jumlah yang baik (kira-kira setengah dalam tes informal saya) dari item potensial dalam daftar. Dalam contoh kecil di bawah ini, saya mendapatkan kira-kira angka yang sama dari kedua sampel ketika Di mana melompat kira-kira 4mil item dari 10mil. Saya berlari dalam rilis, dan memesan kembali pelaksanaan di mana + pilih vs pilih dengan hasil yang sama.

static void Main(string[] args)
        {
            int total = 10000000;
            Random r = new Random();
            var list = Enumerable.Range(0, total).Select(i => r.Next(0, 5)).ToList();
            for (int i = 0; i < 4000000; i++)
                list[i] = 10;

            var sw = new Stopwatch();
            sw.Start();

            int sum = 0;

            sum = list.Where(i => i < 10).Select(i => i).Sum();            

            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);

            sw.Reset();
            sw.Start();
            sum = list.Select(i => i).Sum();            

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);
        }

Jika Anda membutuhkan kecepatan, hanya melakukan perulangan lurus mungkin merupakan taruhan terbaik Anda. Dan melakukan forcenderung lebih baik daripadaforeach (dengan asumsi koleksi Anda adalah akses acak tentu saja).

Berikut adalah timing yang saya dapatkan dengan 10% elemen tidak valid:

Where + Select + Sum:   257
Select + Sum:           253
foreach:                111
for:                    61

Dan dengan 90% elemen tidak valid:

Where + Select + Sum:   177
Select + Sum:           247
foreach:                105
for:                    58

Dan ini kode tolok ukur saya ...

public class MyClass {
    public int Value { get; set; }
    public bool IsValid { get; set; }
}

class Program {

    static void Main(string[] args) {

        const int count = 10000000;
        const int percentageInvalid = 90;

        var rnd = new Random();
        var myCollection = new List<MyClass>(count);
        for (int i = 0; i < count; ++i) {
            myCollection.Add(
                new MyClass {
                    Value = rnd.Next(0, 50),
                    IsValid = rnd.Next(0, 100) > percentageInvalid
                }
            );
        }

        var sw = new Stopwatch();
        sw.Restart();
        int result1 = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();
        sw.Stop();
        Console.WriteLine("Where + Select + Sum:\t{0}", sw.ElapsedMilliseconds);

        sw.Restart();
        int result2 = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();
        sw.Stop();
        Console.WriteLine("Select + Sum:\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result2);

        sw.Restart();
        int result3 = 0;
        foreach (var mc in myCollection) {
            if (mc.IsValid)
                result3 += mc.Value;
        }
        sw.Stop();
        Console.WriteLine("foreach:\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result3);

        sw.Restart();
        int result4 = 0;
        for (int i = 0; i < myCollection.Count; ++i) {
            var mc = myCollection[i];
            if (mc.IsValid)
                result4 += mc.Value;
        }
        sw.Stop();
        Console.WriteLine("for:\t\t\t{0}", sw.ElapsedMilliseconds);
        Debug.Assert(result1 == result4);

    }

}

BTW, saya setuju dengan dugaan Stilgar : kecepatan relatif dari dua kasus Anda bervariasi tergantung pada persentase item yang tidak valid, hanya karena jumlah pekerjaan yang Sumperlu dilakukan bervariasi dalam kasus "Di mana".

Daripada mencoba menjelaskan melalui deskripsi, saya akan mengambil pendekatan yang lebih matematis.

Dengan kode di bawah ini yang seharusnya mendekati apa yang dilakukan LINQ secara internal, biaya relatifnya adalah sebagai berikut:
Pilih saja:Nd + Na
Di mana + Pilih:Nd + Md + Ma

Untuk mengetahui titik di mana mereka akan menyeberang, kita perlu melakukan aljabar kecil:
Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)

Ini artinya bahwa agar titik belok mencapai 50%, biaya pemanggilan seorang delegasi harus kira-kira sama dengan biaya penambahan. Karena kita tahu bahwa titik belok yang sebenarnya adalah sekitar 60%, kita dapat bekerja mundur dan menentukan bahwa biaya permohonan delegasi untuk @ It'sNotALie sebenarnya sekitar 2/3 biaya tambahan yang mengejutkan, tapi itulah yang angka-angkanya mengatakan.

static void Main(string[] args)
{
    var set = Enumerable.Range(1, 10000000)
                        .Select(i => new MyClass {Value = i, IsValid = i%2 == 0})
                        .ToList();

    Func<MyClass, int> select = i => i.IsValid ? i.Value : 0;
    Console.WriteLine(
        Sum(                        // Cost: N additions
            Select(set, select)));  // Cost: N delegate
    // Total cost: N * (delegate + addition) = Nd + Na

    Func<MyClass, bool> where = i => i.IsValid;
    Func<MyClass, int> wSelect = i => i.Value;
    Console.WriteLine(
        Sum(                        // Cost: M additions
            Select(                 // Cost: M delegate
                Where(set, where),  // Cost: N delegate
                wSelect)));
    // Total cost: N * delegate + M * (delegate + addition) = Nd + Md + Ma
}

// Cost: N delegate calls
static IEnumerable<T> Where<T>(IEnumerable<T> set, Func<T, bool> predicate)
{
    foreach (var mc in set)
    {
        if (predicate(mc))
        {
            yield return mc;
        }
    }
}

// Cost: N delegate calls
static IEnumerable<int> Select<T>(IEnumerable<T> set, Func<T, int> selector)
{
    foreach (var mc in set)
    {
        yield return selector(mc);
    }
}

// Cost: N additions
static int Sum(IEnumerable<int> set)
{
    unchecked
    {
        var sum = 0;
        foreach (var i in set)
        {
            sum += i;
        }

        return sum;
    }
}

Saya pikir ini menarik bahwa hasil MarcinJuraszek berbeda dari It'sNotALie. Secara khusus, hasil MarcinJuraszek dimulai dengan keempat implementasi di tempat yang sama, sementara hasil It'sNotALie melintasi tengah. Saya akan menjelaskan bagaimana ini bekerja dari sumbernya.

Mari kita asumsikan ada nelemen total, dan melemen valid.

The SumFungsi ini cukup sederhana. Itu hanya loop melalui enumerator: http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)

Untuk kesederhanaan, anggap koleksi tersebut adalah daftar. Kedua Pilih dan WhereSelect akan membuat WhereSelectListIterator. Ini berarti iterator aktual yang dihasilkan adalah sama. Dalam kedua kasus, ada Sumyang loop di atas iterator, the WhereSelectListIterator. Bagian yang paling menarik dari iterator adalah metode MoveNext .

Karena iteratornya sama, loopnya sama. Satu-satunya perbedaan adalah di tubuh loop.

Tubuh lambda ini memiliki biaya yang sangat mirip. Klausa mana mengembalikan nilai bidang, dan predikat ternary juga mengembalikan nilai bidang. Klausa pilih mengembalikan nilai bidang, dan dua cabang operator ternary mengembalikan nilai bidang atau konstanta. Klausa pilih gabungan memiliki cabang sebagai operator ternary, tetapi WhereSelect menggunakan cabang diMoveNext .

Namun, semua operasi ini cukup murah. Operasi yang paling mahal sejauh ini adalah cabang, di mana prediksi yang salah akan merugikan kita.

Operasi mahal lainnya di sini adalah Invoke . Meminta fungsi membutuhkan waktu lebih lama daripada menambahkan nilai, seperti yang ditunjukkan oleh Branko Dimitrijevic.

Juga menimbang adalah akumulasi diperiksa di Sum . Jika prosesor tidak memiliki flag overflow aritmatika, maka ini bisa mahal untuk diperiksa juga.

Karenanya, biaya yang menarik adalah: adalah:

1. ( n+ m) * Aktifkan + m*checked+=
2. n* Ajukan + n*checked+=

Jadi, jika biaya Invoke jauh lebih tinggi daripada biaya akumulasi yang diperiksa, maka kasing 2 selalu lebih baik. Jika mereka tentang genap, maka kita akan melihat keseimbangan ketika sekitar setengah dari elemen valid.

Sepertinya pada sistem MarcinJuraszek, dicentang + = memiliki biaya yang dapat diabaikan, tetapi pada sistem It'sNotALie dan Branko Dimitrijevic, dicentang + = memiliki biaya yang signifikan. Sepertinya itu yang paling mahal pada sistem It'sNotALie karena titik impas jauh lebih tinggi. Sepertinya tidak ada yang memposting hasil dari sistem di mana akumulasi biayanya jauh lebih tinggi daripada Invoke.