poniedziałek, 28 marca 2011

Obiecałem niedawno napisać więcej na temat programów do ... przewidywania przyszłości ... no to do dzieła - jednym z przykładów takich programów był ten zlecony ostatnio przez pewnego zapalonego gracza mulitlotka, nie pierwszy i nie ostatni bo wszystkie te programy łączy jedno założenie - otóż w jakiś sposób z tego że w poprzednich losowaniach padły (lub nie padły dane liczby) ma wynikać to czy te (lub inne) liczby zostaną wylosowane w przyszłości ...
Z założeniem tym fundamentalnie się nie zgadzam bo w swojej naiwności wierzę że losowania państwowego monopolisty są prowadzone uczciwie w sposób ... losowy ... Gdyby jednak uznać że losowania te są elementem jakiejś manipulacji to być może rozumowanie takie ma sens. Tyle wstępu przejdźmy do omówienia tego konkretnego zlecenia:  

Zamawiający oczekiwał ode mnie rzeczy które z początku wydawały mi się niewykonalne - zastanawiałem się nad tym jak napisać program który by szybko i sprawnie porównywał dwa gigantyczne zbiory liczb...
Naprawdę szybko no bo jak inaczej  sprawdzić wystąpienia wszystkich kombinacji 7 elementowych ze zbioru 80 elementowego w (UWAGA!) całej historii losowań multilotka - można to na szybko policzyć: 

Symbol Newtona (n/k) = n!/(n-k)! do tego pomnożony przez ilość losowań co w tym przypadku wyniesie 16010650656000 razy kilkanaście tysięcy  - na pierwszy rzut oka rzecz jest niewykonalna - a jednak udało  się to zrobić w czasie który jest do zaakceptowania dla mojego klienta!

Oczywiście możliwa jest metoda bruteforce - można sprawdzać po kolei każdą z liczb z pierwszego zbioru i szukać jej w drugim zbiorze,  ale przy tych ilościach kombinacji zajęło by to lata - skala problemu wymusza na programiście stworzenie naprawdę szybkiego algorytmu porównującego...

Przedstawię tu ten algorytm pomijając jednak system przygotowania danych, napiszę tylko że trzeba zapisać każdą możliwą kombinację jako trzy 32 bitowe liczby całkowite - unsigned int - wstawiając jedynki w tych bitach których numery porządkowe odpowiadają liczbom występującym w danej kolejności i tak dla przykładu - jeżeli mamy np kombinację liczb 1.2.3.5.6.8.9 to reprezentuje je zestaw liczb 0000 0000 0000 0000 0000 0000 0000 0000,0000 0000 0000 0000 0000 0000 0000 0000,0000 0000 0000 0000 0000 0001 1011 0111 czyli po ludzku 0,0,439...

Mając tak przygotowane dane wejściowe (algorytm tworzący je udostępnię jeżeli będzie zainteresowanie) te które sprawdzamy (wszystkie możliwe kombinacje 7 elementowe)   wyniki losowań które rzeczywiście wystąpiły w historii do stwierdzenia które kombinacje 7 elementowe wystąpiły w historycznych losowanich  wystarczy już tylko sprawdzenie iloczynu binarnego (powiedzmy że a to kolejne możliwe kombinacje 7 elementowe a b to wyniki losowań)  liczb a i b. 




Jeżeli wynik iloczynu jest równy a to oznacza że dana kombinacja wystąpiła w danym losowaniu .... Tylko po co to wszystko ? No oczywiście po to by znaleźć kombinacje "gorące" - czyli takie które "lubią" występować razem - tak więc przyjmujemy że jeżeli nasza kombinacja 1.2.3.5.6.8.9  występowała w historii zdecydowanie częściej niż inne równoważne - to ta kombinacja jest w jakiś sposób "forowana" przez system i należy ją obstawiać bo dalej będzie występować zdecydowanie częściej niż inne kombinacje ... ;)

Co o tym myślicie ?   

1 komentarz:

  1. Również fajnie zacząłeś, ale musisz wrócić do blogowania ;) chyba, że masz coś świeżego.

    OdpowiedzUsuń