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

80

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ść?

etaiso
źródło
10
HashSet<T>nie pomoże ci tutaj, ponieważ szukasz części łańcucha.
Dennis
8
Wypróbuj tablice przyrostków .
CodesInChaos
66
Nie pytaj „jak najszybciej”, ponieważ zajęłoby to dosłownie tygodnie lub lata badań. Powiedz raczej „Potrzebuję rozwiązania działającego w czasie krótszym niż 30 ms” lub jakimkolwiek innym celem jest osiągnięcie celu. Nie potrzebujesz najszybszego urządzenia, potrzebujesz wystarczająco szybkiego urządzenia.
Eric Lippert
44
Również uzyskać profilera . Nie zgaduj, gdzie jest wolna część; takie domysły są często błędne. Wąskie gardło może być gdzieś zaskakujące.
Eric Lippert
4
@Basilevs: Kiedyś napisałem uroczą tabelę z haszowaniem O (1), która w praktyce była wyjątkowo powolna. Profilowałem go, aby dowiedzieć się, dlaczego i odkryłem, że przy każdym wyszukiwaniu wywoływało metodę, która - bez żartów - kończyła się pytaniem rejestru „czy jesteśmy teraz w Tajlandii?”. Brak buforowania informacji o tym, czy użytkownik znajduje się w Tajlandii, był wąskim gardłem w tym kodzie O (1). Lokalizacja wąskiego gardła może być głęboko sprzeczna z intuicją . Użyj profilera.
Eric Lippert

Odpowiedzi:

48

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.

Groo
źródło
Właśnie przetestowałem Twoje rozwiązanie i działa idealnie! Ładnie wykonane. Jedyny problem, jaki mam, to to, że nie mogę dokonać _signal.Dispose();kompilacji (błąd dotyczący poziomu ochrony).
etaiso
@etaiso: to dziwne, gdzie dokładnie dzwonisz _signal.Dispose()Czy to gdzieś poza BackgroundWordFilterklasą?
Groo
1
@Groo Jest to jawna implementacja, co oznacza, że ​​nie można tego wywołać bezpośrednio. Powinieneś użyć albo usingbloku, albo zadzwońWaitHandle.Close()
Matthew Watson
1
Ok, teraz ma sens, metoda została upubliczniona w .NET 4. Strona MSDN dla .NET 4 wymienia ją jako metody publiczne , podczas gdy strona dla .NET 3.5 pokazuje ją jako metody chronione . To wyjaśnia również, dlaczego istnieje warunkowa definicja w źródle mono dla WaitHandle .
Groo
1
@Groo Przepraszamy, powinienem był wspomnieć, że mówię o starszej wersji .Net - przepraszam za zamieszanie! Pamiętaj jednak, że nie musi rzucać - .Close()zamiast tego może zadzwonić , co samo w sobie wzywa .Dispose().
Matthew Watson
36

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.

Matthew Watson
źródło
1
Dzięki Matthew. Wypróbowałem twoje rozwiązanie, ale nie sądzę, że problem dotyczy populacji ListBox. Myślę, że potrzebuję lepszego podejścia, ponieważ ten rodzaj filtrowania jest bardzo naiwny (np. - wyszukanie „abc” zwraca 0 wyników, nie powinienem nawet szukać „abcX” itd.)
etaiso
@etaiso dobrze (nawet jeśli rozwiązanie Matthew może działać świetnie, jeśli tak naprawdę nie musisz ustawiać wszystkich dopasowań), dlatego jako drugi krok zasugerowałem zawężenie wyszukiwania zamiast wykonywania pełnego wyszukiwania za każdym razem.
Adriano Repetti
5
@etaiso Cóż, czas wyszukiwania jest znikomy, jak powiedziałem. Wypróbowałem to ze 120 000 strun i szukanie bardzo długiej struny, która nie dawała żadnych dopasowań, oraz bardzo krótkiej struny, która dawała wiele dopasowań, zajęło mniej niż 1/50 sekundy.
Matthew Watson
3
Czy textBox_search.Textprzyczynia się do wymiernej ilości czasu? TextJednokrotne umieszczenie właściwości w polu tekstowym dla każdego ze 120 tys. Ciągów prawdopodobnie powoduje wysłanie 120 tys. Komunikatów do okna sterowania edycją.
Gabe
@ Gabe Tak, to robi. Zobacz moją odpowiedź po szczegóły.
Andris
28

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.

Basilevs
źródło
Z tego, co wiem, tablice przyrostków są zwykle lepszym wyborem niż drzewa przyrostków. Łatwiejsze do wdrożenia i mniejsze zużycie pamięci.
CodesInChaos
Proponuję SortedList, który jest bardzo łatwy do zbudowania i utrzymania kosztem narzutu pamięci, który można zminimalizować poprzez zapewnienie pojemności list.
Basilevs
Wydaje się również, że tablice (i oryginalny ST) są przeznaczone do obsługi dużych tekstów, podczas gdy tutaj mamy dużą liczbę krótkich fragmentów, co jest innym zadaniem.
Basilevs
+1 za dobre podejście, ale użyłbym mapy skrótów lub rzeczywistego drzewa wyszukiwania, zamiast ręcznie przeszukiwać listę.
OrangeDog
Czy jest jakaś zaleta używania drzewa sufiksów zamiast drzewa przedrostków?
jnovacho
15

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.

Dennis
źródło
Indeksowanie to wyszukiwanie oparte na skrótach. Po prostu dodajesz wszystkie podciągi jako klucze, a nie tylko wartość.
OrangeDog
3
@OrangeDog: nie zgadzam się. Wyszukiwanie indeksowane można zaimplementować jako wyszukiwanie oparte na skrótach według kluczy indeksowych, ale nie jest to konieczne i nie jest to wyszukiwanie oparte na skrótach według samej wartości ciągu.
Dennis
@Dennis Zgadzam się. +1, aby anulować ducha -1.
użytkownik
+1, ponieważ implementacje takie jak wyszukiwarka tekstowa mają inteligentniejsze optymalizacje niż string.Contains. To znaczy. wyszukiwanie baw bcaaaabaaspowoduje wyświetlenie (zindeksowanej) listy pominięć. Pierwsza bjest brana pod uwagę, ale nie pasuje, ponieważ następna to a c, więc przeskoczy do następnej b.
Caramiriel
12

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.

paulslater19
źródło
Zobacz implementację C # ogranicznika zdarzeń w klasie EventThrotler w
Frans Bouma
11

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);
}
animaonline
źródło
1
Wiem, że to możliwe. Ale moje pytanie brzmi, czy i jak mogę skrócić ten proces?
etaiso
1
@etaiso to nie powinno być problemem, chyba że pracujesz na jakimś naprawdę niskim sprzęcie, upewnij się, że nie używasz debugera, CTRL + F5
animaonline
1
To nie jest dobry kandydat do PLINQ, ponieważ metoda String.Containsnie jest droga. msdn.microsoft.com/en-us/library/dd997399.aspx
Tim Schmelter
1
@TimSchmelter, kiedy mówimy o tonach strun, to prawda!
animaonline
4
@TimSchmelter Nie mam pojęcia, co próbujesz udowodnić, użycie dostarczonego przeze mnie kodu najprawdopodobniej zwiększy wydajność OP, a oto test porównawczy, który pokazuje, jak to działa: pastebin.com/ATYa2BGt --- Okres - -
animaonline
11

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.

Andris
źródło
Nie sądzę, aby to poprawiło cokolwiek, ponieważ BeginUpdatei EndUpdatesą przeznaczone do użycia podczas dodawania elementów indywidualnie lub podczas używania AddRange().
etaiso
To zależy od tego, jak dana DataSourcenieruchomość jest realizowana. Może warto spróbować.
Andris,
Twoje wyniki profilowania bardzo różnią się od moich. Udało mi się przeszukać 120 tys. Ciągów w 30 ms, ale dodanie ich do listy zajęło 4500 ms. Wygląda na to, że dodajesz 2,5M ciągów do listy w czasie krótszym niż 600 ms. Jak to możliwe?
Gabe
@ Gabe Podczas profilowania użyłem wejścia, w którym tekst filtru eliminował dużą część oryginalnej listy. Jeśli użyję danych wejściowych, w których tekst filtru nie usuwa niczego z listy, otrzymuję wyniki podobne do twoich. Zaktualizuję swoją odpowiedź, aby wyjaśnić, co zmierzyłem.
Andris,
9

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 #.

Groo
źródło
1
Zakładając, że filtruje swoje rekordy za pomocą przedrostka.
Tarec
1
Zauważ, że używa metody String.Contains () zamiast String.StartsWith (), więc może nie być dokładnie tym, czego szukamy. Mimo wszystko - Twój pomysł jest niewątpliwie lepszy niż zwykłe filtrowanie z rozszerzeniem StartsWith () w scenariuszu z prefiksem.
Tarec
Gdyby nie znaczy rozpoczyna się, a następnie Trie można łączyć z podejściem pracowników tła dla zwiększenia wydajności
Lyndon Biały
8

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;
}
LarsTech
źródło
2
+1 podczas gdy wszyscy inni próbowali zoptymalizować wyszukiwanie, które zajmuje tylko 30 ms, jesteś jedyną osobą, która rozpoznała, że ​​problem polega na wypełnieniu pola listy.
Gabe
7

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ń).

Adriano Repetti
źródło
1
Jak niektórzy już zauważyli, OP nie chce ograniczać wyników tylko do przedrostków (tj. Używa Contains, a nie StartsWith). Na marginesie, zwykle lepiej jest użyć ContainsKeymetody ogólnej podczas wyszukiwania klucza, aby uniknąć boksu, a jeszcze lepiej, TryGetValueaby uniknąć dwóch wyszukiwań.
Groo
2
@Groo masz rację, jak powiedziałem, jest to tylko do celów ilustracyjnych. Celem tego kodu nie jest działające rozwiązanie, ale wskazówka: jeśli spróbowałeś wszystkiego innego - unikaj kopiowania, zawężaj wyszukiwanie, przenieś go do innego wątku - i to nie wystarczy, musisz zmienić strukturę danych, z której korzystasz . Przykład dotyczy początku łańcucha, aby pozostać prostym.
Adriano Repetti
@Adriano dzięki za jasną i szczegółową odpowiedź! Zgadzam się z większością rzeczy, o których wspomniałeś, ale jak powiedział Groo, ostatnia część porządkowania danych nie ma zastosowania w moim przypadku. Ale myślę, że może powinienem mieć podobny słownik z kluczami jak zawarta litera (chociaż nadal będą duplikaty)
etaiso
po szybkim sprawdzeniu i obliczeniu pomysł „zawartej litery” nie jest dobry tylko dla jednego znaku (a jeśli pójdziemy na kombinacje dwóch lub więcej, otrzymamy bardzo dużą tabelę haszowania)
etaiso
@etaiso tak, możesz zachować listę dwóch liter (aby szybko zmniejszyć listę podrzędną), ale prawdziwe drzewo może działać lepiej (każda litera jest połączona z jej następcami, nie ma znaczenia, gdzie znajduje się w ciągu, więc dla "HOME" masz „H-> O”, „O-> M” i „M-> E”. Jeśli szukasz „om”, szybko je znajdziesz. Problem polega na tym, że staje się to bardziej skomplikowane i może być za dużo dla ciebie scenariusz (IMO)
Adriano Repetti
4

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.

D. Gierveld
źródło
4

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.

Tarec
źródło
1
Nie zgadzam się, aby było to równoległe, ale całkowicie zgadzam się z pozostałymi dwoma punktami. Może nawet wystarczyć do spełnienia wymagań interfejsu użytkownika.
Adriano Repetti
Zapomniałem o tym wspomnieć, ale używam .NET 3.5, więc AsParallel nie wchodzi w grę.
etaiso
3

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!

Nigdy bez nadziei
źródło
2

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.

hardsky
źródło
1
Nie pracuje z początkiem łańcucha (dlatego używa String.Contains ()). Dzięki Contains () posortowana lista nie zmienia wydajności.
Adriano Repetti
Tak, z „Zawiera” jest to bezużyteczne. Podoba mi się sugestia dotycząca drzewa sufix stackoverflow.com/a/21383731/994849 W wątku jest wiele interesujących odpowiedzi, ale zależy to od tego, ile czasu może poświęcić na to zadanie.
hardsky
1

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:


źródło
1

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.

dada
źródło
Hashmap z jakim kluczem? Chcę móc znaleźć słowa kluczowe zawarte w ciągach.
etaiso
ponieważ klucz możesz umieścić numer na liście, jeśli chcesz bardziej skomplikować, możesz dodać numer wraz z nazwą, wybór należy do Ciebie.
dada
co do reszty albo nie przeczytałem wszystkiego albo było złe wyjaśnienie (prawdopodobnie oba;)) [cytat] mam plik tekstowy z około 120 000 użytkowników (ciągi znaków), który chciałbym przechowywać w kolekcji, a później wykonać szukaj w tej kolekcji. [/ quote] Myślałem, że to tylko wyszukiwanie ciągów znaków.
dada
1

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.

user2917540
źródło