Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

 
Reply to this topicStart new topic
> Wyszukiwanie binarne - ale to jest szybkie :O
SmokAnalog
post 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 laugh.gif

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. laugh.gif

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
Go to the top of the page
+Quote Post
Tomplus
post 4.10.2020, 20:41:47
Post #2





Grupa: Zarejestrowani
Postów: 1 825
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ą.
Go to the top of the page
+Quote Post
SmokAnalog
post 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ś Lkingsmiley.png

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.
Go to the top of the page
+Quote Post
Pyton_000
post 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%)
-----


https://www.8bitmen.com/google-database-how...yte-scale-data/
Go to the top of the page
+Quote Post

Reply to this topicStart new topic
1 Użytkowników czyta ten temat (1 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 



RSS Wersja Lo-Fi Aktualny czas: 19.03.2024 - 10:04