Apa jaminan yang ada pada kompleksitas run-time (Big-O) dari metode LINQ?

Saya baru-baru ini mulai menggunakan LINQ cukup banyak, dan saya belum benar-benar melihat adanya penyebutan kompleksitas run-time untuk salah satu metode LINQ. Jelas, ada banyak faktor yang berperan di sini, jadi mari kita batasi diskusi pada IEnumerablepenyedia LINQ-to-Objects biasa. Selanjutnya, mari kita asumsikan bahwa apapun yang Funcditeruskan sebagai selector / mutator / etc. adalah operasi O (1) yang murah.

Tampak jelas bahwa semua operasi tunggal-pass ( Select, Where, Count, Take/Skip, Any/All, dll) akan menjadi O (n), karena mereka hanya perlu berjalan urutan sekali; meskipun ini pun tunduk pada kemalasan.

Segalanya lebih suram untuk operasi yang lebih kompleks; set-seperti operator ( Union, Distinct, Except, dll) bekerja menggunakan GetHashCodesecara default (afaik), sehingga tampaknya masuk akal untuk mengasumsikan mereka menggunakan hash-table internal, membuat operasi ini O (n) juga, pada umumnya. Bagaimana dengan versi yang menggunakan IEqualityComparer?

OrderByakan membutuhkan semacam, jadi kemungkinan besar kita sedang melihat O (n log n). Bagaimana jika sudah diurutkan? Bagaimana jika saya mengatakan OrderBy().ThenBy()dan memberikan kunci yang sama untuk keduanya?

Saya bisa melihat GroupBy(dan Join) menggunakan penyortiran, atau hashing. Yang mana

Containsakan menjadi O (n) pada a List, tetapi O (1) pada a HashSet- apakah LINQ memeriksa container yang mendasarinya untuk melihat apakah itu dapat mempercepat?

Dan pertanyaan sebenarnya - sejauh ini, saya percaya bahwa operasinya berjalan dengan baik. Namun, bisakah saya mengandalkan itu? Kontainer STL, misalnya, dengan jelas menetapkan kompleksitas setiap operasi. Apakah ada jaminan serupa pada kinerja LINQ dalam spesifikasi pustaka .NET?

Lebih banyak pertanyaan (dalam menanggapi komentar):
Tidak benar-benar memikirkan tentang overhead, tetapi saya tidak berharap ada banyak hal untuk Linq-to-Objects sederhana. Posting CodingHorror berbicara tentang Linq-to-SQL, di mana saya dapat memahami parsing kueri dan membuat SQL akan menambah biaya - apakah ada biaya yang sama untuk penyedia Objek juga? Jika demikian, apakah berbeda jika Anda menggunakan sintaks deklaratif atau fungsional?

Ada sangat, sangat sedikit jaminan, tetapi ada beberapa pengoptimalan:

• Metode penyuluhan yang menggunakan diindeks akses, seperti ElementAt, Skip, Lastatau LastOrDefault, akan memeriksa untuk melihat apakah jenis alat yang mendasari IList<T>, sehingga Anda mendapatkan O (1) akses bukan O (N).

• The CountMetode pemeriksaan untuk ICollectionimplementasi, sehingga operasi ini adalah O (1) bukan O (N).

• Distinct,, GroupBy Joindan saya percaya juga metode kumpulan-kumpulan ( Union, Intersectdan Except) menggunakan hashing, jadi mereka harus mendekati O (N) dan bukan O (N²).

• Containsmemeriksa ICollectionimplementasi, jadi mungkin O (1) jika koleksi yang mendasarinya juga O (1), seperti a HashSet<T>, tetapi ini tergantung pada struktur data aktual dan tidak dijamin. Himpunan hash mengesampingkan Containsmetode, itulah mengapa mereka O (1).

• OrderBy metode menggunakan quicksort stabil, jadi itu kasus rata-rata O (N log N).

Saya pikir itu mencakup sebagian besar, jika tidak semua, metode ekstensi bawaan. Ada sangat sedikit jaminan kinerja; LINQ sendiri akan mencoba memanfaatkan struktur data yang efisien tetapi ini bukan cara bebas menulis kode yang berpotensi tidak efisien.

Saya sudah lama tahu bahwa .Count()pengembalian .Countjika pencacahan adalah IList.

Tapi aku selalu sedikit lelah tentang kompleksitas run-time dari operasi Set: .Intersect(), .Except(), .Union().

Berikut implementasi BCL (.NET 4.0 / 4.5) yang telah didekompilasi untuk .Intersect()(komentar saya):

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)                    // O(M)
    set.Add(source);                                    // O(1)

  foreach (TSource source in first)                     // O(N)
  {
    if (set.Remove(source))                             // O(1)
      yield return source;
  }
}

Kesimpulan:

• kinerjanya adalah O (M + N)
• penerapannya tidak memanfaatkan saat koleksi sudah disetel. (Ini mungkin tidak selalu langsung, karena yang digunakan IEqualityComparer<T>juga harus sesuai.)

Untuk kelengkapannya, berikut adalah implementasi untuk .Union()dan .Except().

Peringatan spoiler: mereka juga memiliki kompleksitas O (N + M) .

private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
  foreach (TSource source in second)
  {
    if (set.Add(source))
      yield return source;
  }
}


private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
  Set<TSource> set = new Set<TSource>(comparer);
  foreach (TSource source in second)
    set.Add(source);
  foreach (TSource source in first)
  {
    if (set.Add(source))
      yield return source;
  }
}

Yang dapat Anda lakukan hanyalah mengandalkan metode Enumerable yang ditulis dengan baik untuk kasus umum dan tidak akan menggunakan algoritme yang naif. Mungkin ada hal-hal pihak ketiga (blog, dll.) Yang mendeskripsikan algoritme yang sebenarnya digunakan, tetapi ini tidak resmi atau dijamin seperti halnya algoritme STL.

Sebagai ilustrasi, berikut adalah kode sumber yang direfleksikan (milik ILSpy) untuk Enumerable.Countdari System.Core:

// System.Linq.Enumerable
public static int Count<TSource>(this IEnumerable<TSource> source)
{
    checked
    {
        if (source == null)
        {
            throw Error.ArgumentNull("source");
        }
        ICollection<TSource> collection = source as ICollection<TSource>;
        if (collection != null)
        {
            return collection.Count;
        }
        ICollection collection2 = source as ICollection;
        if (collection2 != null)
        {
            return collection2.Count;
        }
        int num = 0;
        using (IEnumerator<TSource> enumerator = source.GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                num++;
            }
        }
        return num;
    }
}

Seperti yang Anda lihat, diperlukan beberapa upaya untuk menghindari solusi naif dengan hanya menyebutkan setiap elemen.

Saya baru saja merusak reflektor dan mereka memeriksa tipe yang mendasari saat Containsdipanggil.

public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value)
{
    ICollection<TSource> is2 = source as ICollection<TSource>;
    if (is2 != null)
    {
        return is2.Contains(value);
    }
    return source.Contains<TSource>(value, null);
}

Jawaban yang benar adalah "tergantung". itu tergantung pada jenis IEnumerable yang mendasarinya. saya tahu bahwa untuk beberapa koleksi (seperti koleksi yang mengimplementasikan ICollection atau IList) ada jalur kode khusus yang digunakan, namun implementasi sebenarnya tidak dijamin untuk melakukan sesuatu yang istimewa. misalnya saya tahu bahwa ElementAt () memiliki kasus khusus untuk koleksi yang dapat diindeks, mirip dengan Count (). Tapi secara umum Anda mungkin harus mengasumsikan kasus terburuk kinerja O (n).

Secara umum saya tidak berpikir Anda akan menemukan jenis jaminan kinerja yang Anda inginkan, meskipun jika Anda mengalami masalah kinerja tertentu dengan operator LINQ Anda selalu dapat menerapkannya kembali untuk koleksi khusus Anda. Juga ada banyak blog dan proyek perluasan yang memperluas Linq ke Objek untuk menambahkan jaminan kinerja semacam ini. lihat Indexed LINQ yang memperluas dan menambah set operator untuk manfaat kinerja lebih.