IndexOf zbyt wolny na liście. Szybsze rozwiązanie?

Question

Mam ogólną listę, która musi być zachowanym porządkiem, aby można było pobrać indeks obiektu na liście. Problem polega na tym, że IndexOf jest zbyt wolny. Jeśli skomentuję IndexOf, kod działa szybko, jak tylko można. Czy istnieje lepszy sposób, taki jak zakonserwowane uporządkowana lista hash dla C#?

Dzięki, Nate

• Edit - Kolejność, w których elementy są dodawane/włożona jest porządek musi być. Nie jest konieczne ich sortowanie. Również ta lista może być często aktualizowana, dodawać, usuwać, wstawiać. Zasadniczo muszę przetłumaczyć obiekt na indeks, ponieważ są one reprezentowane w formancie siatki, więc mogę wykonywać operacje na sterowaniu siatką na podstawie indeksu.

Answer 1

Jeśli nie jest posortowane, ale zamówienie musi zostać zachowane, to możesz mieć oddzielny Dictionary<YourClass, int>, który będzie zawierać indeks dla każdego elementu.

Jeśli chcesz posortowaną listę, sprawdź poprzednie posty - możesz użyć SortedList<Tkey, TValue> w .Net 3.5, lub posortuj i użyj BinarySearch w starszych wersjach .Net.

[Edytuj] Podobne przykłady można znaleźć w Internecie, np.g .: OrderedList. Ten używa wewnętrznie ArrayList i HashTable, ale możesz łatwo uczynić go ogólnym.

[Edytuj2] Ooops ... przykład, który ci podałam, nie implementuję IndexOf tak jak opisałem na początku ... Ale dostajesz punkt - jedna lista powinna zostać zamówiona, druga do szybkiego wyszukiwania.

Answer 2

Cóż, nie ma powodu, dla którego powinieneś kiedykolwiek zamówić listę haszyszu ... to jest o to chodzi. Jednak lista haszująca powinna zrobić to całkiem łatwo.

Answer 3

Być może szukasz SortedList<TKey, TValue>?

Answer 4

układać pomocą List<T>.Sort, a następnie za pomocą metody List<T>.BinarySearch: „przenika cały klasyfikowane List(T) dla elementu [...] Sposób ten jest O (log n) operacji, gdzie n jest liczbą elementów na zasięg."

Answer 5

Jeśli korzystasz z klasy Lista, możesz użyć metody Sortuj do posortowania po początkowym wypełnieniu, a następnie użyj Metody BinarySearch, aby znaleźć odpowiedni element.

Answer 6

Proponuję użyć klasy SortedList<TKey, TValue> lub SortedDictionary<TKey, TValue>, jeśli potrzebujesz posortowanych produktów. Różnice są następujące.

• SortedList<TKey, TValue> zużywa mniej pamięci niż SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> ma szybsze operacje wstawiania i usuwania dla niesegregowanych danych: o (log n), w przeciwieństwie do O (n) w przypadku SortedList<TKey, TValue>.

• Jeśli na liście posortowane są wszystkie dane z sortowanych danych, jest szybsza niż niż SortedDictionary<TKey, TValue>.

Jeśli tylko chcesz zachować kolejność, można po prostu użyć Dictionary<TKey, TValue> i zapisać pozycję jako klucz i indeks jako wartość. Wadą jest to, że zmiana kolejności elementów, wstawiania lub usuwania są dość kosztowne.

Answer 7

Nie jestem pewien co do specyfiki w języku C#, ale możesz być w stanie go posortować (QuickSort?), A następnie użyć wyszukiwania binarnego (wydajność BinarySearch to O (log2 (N)) w porównaniu z sekwencją, np. jako indexOf, który jest O (n)). (WAŻNE: w przypadku wyszukiwania binarnego należy posortować strukturę)

Po wstawieniu elementów do struktury danych można spróbować zmodyfikowanego wyszukiwania binarnego, aby znaleźć także punkt wstawiania lub w przypadku dodawania dużej grupy , dodajesz je, a następnie sortujesz.

Jedynym problemem jest to, że wstawianie będzie wolniejsze.

Answer 8

Jeśli kolejność obiektów na liście ma być zachowana, jedyny sposób, w jaki mogę się zorientować, gdzie najszybciej uzyskasz dostęp, to przekazanie obiektowi, jaka jest jego pozycja w indeksie, gdy dodane itp. do listy. W ten sposób możesz zapytać obiekt, aby uzyskać jego indeks na liście. Minusem, a jego dużą wadą jest to, że wstawione obiekty mają teraz zależność od listy.

Answer 9

Zobacz dno this article here.

Wygląda na to, że zapisanie własnej metody pobierania indeksu jest znacznie szybsze niż przy użyciu metody IndexOf, ponieważ wywołuje metodę wirtualną w zależności od typu.

Coś takiego może poprawić Twoją wydajność. Napisałem mały test jednostkowy, aby zweryfikować, czy poprawia to wydajność wyszukiwania, i tak było około 15 razy na liście z 10 000 pozycji.

static int GetIndex(IList<Item> list, Item value) 
{ 
    for (int index = 0; index < list.Count; index++) 
    { 
     if (list[index] == value) 
     { 
      return index; 
     } 
    } 
    return -1; 
}