Eksperyment z losowymi ciągami

2011-09-06 20:51

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 A=\{a_1, \ldots, a_n\} dowolnych elementów a_i oraz liczbę naturalną k \in N.
  • Szukamy ciągu S=<s_1, \ldots, s_k> k elementów s_i \in A.

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:

  1. import random
  2.  
  3. def k_permutation(elems, k=None):
  4.     k = k or len(elems)
  5.     res = []
  6.     while k > len(res):
  7.         next = elems[random.randrange(0, len(elems)]
  8.         res.append(next)
  9.     return res

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:

  1. def k_permutations_bignum(elems, k=None):
  2.     k = k or len(elems)
  3.     max_seq_num = len(elems) ** k
  4.     seq_num = random.randrange(0, max_seq_num) # (zob. 3. komentarz)
  5.     res = []
  6.     while seq_num > 0:
  7.         seq_num, next = divmod(seq_num, len(elems))
  8.         res.append(elems[next])
  9.     return res

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:

  1. >> import cProfile, string
  2. >> cProfile.run('k_permutations_bignum(string.digits, 10000)')
  3.    30008 function calls in 0.292 CPU seconds
  4.  
  5.    Ordered by: standard name
  6.  
  7.    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  8.         1    0.045    0.045    0.292    0.292 <pyshell#5>:1(k_permutations_bignum)
  9.         1    0.000    0.000    0.292    0.292 <string>:1(<module>)
  10.         1    0.000    0.000    0.000    0.000 random.py:173(randrange)
  11.         1    0.000    0.000    0.000    0.000 random.py:243(_randbelow)
  12.     10000    0.224    0.000    0.224    0.000 {divmod}
  13.     10001    0.011    0.000    0.011    0.000 {len}
  14.         1    0.000    0.000    0.000    0.000 {math.log}
  15.     10000    0.011    0.000    0.011    0.000 {method 'append' of 'list' objects}
  16.         1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
  17.         1    0.000    0.000    0.000    0.000 {method 'getrandbits' of '_random.Random' objects}

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 ;)

Tags: , , , ,
Author: Xion, posted under Math, Programming »


4 comments for post “Eksperyment z losowymi ciągami”.
  1. Kokos:
    September 6th, 2011 o 23:48

    Czy w drugim kodzie elems nie powinno być użyte do czegoś poza sprawdzeniem długości?

  2. Xion:
    September 7th, 2011 o 0:15

    Słusznie – brakowało elems[...] w linijce z res.append. Brawa za czujność :)

  3. Michał Komorowski:
    September 9th, 2011 o 14:16

    Fajny pomysł ale moim zdaniem zawiera niewielki błąd. Uruchomiłem Twój kod w taki sposób:

    input = range(10)
    for x in range(1000):
    res = k_permutations_bignum(input,3)
    if len(res) < 3: print res;[/code] I jako wynik otrzymałem oprócz zbiorów 3 elementowych zbiory 1 i 2 elementowe. Łatwo to naprawić: [code] def k_permutations_bignum(elems, k=None): k = k or len(elems) min_seq_num = len(elems) ** (k-1) max_seq_num = len(elems) ** k seq_num = random.randrange(min_seq_num, max_seq_num) … [/code] W ten sposób mamy zagwarantowane, że uda nam się podzielić ‘seq_num’ przez ‘len(elems)’ dokładnie ‘k’ razy.

  4. Xion:
    September 9th, 2011 o 16:16

    Fakt! Liczby mniejsze od len(elems) ** (k-1) są jakby ciągami mającymi “zera” na początku (tj. symbole nie odpowiadające żadnym elementom), więc odpowiadające im zbiory mają mniej niż k elementów.

    Dodałem odpowiednią uwagę odsyłającą do twojego komentarza.

Comments are disabled.
 


© 2017 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.