Wydajność algorytmu

Mam doniesienie, że wysyłają nowy łazik na Marsa. Odpowiadamy za jedno: mamy zaprogramować algorytm, do łazika, sprawdzający, czy liczby są pierwsze. Powiedzmy, że łazik porozumiewa się używając RSA. Musi mieć on wgrany algorytm wykonujący test pierwszości. Projektując łazik lub cokolwiek, co poleci w Kosmos, musicie dbać o wydajność pod każdym względem. Składniki muszą być bardzo lekkie. Każdy podsystem musi zużywać jak najmniej mocy, trzeba oszczędzać energię i masę w każdym momencie procesu projektowego. Ułatwiliśmy sobie pracę. Będziemy mieć do czynienia z liczbami do tej wielkości. Trzeba sobie z nimi radzić szybko. Przy bardzo małych danych wejściowych, np. przy 90, algorytm powinien to obliczyć prawie tak szybko, jak tę całą liczbę. Rozmiar danych wejściowych rośnie, ale nie chcemy zauważalnego spowolnienia. Przeanalizuję pytania użytkowników i ich pomysły, bardzo dobre, z matematycznego punktu widzenia. Sprawdzamy, czy liczba n jest pierwsza czy złożona. Mając dane n, pomyślcie o przestrzeni wszystkich możliwych n. Jeśli n równa się 100, to przestrzeń – od dwóch do stu. Nasz algorytm przeszukuje tę przestrzeń. Myślcie o algorytmie, który przeszukuje. W każdym punkcie pyta… Potraktujcie to jako krok. Podstawowy. Algorytm pyta… to jest pytanie o złożoność n. Jesteśmy przy liczbie a. W metodzie próbnych dzieleń spytamy: „Czy n dzieli się przez a?”. Próbujemy. Wrzucamy a, próbujemy podzielić przez nie n, patrzymy, czy reszta wynosi zero, co oznacza, że a jest dzielnikiem n. I mówimy: „Tak, wiemy na 100%”. Wiemy na pewno, że ta liczba jest złożona. Inaczej, przy każdym z kroków, nie mamy całkowitej pewności. Liczba może być pierwsza. Kontynuujemy szukanie do końca. Pamiętacie, że w tym przypadku granicą był pierwiastek z n. Najgorzej jest wtedy, gdy n jest liczbą pierwszą, a my szukamy aż do pierwiastka z n i dopiero wtedy powiemy: „Pierwsza. Wiemy to na 100%”. W razie, gdy n jest iloczynem dwóch liczb pierwszych, 7 razy 7 równa się 49, jeśli wrzucimy 49 w nasz algorytm, będzie to najgorszy przypadek. Dojdziemy aż do pierwiastka kwadratowego z n. Pierwsze komentarze… Np. użytkownik TheFourthDimension pyta: „Kiedy wykluczymy 2, jako niepodzielne, można wykluczyć wszystkie wielokrotności 2, i 3, 4, 5 itd.”. Świetne spostrzeżenie. Stary algorytm posuwał się po kolei, ale możemy wykorzystywać wzory związane z liczbami złożonymi. Np. wiemy na pewno, że jeśli liczba jest podzielna przez 2, to jest złożona. Większa od 2, bo 2 to liczba pierwsza. Powiemy: „4 to liczba złożona”. Nie wpisałem 5, przepraszam. 4, 6, 8… 10. Zamiast tego możemy zrobić taki krok. 3, 5, 7, 9… Jedna kategoria pytań to te starające się ograniczyć przestrzeń. Jeśli wyeliminujemy wszystkie liczby parzyste, to przestrzeń sprawdzania nie sięga pierwiastka z n, tylko pierwiastka z n podzielonego przez 2. Znajdziemy inne schematy dotyczące liczb złożonych, żeby zmniejszyć to jeszcze bardziej. Inny typ pytań… dotyczy przypadku, gdy znajdujemy świadka złożoności. Takie a, które pozwoli powiedzieć: „Wiemy, że n jest liczbą złożoną”. Lola napisała: „Czy wyjście z pętli gdy test pierwszości równa się FAŁSZ oszczędziłoby czas?”. Tak, zgadza się, i tego właśnie chcemy. Kiedy szukamy krokami określonymi w wybranym schemacie, znajdujemy świadka złożoności. Przechodzi test i mamy stuprocentową pewność, że możemy przerwać wcześniej. Zatrzymujemy się. „Gotowe. Dalej nie szukamy”. To wcześniejsze zatrzymanie jest świetne, tylko nie pomaga w najgorszym przypadku, czyli kiedy n jest liczbą pierwszą. Wtedy nie da się przerwać wcześniej. Zobaczmy, jak te ulepszenia pozwalają nam zmniejszyć przestrzeń, ograniczając liczbę testów wewnątrz komputera. To, zależnie od komputera, skróci cały proces. Mogę wam pokazać wizualizację, którą przygotowałem. Pozwoli ona porównać dwa algorytmy w oparciu o to, ile kroków wymaga ich wykonanie. Po lewej mamy algorytm A, metodę próbnych dzieleń, sprawdzanie od dwóch do pierwiastka kwadratowego z n. Po prawej jest algorytm B, nasz algorytm ulepszony. W tym przypadku zastosowałem test podzielności przez 2, więc kroków wykonujemy już tylko połowę. W algorytmie B także wcześniej kończę. Nie jest doskonały. Wprowadziłem parę sugestii użytkowników, zobaczymy, co będzie. Uruchomię to, żebyście zobaczyli. Kiedy przesuwam, widzimy algorytm A. Mamy wynik: liczba złożona czy pierwsza. Zaś na dole widzicie liczbę kroków. Zauważcie: po prawej stronie, co druga liczba zajmuje tylko jeden krok. Wiemy, dlaczego. Bo jeśli to liczba parzysta, jak ta, to program się zatrzyma. Nasz stary algorytm potrzebował 314 kroków. Nowy algorytm – tylko jednego, bo sprawdza, czy liczba dzieli się przez 2. Przyjemna optymalizacja! Ale gdy będziemy zwiększać dane wejściowe, zobaczycie, że liczba kroków rośnie, prostokąt powiększa się i staje się czerwony. W miarę zbliżania się do regionu, gdzie program się załamie. Czerwona linia to granica. Jeśli prostokąt tu sięgnie, to nam się nie uda. Łazik się zepsuje. W naszym przypadku padnie przeglądarka. Spróbuję się zbliżyć. Jestem blisko i program działa bardzo wolno. Czuję, że moja przeglądarka zaraz się posypie. Zauważcie, że ulepszony algorytm potrzebował tylko dwóch kroków. Pamiętajcie o najgorszym przypadku. Mam parę dużych liczb pierwszych zapisanych dla przykładu. Musimy sobie radzić z każdym przypadkiem. Nie wiadomo, co się trafi. Jeśli wrzucę dużą liczbę pierwszą, patrzcie, co będzie. Algorytm B, jak wiemy potrzebuje połowy kroków w najgorszym przypadku, ale i tak wykonuje wiele kroków tutaj. Bo to najgorszy przypadek. Zbliżamy się do katastrofy, a to nie jest bardzo długa liczba. Znacznie poniżej 15 cyfr. Gdy wprowadzą tę 12-cyfrową liczbę pierwszą do naszego algorytmu, zobaczmy, co będzie… Zwalnia, może się zatrzyma. Patrzcie: oba algorytmy przekroczyły granicę. Nie udało się. Nasz ulepszony algorytm nie jest jeszcze dość dobry. Ale teraz rozumiemy, co staramy się ulepszyć: liczbę kroków w najgorszym przypadku. I mamy też świetne narzędzie, które pozwala wizualizować, jak szybko to rośnie w miarę wzrostu rozmiaru danych wejściowych. Poniżej wyjaśnię, jak to zrobiłem, żebyście mogli ułożyć własny algorytm. I porównać z naszym przykładem. Może dacie radę lepiej.