Najszybszy sposób wyszukiwania w kolekcji ciągów

Problem:

Mam plik tekstowy zawierający około 120 000 użytkowników (ciągi znaków), które chciałbym przechowywać w kolekcji, a następnie przeprowadzić wyszukiwanie w tej kolekcji.

Metoda wyszukiwania będzie występować za każdym razem, gdy użytkownik zmieni tekst a, TextBoxa wynikiem powinny być ciągi zawierające tekst w TextBox.

Nie muszę zmieniać listy, po prostu ściągam wyniki i umieszczam je w pliku ListBox.

Czego próbowałem do tej pory:

Próbowałem z dwoma różnymi kolekcjami / kontenerami, do których zrzucam wpisy ciągów z zewnętrznego pliku tekstowego (oczywiście raz):

1. List<string> allUsers;
2. HashSet<string> allUsers;

Za pomocą następującego zapytania LINQ :

allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();

Moje zdarzenie wyszukiwania (uruchamiane, gdy użytkownik zmieni wyszukiwany tekst):

private void textBox_search_TextChanged(object sender, EventArgs e)
{
    if (textBox_search.Text.Length > 2)
    {
        listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
    }
    else
    {
        listBox_choices.DataSource = null;
    }
}

Wyniki:

Oba dały mi słaby czas odpowiedzi (około 1-3 sekund między każdym naciśnięciem klawisza).

Pytanie:

Jak myślisz, gdzie jest moje wąskie gardło? Kolekcja, z której korzystałem? Metoda wyszukiwania? Obie?

Jak mogę uzyskać lepszą wydajność i płynniejszą funkcjonalność?

Możesz rozważyć wykonanie zadania filtrowania w wątku w tle, który wywołałby metodę wywołania zwrotnego po zakończeniu, lub po prostu wznowić filtrowanie, jeśli dane wejściowe zostaną zmienione.

Ogólna idea jest taka, aby móc go używać w następujący sposób:

public partial class YourForm : Form
{
    private readonly BackgroundWordFilter _filter;

    public YourForm()
    {
        InitializeComponent();

        // setup the background worker to return no more than 10 items,
        // and to set ListBox.DataSource when results are ready

        _filter = new BackgroundWordFilter
        (
            items: GetDictionaryItems(),
            maxItemsToMatch: 10,
            callback: results => 
              this.Invoke(new Action(() => listBox_choices.DataSource = results))
        );
    }

    private void textBox_search_TextChanged(object sender, EventArgs e)
    {
        // this will update the background worker's "current entry"
        _filter.SetCurrentEntry(textBox_search.Text);
    }
}

Szkic mógłby wyglądać mniej więcej tak:

public class BackgroundWordFilter : IDisposable
{
    private readonly List<string> _items;
    private readonly AutoResetEvent _signal = new AutoResetEvent(false);
    private readonly Thread _workerThread;
    private readonly int _maxItemsToMatch;
    private readonly Action<List<string>> _callback;

    private volatile bool _shouldRun = true;
    private volatile string _currentEntry = null;

    public BackgroundWordFilter(
        List<string> items,
        int maxItemsToMatch,
        Action<List<string>> callback)
    {
        _items = items;
        _callback = callback;
        _maxItemsToMatch = maxItemsToMatch;

        // start the long-lived backgroud thread
        _workerThread = new Thread(WorkerLoop)
        {
            IsBackground = true,
            Priority = ThreadPriority.BelowNormal
        };

        _workerThread.Start();
    }

    public void SetCurrentEntry(string currentEntry)
    {
        // set the current entry and signal the worker thread
        _currentEntry = currentEntry;
        _signal.Set();
    }

    void WorkerLoop()
    {
        while (_shouldRun)
        {
            // wait here until there is a new entry
            _signal.WaitOne();
            if (!_shouldRun)
                return;

            var entry = _currentEntry;
            var results = new List<string>();

            // if there is nothing to process,
            // return an empty list
            if (string.IsNullOrEmpty(entry))
            {
                _callback(results);
                continue;
            }

            // do the search in a for-loop to 
            // allow early termination when current entry
            // is changed on a different thread
            foreach (var i in _items)
            {
                // if matched, add to the list of results
                if (i.Contains(entry))
                    results.Add(i);

                // check if the current entry was updated in the meantime,
                // or we found enough items
                if (entry != _currentEntry || results.Count >= _maxItemsToMatch)
                    break;
            }

            if (entry == _currentEntry)
                _callback(results);
        }
    }

    public void Dispose()
    {
        // we are using AutoResetEvent and a background thread
        // and therefore must dispose it explicitly
        Dispose(true);
    }

    private void Dispose(bool disposing)
    {
        if (!disposing)
            return;

        // shutdown the thread
        if (_workerThread.IsAlive)
        {
            _shouldRun = false;
            _currentEntry = null;
            _signal.Set();
            _workerThread.Join();
        }

        // if targetting .NET 3.5 or older, we have to
        // use the explicit IDisposable implementation
        (_signal as IDisposable).Dispose();
    }
}

Powinieneś także pozbyć się _filterinstancji, gdy element nadrzędny Formzostanie usunięty. Oznacza to należy otworzyć i edytować Form„s Disposemetoda (wewnątrz YourForm.Designer.cspliku), aby wyglądać tak:

// inside "xxxxxx.Designer.cs"
protected override void Dispose(bool disposing)
{
    if (disposing)
    {
        if (_filter != null)
            _filter.Dispose();

        // this part is added by Visual Studio designer
        if (components != null)
            components.Dispose();
    }

    base.Dispose(disposing);
}

Na moim komputerze działa to dość szybko, więc przed przejściem do bardziej złożonego rozwiązania należy to przetestować i sprofilować.

Mając to na uwadze, „bardziej złożonym rozwiązaniem” byłoby prawdopodobnie przechowywanie ostatnich kilku wyników w słowniku, a następnie filtrowanie ich tylko wtedy, gdy okaże się, że nowy wpis różni się tylko pierwszym z ostatniego znaku.

Zrobiłem kilka testów i przeszukanie listy 120 000 pozycji i zapełnienie nowej listy wpisami zajmuje znikomą ilość czasu (około 1/50 sekundy, nawet jeśli wszystkie ciągi znaków są dopasowane).

Dlatego problem, który widzisz, musi wynikać z zapełnienia źródła danych, tutaj:

listBox_choices.DataSource = ...

Podejrzewam, że po prostu umieszczasz zbyt wiele pozycji w polu listy.

Być może powinieneś spróbować ograniczyć go do pierwszych 20 wpisów, na przykład:

listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text))
    .Take(20).ToList();

Zwróć również uwagę (jak zauważyli inni), że uzyskujesz dostęp do TextBox.Textwłaściwości dla każdego elementu w allUsers. Można to łatwo naprawić w następujący sposób:

string target = textBox_search.Text;
listBox_choices.DataSource = allUsers.Where(item => item.Contains(target))
    .Take(20).ToList();

Jednak mierzyłem czas potrzebny do uzyskania dostępu TextBox.Text500 000 razy i zajęło to tylko 0,7 sekundy, znacznie mniej niż 1 - 3 sekundy wymienione w OP. Jest to jednak opłacalna optymalizacja.

Użyj drzewa sufiksowego jako indeksu. Lub raczej po prostu zbuduj posortowany słownik, który będzie kojarzył każdy sufiks każdego nazwiska z listą odpowiadających im nazw.

Do wprowadzenia:

Abraham
Barbara
Abram

Struktura wyglądałaby następująco:

a -> Barbara
ab -> Abram
abraham -> Abraham
abram -> Abram
am -> Abraham, Abram
aham -> Abraham
ara -> Barbara
arbara -> Barbara
bara -> Barbara
barbara -> Barbara
bram -> Abram
braham -> Abraham
ham -> Abraham
m -> Abraham, Abram
raham -> Abraham
ram -> Abram
rbara -> Barbara

Algorytm wyszukiwania

Załóżmy, że użytkownik wprowadził „biustonosz”.

1. Oddziel słownik po wprowadzeniu danych przez użytkownika, aby znaleźć dane wejściowe użytkownika lub pozycję, do której może się udać. W ten sposób znajdujemy „barbara” - ostatni klawisz niżej niż „biustonosz”. Nazywa się to dolną granicą dla „stanika”. Wyszukiwanie zajmie czas logarytmiczny.
2. Iteruj od znalezionego klucza, aż dane wejściowe użytkownika przestaną być zgodne. To dałoby „bram” -> Abram i „braham” -> Abraham.
3. Połącz wynik iteracji (Abram, Abraham) i wyślij go.

Takie drzewa są przeznaczone do szybkiego wyszukiwania podciągów. Jego wydajność jest bliska O (log n). Wierzę, że to podejście będzie działać na tyle szybko, że będzie używane bezpośrednio przez wątek GUI. Ponadto będzie działać szybciej niż rozwiązanie wielowątkowe ze względu na brak narzutu synchronizacji.

Potrzebujesz wyszukiwarki tekstowej (np. Lucene.Net ) lub bazy danych (możesz rozważyć wbudowaną, taką jak SQL CE , SQLite itp.). Innymi słowy, potrzebujesz wyszukiwania indeksowanego. Wyszukiwanie na podstawie skrótu nie ma tutaj zastosowania, ponieważ wyszukujesz podłańcuch, podczas gdy wyszukiwanie na podstawie skrótu jest dobre do wyszukiwania dokładnej wartości.

W przeciwnym razie będzie to wyszukiwanie iteracyjne z zapętleniem kolekcji.

Przydatne może być również zdarzenie typu „odbicia”. Różni się to od ograniczania tym, że czeka pewien okres (na przykład 200 ms) na zakończenie zmian przed uruchomieniem zdarzenia.

Zobacz Debounce and Throttle: wizualne wyjaśnienie, aby uzyskać więcej informacji na temat odbicia. Doceniam, że ten artykuł skupia się na JavaScript, zamiast na C #, ale zasada ma zastosowanie.

Zaletą tego jest to, że nie wyszukuje, gdy nadal wpisujesz zapytanie. Powinien wtedy przestać próbować wykonywać dwa wyszukiwania jednocześnie.

Uruchom wyszukiwanie w innym wątku i pokaż animację ładowania lub pasek postępu, gdy ten wątek jest uruchomiony.

Możesz również spróbować zrównoleglenie zapytania LINQ .

var queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();

Oto test porównawczy, który pokazuje zalety wydajnościowe AsParallel ():

{
    IEnumerable<string> queryResults;
    bool useParallel = true;

    var strings = new List<string>();

    for (int i = 0; i < 2500000; i++)
        strings.Add(i.ToString());

    var stp = new Stopwatch();

    stp.Start();

    if (useParallel)
        queryResults = strings.AsParallel().Where(item => item.Contains("1")).ToList();
    else
        queryResults = strings.Where(item => item.Contains("1")).ToList();

    stp.Stop();

    Console.WriteLine("useParallel: {0}\r\nTime Elapsed: {1}", useParallel, stp.ElapsedMilliseconds);
}

Aktualizacja:

Zrobiłem pewne profilowanie.

(Aktualizacja 3)

• Zawartość listy: liczby generowane od 0 do 2.499.999
• Tekst filtru: 123 (20.477 wyników)
• Core i5-2500, Win7 64-bitowy, 8 GB pamięci RAM
• VS2012 + JetBrains dotTrace

Początkowy przebieg testowy dla 2.500.000 rekordów zajął mi 20.000ms.

Numer jeden to wezwanie do textBox_search.Textśrodka Contains. To powoduje, że każdy element wywołuje kosztowną get_WindowTextmetodę pola tekstowego. Wystarczy zmienić kod na:

    var text = textBox_search.Text;
    listBox_choices.DataSource = allUsers.Where(item => item.Contains(text)).ToList();

skrócono czas wykonywania do 1,858 ms .

Aktualizacja 2:

Pozostałe dwie istotne wąskie gardła to teraz wywołanie string.Contains(około 45% czasu wykonania) i aktualizacja elementów listy w set_Datasource(30%).

Moglibyśmy znaleźć kompromis między szybkością a zużyciem pamięci, tworząc drzewo sufiksów, jak zasugerował Basilevs, aby zmniejszyć liczbę niezbędnych porównań i przesunąć trochę czasu przetwarzania od wyszukiwania po naciśnięciu klawisza do wczytania nazw z pliku, który może być preferowane przez użytkownika.

Aby zwiększyć wydajność ładowania elementów do listy, sugerowałbym załadowanie tylko kilku pierwszych elementów i wskazanie użytkownikowi, że są dostępne kolejne elementy. W ten sposób dajesz użytkownikowi informację zwrotną, że są dostępne wyniki, aby mógł zawęzić wyszukiwanie, wprowadzając więcej liter lub załadować całą listę za pomocą jednego przycisku.

Korzystanie BeginUpdatei EndUpdatenie wprowadzono żadnych zmian w czasie wykonywania set_Datasource.

Jak zauważyli inni, samo zapytanie LINQ działa dość szybko. Uważam, że twoja wąska gardło to aktualizacja samej listy. Możesz spróbować czegoś takiego:

if (textBox_search.Text.Length > 2)
{
    listBox_choices.BeginUpdate(); 
    listBox_choices.DataSource = allUsers.Where(item => item.Contains(textBox_search.Text)).ToList();
    listBox_choices.EndUpdate(); 
}

Mam nadzieję, że to pomoże.

Zakładając, że dopasowujesz tylko przedrostki, struktura danych, której szukasz, nazywa się trie , znaną również jako „drzewo prefiksów”. IEnumerable.WhereSposób, że używasz teraz będzie musiał wykonać iterację wszystkich elementów słownika na każdym wejściu.

W tym wątku pokazano, jak utworzyć próbę w języku C #.

Kontrolka WinForms ListBox naprawdę jest tutaj twoim wrogiem. Ładowanie rekordów będzie powolne, a pasek ScrollBar będzie walczył o wyświetlenie wszystkich 120000 rekordów.

Spróbuj użyć przestarzałych danych DataGridView pochodzących z DataTable z jedną kolumną [UserName] do przechowywania danych:

private DataTable dt;

public Form1() {
  InitializeComponent();

  dt = new DataTable();
  dt.Columns.Add("UserName");
  for (int i = 0; i < 120000; ++i){
    DataRow dr = dt.NewRow();
    dr[0] = "user" + i.ToString();
    dt.Rows.Add(dr);
  }
  dgv.AutoSizeColumnsMode = DataGridViewAutoSizeColumnsMode.Fill;
  dgv.AllowUserToAddRows = false;
  dgv.AllowUserToDeleteRows = false;
  dgv.RowHeadersVisible = false;
  dgv.DataSource = dt;
}

Następnie użyj DataView w zdarzeniu TextChanged swojego TextBox, aby przefiltrować dane:

private void textBox1_TextChanged(object sender, EventArgs e) {
  DataView dv = new DataView(dt);
  dv.RowFilter = string.Format("[UserName] LIKE '%{0}%'", textBox1.Text);
  dgv.DataSource = dv;
}

Po pierwsze chciałbym zmienić sposób ListControlwidzi źródło danych, jesteś konwersji wynik IEnumerable<string>do List<string>. Może to być nieefektywne (i niepotrzebne), zwłaszcza gdy wpisałeś tylko kilka znaków. Nie rób obszernych kopii swoich danych .

• Zawinąłbym .Where()wynik do kolekcji, która implementuje tylko to, co jest wymagane od IList(wyszukiwanie). Pozwoli to zaoszczędzić na tworzeniu nowej dużej listy dla każdego wpisanego znaku.
• Alternatywnie unikałbym LINQ i napisałbym coś bardziej szczegółowego (i zoptymalizowanego). Przechowuj listę w pamięci i buduj tablicę dopasowanych indeksów, wykorzystuj ponownie tablicę, aby nie trzeba było jej ponownie przydzielać przy każdym wyszukiwaniu.

Drugim krokiem jest nie przeszukiwanie dużej listy, gdy wystarczy mała. Gdy użytkownik zaczął wpisywać „ab” i dodawał „c”, nie ma potrzeby przeszukiwania dużej listy, wystarczy przeszukać filtrowaną listę (i to szybciej). Zawęź wyszukiwanie każdym razem, gdy jest to możliwe, nie wykonuj za każdym razem pełnego wyszukiwania.

Trzeci krok może być trudniejszy: uporządkuj dane, aby można je było szybko przeszukiwać . Teraz musisz zmienić strukturę, której używasz do przechowywania danych. wyobraź sobie takie drzewo:

ABC
 Dodaj lepszy sufit
 Powyżej konturu kości

Można to po prostu zaimplementować za pomocą tablicy (jeśli pracujesz z nazwami ANSI, w przeciwnym razie słownik byłby lepszy). Zbuduj listę w ten sposób (dla celów ilustracyjnych, pasuje do początku ciągu):

var dictionary = new Dictionary<char, List<string>>();
foreach (var user in users)
{
    char letter = user[0];
    if (dictionary.Contains(letter))
        dictionary[letter].Add(user);
    else
    {
        var newList = new List<string>();
        newList.Add(user);
        dictionary.Add(letter, newList);
    }
}

Wyszukiwanie zostanie przeprowadzone przy użyciu pierwszego znaku:

char letter = textBox_search.Text[0];
if (dictionary.Contains(letter))
{
    listBox_choices.DataSource =
        new MyListWrapper(dictionary[letter].Where(x => x.Contains(textBox_search.Text)));
}

Zwróć uwagę, że użyłem MyListWrapper()zgodnie z sugestią w pierwszym kroku (ale pominąłem drugą sugestię dla zwięzłości, jeśli wybierzesz odpowiedni rozmiar klucza słownika, możesz sprawić, że każda lista będzie krótka i szybka, aby - być może - uniknąć czegokolwiek innego). Ponadto pamiętaj, że możesz spróbować użyć pierwszych dwóch znaków ze swojego słownika (więcej list i krótszych). Jeśli to rozszerzysz, otrzymasz drzewo (ale nie sądzę, że masz tak dużą liczbę przedmiotów).

Istnieje wiele różnych algorytmów wyszukiwania ciągów (z powiązanymi strukturami danych), aby wymienić tylko kilka:

• Wyszukiwanie oparte na automatach skończonych : w tym podejściu unikamy cofania się poprzez konstruowanie deterministycznego automatu skończonego (DFA), który rozpoznaje przechowywany ciąg wyszukiwania. Są drogie w budowie - zwykle są tworzone przy użyciu konstrukcji zestawu napędowego - ale są bardzo szybkie w użyciu.
• Stubs : Knuth – Morris – Pratt oblicza DFA, który rozpoznaje wejścia ze ciągiem do wyszukania jako przyrostek, Boyer – Moore rozpoczyna wyszukiwanie od końca igły, więc zwykle może przeskoczyć całą długość igły w każdym kroku. Baeza – Yates śledzi, czy poprzednie znaki j były prefiksem szukanego ciągu i dlatego można go dostosować do wyszukiwania rozmytego. Algorytm bitapowy jest zastosowaniem podejścia Baeza-Yatesa.
• Metody indeksowania : szybsze algorytmy wyszukiwania opierają się na wstępnym przetwarzaniu tekstu. Po zbudowaniu indeksu podciągów, na przykład drzewa sufiksów lub tablicy sufiksów, wystąpienia wzorca można szybko znaleźć.
• Inne warianty : niektóre metody wyszukiwania, na przykład wyszukiwanie trygramowe, mają na celu znalezienie wyniku „bliskości” między szukanym ciągiem a tekstem, a nie „dopasowania / braku dopasowania”. Są to czasami nazywane wyszukiwaniami „rozmytymi”.

Kilka słów o wyszukiwaniu równoległym. Jest to możliwe, ale rzadko jest to trywialne, ponieważ narzut, aby był równoległy, może być znacznie wyższy niż samo wyszukiwanie. Nie przeprowadzałbym samego wyszukiwania równolegle (partycjonowanie i synchronizacja wkrótce staną się zbyt rozbudowane i być może skomplikowane), ale przeniósłbym wyszukiwanie do osobnego wątku . Jeśli główny wątek nie jest zajęty, Twoi użytkownicy nie odczują żadnego opóźnienia podczas pisania (nie zauważą, czy lista pojawi się po 200 ms, ale poczują się nieswojo, jeśli będą musieli czekać 50 ms po wpisaniu) . Oczywiście samo wyszukiwanie musi być wystarczająco szybkie, w tym przypadku nie używasz wątków do przyspieszania wyszukiwania, ale do utrzymywania responsywności interfejsu użytkownika . Należy pamiętać, że osobny wątek nie spowoduje wysłania zapytaniaszybciej , nie zawiesi interfejsu użytkownika, ale jeśli twoje zapytanie było powolne, nadal będzie wolne w oddzielnym wątku (ponadto musisz obsługiwać również wiele kolejnych żądań).

Możesz spróbować użyć PLINQ (Parallel LINQ). Chociaż nie gwarantuje to zwiększenia prędkości, musisz to sprawdzić metodą prób i błędów.

Wątpię, czy będziesz w stanie to zrobić szybciej, ale na pewno powinieneś:

a) Użyj metody rozszerzenia AsParallel LINQ

a) Użyj jakiegoś timera, aby opóźnić filtrowanie

b) Umieść metodę filtrowania na innym wątku

Trzymaj string previousTextBoxValuegdzieś jakieś miejsce. Stwórz timer z opóźnieniem 1000 ms, który uruchamia wyszukiwanie na tiku, jeśli previousTextBoxValuejest taki sam jak twoja textbox.Textwartość. Jeśli nie - ponownie przypisz previousTextBoxValuedo aktualnej wartości i zresetuj timer. Ustaw początek licznika na zdarzenie zmienione w polu tekstowym, a dzięki temu aplikacja będzie płynniejsza. Filtrowanie 120 000 rekordów w ciągu 1-3 sekund jest w porządku, ale Twój interfejs użytkownika musi pozostać responsywny.

Możesz także spróbować użyć funkcji BindingSource.Filter . Użyłem go i działa jak urok do filtrowania z wielu rekordów, za każdym razem aktualizując tę ​​właściwość o wyszukiwany tekst. Inną opcją byłoby użycie AutoCompleteSource dla kontrolki TextBox.

Mam nadzieję, że to pomoże!

Chciałbym posortować kolekcję, wyszukać tylko część początkową i ograniczyć wyszukiwanie do jakiejś liczby.

tak dalej ininializacja

allUsers.Sort();

i szukaj

allUsers.Where(item => item.StartWith(textBox_search.Text))

Może możesz dodać trochę pamięci podręcznej.

Użyj równoległego LINQ. PLINQjest równoległą implementacją LINQ to Objects. PLINQ implementuje pełny zestaw standardowych operatorów zapytań LINQ jako metody rozszerzające dla przestrzeni nazw T: System.Linq i ma dodatkowe operatory dla operacji równoległych. PLINQ łączy w sobie prostotę i czytelność składni LINQ z mocą programowania równoległego. Podobnie jak kod, który jest przeznaczony dla biblioteki równoległej zadań, zapytania PLINQ są skalowane w stopniu współbieżności na podstawie możliwości komputera hosta.

Wprowadzenie do PLINQ

Zrozumienie przyspieszenia w PLINQ

Możesz także użyć Lucene.Net

Lucene.Net to port biblioteki silnika wyszukiwania Lucene, napisany w języku C # i przeznaczony dla użytkowników środowiska uruchomieniowego .NET. Biblioteka wyszukiwania Lucene jest oparta na indeksie odwróconym. Lucene.Net ma trzy główne cele:

Zgodnie z tym, co widziałem, zgadzam się z faktem uporządkowania listy.

Jednak sortowanie po utworzeniu listy będzie bardzo powolne, sortowanie podczas budowania zapewni lepszy czas wykonania.

W przeciwnym razie, jeśli nie musisz wyświetlać listy lub utrzymywać kolejności, użyj hashmap.

Hashmap będzie haszował twój ciąg i przeszukiwał dokładny offset. Myślę, że powinno być szybciej.

Spróbuj użyć metody BinarySearch, która powinna działać szybciej niż metoda Contains.

Zawiera będzie O (n) BinarySearch to O (lg (n))

Myślę, że posortowana kolekcja powinna działać szybciej przy wyszukiwaniu i wolniej przy dodawaniu nowych elementów, ale jak zrozumiałem, masz tylko problem z wydajnością wyszukiwania.