Pytanie Jaki jest najszybszy sposób wyszukiwania listy w wielu usługach?


Mam proces, który odziedziczyłem po konwersji na język C # z innego języka. Liczne kroki w pętli procesowej, przez co może być wiele rekordów (100K-200K) do wykonywania obliczeń. W ramach tych procesów zazwyczaj wykonuje wyszukiwanie na innej liście, aby pobrać niektóre wartości. Zazwyczaj poruszałbym takie rzeczy w deklaracji SQL (i mamy to miejsce, gdzie byliśmy w stanie), ale w tych przypadkach nie jest to naprawdę łatwy sposób na zrobienie tego. W niektórych miejscach próbowaliśmy przekonwertować kod do procedury przechowywanej i zdecydowaliśmy, że nie działa on tak dobrze, jak się spodziewaliśmy.

W rzeczywistości kod wykonuje to:

var match = cost.Where(r => r.ryp.StartsWith(record.form.TrimEnd()) && 
                       r.year == record.year && 
                       r.period == record.period).FirstOrDefault();

koszt to lokalny typ listy. Gdybym szukał tylko jednego pola, prawdopodobnie po prostu przeniosłbym to na słownik. Zapisy nie zawsze są unikalne.

Oczywiście, jest to NAPRAWDĘ powolne.

Przebiegłem przez bibliotekę open source I4O który potrafi budować indeksy, ale nie sprawdza się w różnych kwerendach (i tak naprawdę nie mam czasu, aby próbować debugować kod źródłowy). Nie działa również z .StartsWith lub .Contains (StartsWith jest o wiele ważniejszy, ponieważ wiele oryginalnych zapytań wykorzystuje fakt, że wyszukiwanie "A" spowoduje znalezienie dopasowania w "ABC").

Czy są jakieś inne projekty (open source lub komercyjne), które robią tego typu rzeczy?

EDYTOWAĆ:

Zrobiłem kilka wyszukiwania na podstawie opinii i znaleźć Kolekcje mocy który obsługuje słowniki, które mają klucze, które nie są unikalne.

Przetestowałem ToLookup (), który działał świetnie - nadal nie jest tak szybki jak oryginalny kod, ale jest co najmniej akceptowalny. Zmniejsza się z 45 sekund do 3-4 sekund. Przyjrzę się strukturze Trie dla innych wyszukiwań.

Dzięki.


9
2018-04-11 16:03


pochodzenie


Czy pętla procesowa wykonuje wiele wyszukiwań w tym samym zestawie rekordów, czy zestaw rekordów jest używany tylko kilka razy przed potrzebą nowego? - Telastyn
Wykonuje pętlę na tym samym zestawie rekordów. Więc to samo wyszukiwanie jest używane przez cały czas. Jeden etap procesu, który zajmuje 1-2 sekundy w starym kodzie, zajmuje 35 sekund w nowym kodzie. - Paul Mrozowski
Kolejną rzeczą, na którą warto spojrzeć, może być mapowanie problemu na różne wątki (poprzez Parallel.ForEach) w zależności od tego, czy nie jest krytyczne do iteracji w określonej kolejności, w połączeniu z indeksowaniem wyszukiwania. - Adam Houldsworth


Odpowiedzi:


Zapętlenie listy 100K-200K przedmiotów nie zajmuje zbyt wiele czasu. Znalezienie pasujących elementów na liście za pomocą zagnieżdżonych pętli (n ^ 2) zajmuje dużo czasu. Wnioskuję, że to jest to, co robisz (ponieważ masz przypisanie do lokalnej zmiennej dopasowania).

Jeśli chcesz szybko dopasować elementy do siebie, użyj .ToLookup.

var lookup = cost.ToLookup(r => new {r.year, r.period, form = r.ryp});

foreach(var group in lookup)
{
  // do something with items in group.
}

Twoje kryteria startwith są kłopotliwe w przypadku dopasowań opartych na kluczach. Jednym ze sposobów podejścia do tego problemu jest zignorowanie go podczas generowania kluczy.

var lookup = cost.ToLookup(r => new {r.year, r.period });
var key = new {record.year, record.period};
string lookForThis = record.form.TrimEnd();
var match = lookup[key].FirstOrDefault(r => r.ryp.StartsWith(lookForThis))

Najlepiej byłoby utworzyć wyszukiwanie raz i ponownie użyć go dla wielu zapytań. Nawet jeśli nie zrobiłeś tego, nawet jeśli tworzyłeś wyszukiwanie za każdym razem, to nadal będzie ono szybsze niż n ^ 2.


11
2018-04-11 16:30





Z pewnością możesz zrobić to lepiej. Zacznijmy od tego, że słowniki są nieprzydatne tylko wtedy, gdy chcemy zapytać o jedno pole; możesz bardzo łatwo mieć słownik, w którym klucz jest niezmienną wartością, która agreguje wiele pól. W przypadku tego konkretnego zapytania natychmiastową poprawą byłoby utworzenie typu klucza:

// should be immutable, GetHashCode and Equals should be implemented, etc etc
struct Key
{
    public int year;
    public int period;
}

a następnie spakuj swoje dane do pliku IDictionary<Key, ICollection<T>> lub podobny gdzie T jest typ Twojej bieżącej listy. W ten sposób można znacznie zmniejszyć liczbę wierszy rozpatrywanych w każdej iteracji.

Następnym krokiem byłoby użycie nie ICollection<T> jako typ wartości, ale a trie (to wygląda obiecująco), która jest strukturą danych dostosowaną do wyszukiwania ciągów, które mają określony prefiks.

Wreszcie, darmowa mikro-optymalizacja byłaby do podjęcia TrimEnd z pętli.

Teraz wszystko to odnosi się tylko do konkretnego podanego przykładu i może być konieczne ponowne sprawdzenie ze względu na inną specyfikę twojej sytuacji, ale w każdym razie powinieneś być w stanie wyciągnąć praktyczne korzyści z tego lub czegoś podobnego.


13
2018-04-11 16:15



Dla mnie zabójcą jest to, że te rekordy nie są unikalne - nawet na polach, których szuka. Oryginalny kod wykorzystuje początkową kolejność sortowania. - Paul Mrozowski
@PaulMrozowski: Które rekordy nie są wyjątkowe i dlaczego to ma znaczenie? Sugeruję słownik kolekcje. - Jon