Dlaczego wyszukiwanie binarne, które wymaga posortowanych danych, uważa się za lepsze niż wyszukiwanie liniowe?

20

Zawsze słyszałem, że wyszukiwanie liniowe jest naiwnym podejściem, a wyszukiwanie binarne jest lepsze niż pod względem wydajności ze względu na lepszą asymptotyczną złożoność. Ale nigdy nie zrozumiałem, dlaczego jest lepsze niż wyszukiwanie liniowe, gdy przed wyszukiwaniem binarnym wymagane jest sortowanie?

Wyszukiwanie liniowe jest, O(n)a wyszukiwanie binarne O(log n). To wydaje się być podstawą do stwierdzenia, że ​​wyszukiwanie binarne jest lepsze. Ale wyszukiwanie binarne wymaga sortowania, które jest O(n log n)najlepsze algorytmy. Wyszukiwanie binarne nie powinno być w rzeczywistości szybsze, ponieważ wymaga sortowania.

Czytam CLRS, w którym autor sugeruje, że w sortowaniu wstawiania zamiast naiwnego wyszukiwania liniowego lepiej jest użyć wyszukiwania binarnego w celu znalezienia miejsca, w którym element musi zostać wstawiony. W tym przypadku wydaje się to uzasadnione, ponieważ przy każdej iteracji pętli istnieje posortowana lista, na której można zastosować wyszukiwanie binarne. Ale w ogólnym przypadku, gdy nie ma gwarancji, że zestaw danych, w którym musimy szukać, nie używa wyszukiwania binarnego w rzeczywistości gorszego niż wyszukiwanie liniowe ze względu na wymagania dotyczące sortowania?

Czy pomijam jakieś względy praktyczne, które sprawiają, że wyszukiwanie binarne jest lepsze niż wyszukiwanie liniowe? Czy wyszukiwanie binarne jest uważane za lepsze niż wyszukiwanie liniowe bez uwzględnienia czasu obliczeń wymaganego do sortowania?

Aseem Bansal
źródło
6
Podobnie jak w przypadku wielu innych rzeczy, wszystko sprowadza się do: „To zależy ...;)”
Jeff B
Jeśli lista jest już posortowana, czy uważasz, że wyszukiwanie liniowe jest jeszcze lepsze? To może być coś do rozważenia tutaj.
JB King
3
Każdemu, kto myśli o zmianie tytułu , nie należy zajmować się posortowanymi danymi, ponieważ usunięcie go sprawia, że ​​wydaje się to zupełnie innym pytaniem.
Aseem Bansal,

Odpowiedzi:

53

Czy pomijam jakieś względy praktyczne, które sprawiają, że wyszukiwanie binarne jest lepsze niż wyszukiwanie liniowe?

Tak - musisz wykonać sortowanie O (n log n) tylko raz, a następnie możesz wyszukiwać binarnie O (log n) tak często, jak chcesz, podczas gdy wyszukiwanie liniowe to O (n) za każdym razem.

Oczywiście jest to tylko zaleta, jeśli faktycznie przeprowadzasz wielokrotne wyszukiwania tych samych danych. Ale scenariusze „pisz raz, czytaj często” są dość powszechne.

Michael Borgwardt
źródło
Jeśli robisz coś tylko raz, nie ma sensu go optymalizować.
14

Podstawowym założeniem jest to, że nie przeprowadzasz jednego wyszukiwania.

Jeśli więc musisz wielokrotnie przeszukiwać te same dane, musisz tylko raz posortować dane i skorzystać z wyszukiwania binarnego.

Jeśli często wyszukujesz i zmieniasz dane, warto skorzystać z posortowanej listy, w której nowe wpisy są sortowane na liście.

Zasadniczo wyszukiwanie binarne jest lepsze, gdy przeszukujesz tę samą listę wiele razy bez potrzeby uciekania się.

Kiedy za każdym razem musisz sortować przed wyszukiwaniem, nie ma żadnej przewagi.

Zauważmy, że istnieją algorytmy sortowania, które są bardzo szybkie, gdy lista jest już posortowana (lub prawie posortowana). Większość ustaleń dotyczących wydajności oczekuje nieposortowanej listy.

Uwe Plonus
źródło
2
Jeśli często wyszukujesz i wstawiasz, możesz spojrzeć na bardziej skomplikowane struktury danych (np. Drzewa binarne).
MarkJ
@MarkJ podstawowym pytaniem oryginalnego plakatu było wyszukiwanie na liście. W przeciwnym razie całkowicie się z tobą zgadzam.
Uwe Plonus,
7

ponieważ gdy masz już posortowaną listę, nie musisz jej ponownie sortować za każdym razem, co oznacza, że ​​jeśli masz więcej niż O (log n) wyszukiwań z wyprzedzeniem, sortowanie z wyprzedzeniem zapewni Ci wygraną (w O(n log n + k log n)porównaniu zO(k*n)

maniak zapadkowy
źródło
5

Wyobraź sobie dwie książki telefoniczne.

Jedna książka telefoniczna ma nazwy w kolejności alfabetycznej. Aby znaleźć żądany wpis, otwórz go w środku, sprawdź wpis, a następnie przejdź do przodu lub do tyłu w zależności od tego, czy został przekroczony, czy cofnięty.

Druga książka telefoniczna ma nazwy w losowej kolejności. Aby znaleźć odpowiedni wpis, zacznij od początku i kontynuuj, aż znajdziesz to, czego szukasz.

Czy druga książka będzie działać w jakimkolwiek rozsądnym mieście?

Gort the Robot
źródło
3

Myślę, że wartość wyszukiwania binarnego nad wyszukiwaniem liniowym jest kontekstowa. Jeśli zaczniesz od ogromnego, nieuporządkowanego zestawu danych i planujesz jedynie wyciągnąć z niego niewielką liczbę elementów, sortowanie i wyszukiwanie binarne będzie powolne. Jeśli jednak utrzymujesz uporządkowaną listę przez cały okres użytkowania aplikacji i regularnie uzyskujesz do niej dostęp, wyszukiwanie binarne jest znacznie lepszym sposobem.

Amish Programmer
źródło
3

Podobnie jak wiele innych osób odpowiedziało, wyszukiwanie binarne jest rzeczywiście preferowane, ponieważ krok sortowania można wykonać tylko raz, a wyszukiwanie można wykonać tyle razy, ile chcesz. Jednak w przypadku niektórych wartości n (tj. Niektórych rozmiarów wejściowych) wyszukiwanie binarne jest zawsze bardziej wydajne niż wyszukiwanie liniowe (nawet dla pojedynczego przebiegu).

„Punkt krytyczny” oblicza się, rozwiązując asymptotyczne równanie złożoności:

n log n + log n = n

Jak widać na Wolfram Alpha, istnieje wartość liczbowa dla n, która zapewnia, że ​​wyszukiwanie i sortowanie binarne jest zawsze szybsze niż samo wyszukiwanie liniowe. Oczywiście rzeczywista wartość n, która działa w twoim przypadku, zależy od wielu czynników, które mogą być trudne do oszacowania.

Według tego interesującego artykułu Marka Probsta, który zawiera kilka ciekawych pomiarów wydajności obecnych procesorów:

Jeśli potrzebujesz przeszukać uporządkowaną tablicę liczb całkowitych, a wydajność jest naprawdę bardzo ważna, użyj wyszukiwania liniowego, jeśli tablica ma mniej więcej około 64 elementów, a wyszukiwania binarnego, jeśli jest powyżej.

LorenzCK
źródło
2

Słowami laika:

Jeśli masz nieuporządkowaną listę z dziesięcioma miliardami pozycji, a pozycja, której szukasz, jest ostatnią, skończysz czytać dziesięć miliardów pozycji.

W przypadku wyszukiwania binarnego indeksowanie można wykonać tylko raz. Późniejsze wstawki można wykonać w odpowiednim miejscu, aby zachować porządek.

Tulains Córdova
źródło
2

Chociaż wymieniono już wiele dobrych powodów, dla których „wyszukiwanie binarne jest lepsze”, możemy również spojrzeć na zalety z perspektywy użytkownika:

Chociaż normalnie możesz żyć bardzo dobrze z niewielkim czasem oczekiwania między operacjami wprowadzania danych podczas sortowania wstawki, chcesz, aby „wyszukiwanie” było tak szybkie, jak to możliwe. Z punktu widzenia użytkownika posortowana wstawka w połączeniu z wyszukiwaniem binarnym zapewnia najlepszą możliwą obsługę.

tofro
źródło