TI/Bazy danych: Różnice pomiędzy wersjami
(Utworzono nową stronę " ==Co widać w Google'ach?== Odpowiedź wyszukiwarki (np. google.pl) dociera do nas zwykle w kilka sekund, na pewno więc nie są w tym czasie przeszukiwane wszystkie ko...") |
|||
| Linia 12: | Linia 12: | ||
Jeśli w książce telefonicznej mamy np. <math>N=1024</math> adresów posortowanych tylko według nazwisk, i szukamy znanego numeru telefonu, to w najgorszym razie musimy przejrzeć każdą pozycję, czyli wykonać <math>N=1024</math> operacji porównania szukanego numeru z numerem przypisanym dla danego nazwiska. | Jeśli w książce telefonicznej mamy np. <math>N=1024</math> adresów posortowanych tylko według nazwisk, i szukamy znanego numeru telefonu, to w najgorszym razie musimy przejrzeć każdą pozycję, czyli wykonać <math>N=1024</math> operacji porównania szukanego numeru z numerem przypisanym dla danego nazwiska. | ||
| − | Jeśli szukamy nazwiska, możemy użyć np. algorytmu [[ | + | Jeśli szukamy nazwiska, możemy użyć np. algorytmu [[wikipedia:Przeszukiwanie_binarne|przeszukiwania binarnego]]; wtedy złożoność jest rzędu <math>\log_2(N)</math>, czyli |
w najgorszym razie wykonujemy 10 porównań. Dla miliona wystarczy już tylko 20 porównań — przeszukiwanie działać będzie 50 tysięcy razy szybciej. Dla miliarda (1 000 000 000) — tylko 30 operacji, czyli kilkadziesiąt milionów razy szybciej. | w najgorszym razie wykonujemy 10 porównań. Dla miliona wystarczy już tylko 20 porównań — przeszukiwanie działać będzie 50 tysięcy razy szybciej. Dla miliarda (1 000 000 000) — tylko 30 operacji, czyli kilkadziesiąt milionów razy szybciej. | ||
Wersja z 18:10, 23 maj 2015
Co widać w Google'ach?
Odpowiedź wyszukiwarki (np. google.pl) dociera do nas zwykle w kilka sekund, na pewno więc nie są w tym czasie przeszukiwane wszystkie komputery Internetu. Całe wyszukiwanie odbywa się na dyskach jednego systemu, na których znajduje się indeksowana baza danych o stronach WWW, udostępniana użytkownikom za pośrednictwem wyszukiwarki internetowej.
Indeks, czyli jak szybko szukać?
Jeśli w książce telefonicznej mamy np. [math]N=1024[/math] adresów posortowanych tylko według nazwisk, i szukamy znanego numeru telefonu, to w najgorszym razie musimy przejrzeć każdą pozycję, czyli wykonać [math]N=1024[/math] operacji porównania szukanego numeru z numerem przypisanym dla danego nazwiska.
Jeśli szukamy nazwiska, możemy użyć np. algorytmu przeszukiwania binarnego; wtedy złożoność jest rzędu [math]\log_2(N)[/math], czyli w najgorszym razie wykonujemy 10 porównań. Dla miliona wystarczy już tylko 20 porównań — przeszukiwanie działać będzie 50 tysięcy razy szybciej. Dla miliarda (1 000 000 000) — tylko 30 operacji, czyli kilkadziesiąt milionów razy szybciej.
Quick sort:
http://www.youtube.com/v/FSyr8o8jjwM?fs=1
http://www.youtube.com/v/cNB5JCG3vts?fs=1
Monopole wyszukiwarek
Jeszcze kilka–kilkanaście lat temu konkurowało ze sobą co najmniej kilka wyszukiwarek. Obecnie google.com właściwie wyparł wszelką konkurencję. Pozycję tę uzyskał dzięki świetnej technologii przeszukiwania bazy danych oraz jej tworzenia i uaktualniania, czyli indeksowania Internetu. Możemy to uznać za wygodne uproszczenie ("nie muszę się zastanawiać, której wyszukiwarki użyć"), ale z drugiej strony na każdy powstający monopol powinniśmy patrzeć ostrożnie.
Coraz częściej słyszymy stwierdzenie "nie znalazłem tego w Internecie", co ma niemalże podawać w wątpliwość możliwość istnienia takiego "nieznajdowalnego" bytu (nazwy, nazwiska, pojęcia...). A z kolei "nie znalazłem w Internecie" w praktyce oznacza "google nie znalazł". Ale google tak naprawdę nie szuka w Internecie, tylko w swojej bazie danych! Więc jeśli zarządzające nią osoby zdecydują się usunąć zapisy związane z jakimś pojęciem czy osobą, skazują je na częściowy niebyt... jak w powieściach science fiction.
Ta uwaga nie powinna bynajmniej być odczytywana jako sugestia, że firma zarządzająca aktualnie serwisem google czy jakimkolwiek innym dopuszcza się takich praktyk. Ale warto być świadomym, że jest to technicznie możliwe.
