Eksperyment z losowymi ciągami

Zdarzyło się dzisiaj, że musiałem zaimplementować rozwiązanie wyjątkowo klasycznego problemu. Siląc się matematyczny formalizm, mógłbym go zdefiniować następująco:

• Mamy dany zbiór dowolnych elementów oraz liczbę naturalną .
• Szukamy ciągu k elementów .

Krótko mówiąc, chodzi o trywialną wariację z powtórzeniami. Ambitne to zadanie jest w sumie nawet mniej skomplikowane niż częste ćwiczenie dla początkujących pt. losowanie Lotto, więc po chwili wyprodukowałem coś podobnego do kodu poniżej:

I na tym pewnie historia by się zakończyła, gdybym nie przypomniał sobie, że Python domyślnie potrafi obsługiwać naprawdę duże liczby. (Może nie aż tak duże jak te tutaj, ale jednak dość spore ;]). Obserwacja ta daje się bowiem połączyć z inną: taką, iż ciąg elementów z pewnego zbioru jest równoważny liczbie w systemie o podstawie równej mocy tego zbioru. Taka liczba jest oczywiście bardzo duża w prawie każdym praktycznym przypadku, lecz to nie umniejsza w niczym prawdziwości stwierdzenia. Jest ono zresztą z powodzeniem wykorzystywane w systemach kryptograficznych w rodzaju RSA.

Postanowiłem więc i ja z niego skorzystać. Przynajmniej teoretycznie fakt ten powinien dawać lepsze rezultaty, zamieniając k losowań na tylko jedno – tak jak poniżej:

Doświadczenie z kolei uczyłoby, że bezpośrednie aplikowanie dziwnych matematycznych koncepcji do programowania rzadko miewa dobre skutki ;) Jak więc jest w tym przypadku?…

Okazało się mianowicie, że dla krótkich ciągów oba rozwiązania są porównywalne. Dla długości rzędu maksymalnie tysiąca lub kilku tysięcy czas generowania łańcucha cyfr przy pomocy którejkolwiek metody jest podobnie niezauważalny. Dopiero później zaczynają występować rozbieżności i metoda z “wielką liczbą” ostatecznie przegrywa – ale chyba nie w sposób, którego byśmy się spodziewali.

To powinno być oczywiste, ale warto zaznaczyć, że poniższe logi mają niejawną pieczątkę Works on My Machine: powtórzenie eksperymentu na innym komputerze, systemie, implementacji Pythona i szerokości geograficznej może dać inne rezultaty bezwzględne. Względne zależności powinny być jednak zbliżone.

Intuicja być może podpowiada nam, że w k_permutations_bignum kosztownymi operacjami są obliczenie max_seq_num oraz wylosowanie seq_num, czyli owej “wielkiej liczby” reprezentującej wynikowy ciąg elementów. Gdy to zostanie zrobione, to w zasadzie mamy już wynik; jedyne co nam pozostaje, to przekształcić go do pożądanej postaci listy.
Jak te przewidywania mają się do wyników zwracanych przez profiler? Właściwie to nijak:

Samo losowanie jest kompletnie niezauważalne, zaś potęgowanie w celu obliczenia max_seq_num zajmuje w najlepszym razie kilkanaście procent czasu całej funkcji. (Jest to różnica czasu całkowitego i sumy wszystkich pozostałych). Czysto teoretyczna, matematyczna metoda sprawdzałaby się więc świetnie w praktyce, gdybyśmy tylko nie musieli na sam koniec dokonywać konwersji rezultatu do użytecznej postaci. Jak bowiem widać po udziale funkcji divmod, to ona zajmuje lwią część czasu.

Z tego skromnego eksperymentu można wywieść ogólny wniosek odnoszący się do całej w zasadzie algorytmiki. Otóż reprezentacja danych ma tak duże znaczenie, że wybór odpowiedniej stanowi często o tym, czy dane rozwiązanie jest świetne wydajnościowo czy całkowicie do kitu. Z drugiej strony powoduje to, że konwersja między różnymi reprezentacjami jest prawie zawsze na tyle kosztowna, że nie opłaca się jej przeprowadzać – nawet jeśli wykonanie jakiejś operacji na danych w innej postaci byłoby znacznie bardziej efektywne.

Lecz tak jak od większości reguł, tak i od tej są oczywiście wyjątki. Jak jednak widać powyżej, generowanie losowych ciągów za pomocą wielkich liczb nie jest jednym z nich ;)

Be Sociable, Share!

• 
• 

Be Sociable, Share!

• 
• 

• Tweet
•