List <T> .Contains () działa bardzo wolno?

Czy ktoś mógłby mi wyjaśnić, dlaczego List.Contains()funkcja generyczna działa tak wolno?

Mam List<long>około miliona cyfr i kod, który ciągle sprawdza, czy w tych liczbach jest określona liczba.

Próbowałem zrobić to samo używając Dictionary<long, byte>i Dictionary.ContainsKey()funkcji i było to około 10-20 razy szybciej niż w przypadku listy.

Oczywiście nie chcę używać Słownika do tego celu, ponieważ nie miał być używany w ten sposób.

Tak więc prawdziwe pytanie brzmi: czy jest jakaś alternatywa dla List<T>.Contains(), ale nie tak szalona jak Dictionary<K,V>.ContainsKey()?

Jeśli tylko sprawdzasz, czy istnieje, HashSet<T>w .NET 3.5 jest najlepszą opcją - wydajność podobna do słownika, ale bez pary klucz / wartość - tylko wartości:

    HashSet<int> data = new HashSet<int>();
    for (int i = 0; i < 1000000; i++)
    {
        data.Add(rand.Next(50000000));
    }
    bool contains = data.Contains(1234567); // etc

List.Contains jest operacją O (n).

Dictionary.ContainsKey to operacja O (1), ponieważ używa ona kodu skrótu obiektów jako klucza, co zapewnia szybsze wyszukiwanie.

Nie sądzę, że to dobry pomysł, aby mieć listę zawierającą milion wpisów. Nie sądzę, aby klasa List została zaprojektowana do tego celu. :)

Czy nie jest możliwe zapisanie tych jednostek Millona na przykład w RDBMS i wykonywanie zapytań w tej bazie danych?

Jeśli nie jest to możliwe, i tak użyłbym słownika.

Myślę, że mam odpowiedź! Tak, to prawda, że ​​Contains () na liście (tablicy) to O (n), ale jeśli tablica jest krótka i używasz typów wartości, nadal powinna być dość szybka. Ale używając CLR Profiler [darmowe pobranie z Microsoft], odkryłem, że Contains () pakuje wartości w celu ich porównania, co wymaga alokacji sterty, co jest BARDZO kosztowne (powolne). [Uwaga: to jest .Net 2.0; inne wersje .Net nie zostały przetestowane.]

Oto pełna historia i rozwiązanie. Mamy wyliczenie o nazwie "VI" i stworzyliśmy klasę o nazwie "ValueIdList", która jest typem abstrakcyjnym dla listy (tablicy) obiektów VI. Oryginalna implementacja była w starożytnym .Net 1.1 dnia i korzystała z hermetyzowanej listy ArrayList. Niedawno odkryliśmy na http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx, że lista ogólna (List <VI>) działa znacznie lepiej niż ArrayList w przypadku typów wartości (takich jak nasza enum VI), ponieważ wartości nie muszą być opakowane. To prawda i zadziałało ... prawie.

CLR Profiler ujawnił niespodziankę. Oto część wykresu alokacji:

• ValueIdList :: Zawiera bool (VI) 5,5 MB (34,81%)
• Generic.List :: Zawiera bool (<UNKNOWN>) 5,5 MB (34,81%)
• Generic.ObjectEqualityComparer <T> :: Equals bool (<UNKNOWN> <UNKNOWN>) 5,5 MB (34,88%)
• Wartości VI 7,7 MB (49,03%)

Jak widać, Contains () w zaskakujący sposób wywołuje Generic.ObjectEqualityComparer.Equals (), co najwyraźniej wymaga pakowania wartości VI, co wymaga kosztownego przydzielenia sterty. To dziwne, że Microsoft wyeliminowałby boks na liście, tylko po to, aby ponownie wymagać go do prostej operacji, takiej jak ta.

Naszym rozwiązaniem było ponowne napisanie implementacji Contains (), co w naszym przypadku było łatwe, ponieważ już hermetyzowaliśmy ogólny obiekt listy (_items). Oto prosty kod:

public bool Contains(VI id) 
{
  return IndexOf(id) >= 0;
}

public int IndexOf(VI id) 
{ 
  int i, count;

  count = _items.Count;
  for (i = 0; i < count; i++)
    if (_items[i] == id)
      return i;
  return -1;
}

public bool Remove(VI id) 
{
  int i;

  i = IndexOf(id);
  if (i < 0)
    return false;
  _items.RemoveAt(i);

  return true;
}

Porównanie wartości VI jest teraz wykonywane w naszej własnej wersji IndexOf (), która nie wymaga boksu i jest bardzo szybka. Nasz konkretny program przyspieszył o 20% po tym prostym przepisaniu. O (n) ... nie ma problemu! Po prostu unikaj marnowania pamięci!

Słownik nie jest taki zły, ponieważ klucze w słowniku są zaprojektowane tak, aby można je było szybko znaleźć. Aby znaleźć liczbę na liście, musi przejść przez całą listę.

Oczywiście słownik działa tylko wtedy, gdy liczby są niepowtarzalne i nie są uporządkowane.

Myślę, że HashSet<T>w .NET 3.5 jest też klasa, która pozwala tylko na unikalne elementy.

SortedList będzie szybciej szukać (ale wolniej, aby wstawić pozycje)

To nie jest dokładnie odpowiedź na twoje pytanie, ale mam klasę, która zwiększa wydajność Contains () w kolekcji. Podklasowałem kolejkę i dodałem słownik, który odwzorowuje hashcodes na listy obiektów. Dictionary.Contains()Funkcja O (1), podczas gdy List.Contains(), Queue.Contains()iStack.Contains() O (n).

Typ wartości słownika to kolejka przechowująca obiekty z tym samym hashcode. Obiekt wywołujący może dostarczyć niestandardowy obiekt klasy, który implementuje IEqualityComparer. Możesz użyć tego wzorca dla stosów lub list. Kod wymagałby tylko kilku zmian.

/// <summary>
/// This is a class that mimics a queue, except the Contains() operation is O(1) rather     than O(n) thanks to an internal dictionary.
/// The dictionary remembers the hashcodes of the items that have been enqueued and dequeued.
/// Hashcode collisions are stored in a queue to maintain FIFO order.
/// </summary>
/// <typeparam name="T"></typeparam>
private class HashQueue<T> : Queue<T>
{
    private readonly IEqualityComparer<T> _comp;
    public readonly Dictionary<int, Queue<T>> _hashes; //_hashes.Count doesn't always equal base.Count (due to collisions)

    public HashQueue(IEqualityComparer<T> comp = null) : base()
    {
        this._comp = comp;
        this._hashes = new Dictionary<int, Queue<T>>();
    }

    public HashQueue(int capacity, IEqualityComparer<T> comp = null) : base(capacity)
    {
        this._comp = comp;
        this._hashes = new Dictionary<int, Queue<T>>(capacity);
    }

    public HashQueue(IEnumerable<T> collection, IEqualityComparer<T> comp = null) :     base(collection)
    {
        this._comp = comp;

        this._hashes = new Dictionary<int, Queue<T>>(base.Count);
        foreach (var item in collection)
        {
            this.EnqueueDictionary(item);
        }
    }

    public new void Enqueue(T item)
    {
        base.Enqueue(item); //add to queue
        this.EnqueueDictionary(item);
    }

    private void EnqueueDictionary(T item)
    {
        int hash = this._comp == null ? item.GetHashCode() :     this._comp.GetHashCode(item);
        Queue<T> temp;
        if (!this._hashes.TryGetValue(hash, out temp))
        {
            temp = new Queue<T>();
            this._hashes.Add(hash, temp);
        }
        temp.Enqueue(item);
    }

    public new T Dequeue()
    {
        T result = base.Dequeue(); //remove from queue

        int hash = this._comp == null ? result.GetHashCode() : this._comp.GetHashCode(result);
        Queue<T> temp;
        if (this._hashes.TryGetValue(hash, out temp))
        {
            temp.Dequeue();
            if (temp.Count == 0)
                this._hashes.Remove(hash);
        }

        return result;
    }

    public new bool Contains(T item)
    { //This is O(1), whereas Queue.Contains is (n)
        int hash = this._comp == null ? item.GetHashCode() : this._comp.GetHashCode(item);
        return this._hashes.ContainsKey(hash);
    }

    public new void Clear()
    {
        foreach (var item in this._hashes.Values)
            item.Clear(); //clear collision lists

        this._hashes.Clear(); //clear dictionary

        base.Clear(); //clear queue
    }
}

Moje proste testy pokazują, że mój HashQueue.Contains()działa znacznie szybciej niż Queue.Contains(). Uruchomienie kodu testowego z liczbą ustawioną na 10 000 zajmuje 0,00045 sekund w przypadku wersji HashQueue i 0,37 sekundy w przypadku wersji kolejki. Przy liczbie 100 000 wersja HashQueue zajmuje 0,0031 sekundy, podczas gdy kolejka zajmuje 36,38 sekundy!

Oto mój kod testowy:

static void Main(string[] args)
{
    int count = 10000;

    { //HashQueue
        var q = new HashQueue<int>(count);

        for (int i = 0; i < count; i++) //load queue (not timed)
            q.Enqueue(i);

        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 0; i < count; i++)
        {
            bool contains = q.Contains(i);
        }
        sw.Stop();
        Console.WriteLine(string.Format("HashQueue, {0}", sw.Elapsed));
    }

    { //Queue
        var q = new Queue<int>(count);

        for (int i = 0; i < count; i++) //load queue (not timed)
            q.Enqueue(i);

        System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 0; i < count; i++)
        {
            bool contains = q.Contains(i);
        }
        sw.Stop();
        Console.WriteLine(string.Format("Queue,     {0}", sw.Elapsed));
    }

    Console.ReadLine();
}

Dlaczego słownik jest nieodpowiedni?

Aby sprawdzić, czy dana wartość znajduje się na liście, musisz przejść całą listę. W przypadku słownika (lub innego kontenera opartego na skrótach) znacznie szybciej można zawęzić liczbę obiektów, z którymi należy porównać. Klucz (w twoim przypadku liczba) jest zaszyfrowany, co daje słownikowi ułamkowy podzbiór obiektów do porównania.

Używam tego w Compact Framework, gdzie nie ma wsparcia dla HashSet, wybrałem Dictionary, w którym oba ciągi są wartością, której szukam.

Oznacza to, że otrzymuję funkcję list <> z wydajnością słownika. To trochę hacky, ale działa.