Wyszukiwanie binarne - ale to jest szybkie :O |
Wyszukiwanie binarne - ale to jest szybkie :O |
4.10.2020, 11:26:48
Post
#1
|
|
Grupa: Zarejestrowani Postów: 1 707 Pomógł: 266 Dołączył: 3.07.2012 Skąd: Poznań Ostrzeżenie: (0%) |
Cześć,
zastanawiałem się jak szybkie jest wyszukiwanie binarne w porównaniu do naiwnego, liniowego przeszukiwania. Wyniki mnie dobiły Załóżmy, że przeszukujemy żyjącą ludność świata (około 7 i pół miliarda rekordów), chcąc znaleźć daną osobę. Dla zobrazowania przypadku załóżmy, że robimy to "ręcznie" i każda osoba zajmuje nam 1 sekundę. W przypadku wyszukiwania binarnego, najbardziej pesymistyczny przypadek to 33 sekundy pracy. W przypadku wyszukiwania liniowego, jest to... ... Ponad 237 lat. A teraz przykład z przeszukiwaniem atomów we wszechświecie (tak, wiem - wszyscy to robimy prawie codziennie). Naukowcy szacują, że liczba atomów we wszechświecie to około 1 i 80 zer, czyli: 10000000000000000000000000000000000000000000000000000000000000000000000000000000 0 Metodyka ta sama, szukanie ręczne i jedna sekunda na rekord. W przypadku wyszukiwania binarnego, najbardziej pesymistyczny przypadek to 266 sekund pracy, czyli niecałe 4 i pół minuty. W przypadku wyszukiwania liniowego, jest to... ... Ponad 3168808781402895023702689684893654777296118843004537734174968945673942251 lat. Zakładając, że wszechświat istnieje od 13,82 miliardów lat, nasz wszechświat musiałby się zacząć i skończyć 229291518191236977113074506866400490397693114544467274542327709 razy, żebyśmy przeszukali liniowo wszystkie atomy naszą metodą. Bania zryta. Już mnie tak nie dziwi, że Google jest takie szybkie. Kwestia bardzo dobrego indeksowania, bo samo wyszukiwanie można niesamowicie wręcz przyśpieszyć. Nerdowa część mnie jest szczęśliwa. Ten post edytował SmokAnalog 4.10.2020, 11:29:22 |
|
|
4.10.2020, 20:41:47
Post
#2
|
|
Grupa: Zarejestrowani Postów: 1 836 Pomógł: 225 Dołączył: 20.03.2005 Skąd: Będzin Ostrzeżenie: (0%) |
Tylko pamiętaj, wyszukiwanie binarne jest użyteczne, tylko wtedy, kiedy lista jest posortowana. Dlatego jest takie szybkie, bo pomija połowę niepotrzebnych indeksów z wyszukiwaną wartością.
|
|
|
4.10.2020, 20:49:59
Post
#3
|
|
Grupa: Zarejestrowani Postów: 1 707 Pomógł: 266 Dołączył: 3.07.2012 Skąd: Poznań Ostrzeżenie: (0%) |
No Ameryki nie odkryłeś
Dlatego pisałem, że to kwestia dobrych indeksów. I nie połowę pomija, tylko wykładniczą ilość, jak widać na załączonym przykładzie. Ciekaw jestem jakie dodatkowe sztuczki są stosowane przez Google, żeby to jeszcze bardziej przyśpieszyć, bo przy wysublimowanych indeksach nie trzeba nawet tak skakać po połówkach. |
|
|
5.10.2020, 14:22:23
Post
#4
|
|
Grupa: Zarejestrowani Postów: 8 068 Pomógł: 1414 Dołączył: 26.10.2005 Ostrzeżenie: (0%) |
|
|
|
Wersja Lo-Fi | Aktualny czas: 26.04.2024 - 04:32 |