Generování k-kombinací a porovnání s historickými daty

[johnsmithx]

Dobrý den,

úvodem bych chtěl poděkovat za velmi vydařený a kvalitně zpracovaný software.

Dále bych se chtěl zeptat, zda by tento program uměl vygenerovat a porovnat všechny k-kombinace (6-kombince = všechny možné kombinace 6 čísel od 1 do 49, 10-kombinace = všechny kombinace 10 čísel od 1 do 49, apod.; 'k' v rozsahu od 6 do 15 stejně jako momentální možnosti normální a systémové sázky ve Sportce) vůči historickým datům a pro každou testovanou kombinaci vypočítat, jak často nastala shoda ve 4, 5 a 6 číslech (dodatkové číslo může být ignorováno) a nakonec ukázat x "nejlepších" kombinací s nejvyšším procentem shody.

Pokud to momentálně neumí (asi ne, ale podrobně ho neznám, tak nechci předjímat), jak by bylo pro vás složité to naprogramovat?

Děkuji za odpověď.

johnsmithx

[Aubrecht]

jista oklika je vytvorit loterii 10/53 a vylosovana cisla nacist napriklad ze sportky doplnena o cisla 50.51,52 a 53 na poslednich ctyrech pozicich

zkusim prozkoumat, jak bylo pracne podporovat loterie, kde se sazi vice cisel, nez se losuje...

[johnsmithx]

jista oklika je vytvorit loterii 10/53 a vylosovana cisla nacist napriklad ze sportky doplnena o cisla 50.51,52 a 53 na poslednich ctyrech pozicich

zkusim prozkoumat, jak bylo pracne podporovat loterie, kde se sazi vice cisel, nez se losuje...

Tak ono systémová sázka není ani novinkou ani nějakým českým specifikem. Existuje již řadu let v řadě loterií. Vím, že podobný postup (vytvoření fiktivní větší loterie) jste zde jako určité nouzové řešení již jednou radil, avšak dovolím si při vší úctě oponovat, že toto by řešením nebylo.

Jednak celkový počet prvků množiny, ze které se generují kombinace, má zůstat stále stejný - 49. Jediné, co potřebujeme, je negenerovat kombinace složené ze 6 čísel dané množiny, ale ze 7 čísel, nebo 8 čísel, až z 15 čísel. A každou takto vytvořenou kombinaci porovnat vůči již proběhlým losováním (tj. vůči 6-kombinacím) a vyhodnotit kolik čísel se pro každou námi vygenerovanou kombinaci shoduje s realitou - historií. Mimochodem, když už bychom byli v tom porovnávání, stálo by rovněž za uvážení při té příležitosti provádět i určitou jednoduchou časovou analýzu těch shod. Například kombinace 15 čísel, která by při porovnání s historií představovala 20% pravděpodobnost shody v alespoň 4 číslech, může na první pohled vypadat zajímavě. Avšak jen do té doby, než zjistíme, že značná část těch shod proběhla spíše hlouběji v minulosti a v poslední době to zas taková sláva už nebyla. Naproti tomu například u kombinace, která by představovala "jen" 15% šanci, avšak relativně rovnoměrně průběžně za posledních x desítek let, by nebylo zcela nesmyslné očekávat, že tento trend průběžného výskytu zrovna dnes z ničeho nic neskončí, ale bude pokračovat i dále do budoucnosti.

No a jednak by to nešlo proto, protože pokud byste měl generovat všechny ty kombinace nejdříve do paměti a teprve potom s nimi pracovat (takto se mi jeví, že ExpertLotto v současné době funguje; ale mohu se mýlit), tak kupříkladu pro všechny 15-kombinace, kterých je 1,575,580,702,584, byste za předpokladu, že pro jedno číslo vyhradíme jen 1 bajt, potřeboval téměř 1,5 TB paměti, což nemá k dispozici ani ten v současné době nejvýkonnější superpočítač na světě ("K computer", který se skládá z 88128 jednotek, každá s 16 GB paměti). I kdyby takovou kapacitu měl každý ve svém obýváku, tak by generování, nebo "předgenerování", všech možných kombinací do paměti nemělo smysl. Pokud totiž ty kombinace nevytváříte náhodně, ale určitým algoritmem (což musíte tak jako tak, abyste zajistil, že se žádná kombinace nebude opakovat), tak každá kombinace má své pořadové číslo a není problémem ji kdykoliv z tohoto sekvenčního čísla vygenerovat znovu.

Tedy řešením, nikoliv principiálně složitým, je dle zadaných parametrů generovat kombinace systémové sázky, porovnávat je vůči historickým datům a zaznamenávat si pouze x "nejzajímavějších". Mezi volitelné parametry by rovněž mohla být možnost specifikace čísel, která musí být vždy v testované kombinace obsažena ("šťastná čísla"), a naopak čísel, která v testované kombinace být obsažena nesmí (užitečné kupříkladu při vytváření komplementárních systémových sázek apod.). Já jsem například tyto funkce řešil formou whitelistingu a blacklistingu.

Odpověď na otázku, zda výše naznačené by bylo možné do ExpertLotto naimplementovat, by jistě zajímala více lidí.

Děkuji.

[Aubrecht]

vsechny generovane kombinace se ukladaji do souboru na disk, v operacni pameti se drzi pouze aktualne zpracovavana davka tipu (obvykle nekolik tisic tipu, dle nastaveni loterie).
pokud byste chtel porovnavat vsechny mozne kombinace 15 cisel z osudi 49, budete potrebovat hodne rychly pocitac nebo hodne trpelivosti (nebo nejlepe oboji:) kombinace 10 a mene cisel budou asi pouzitelnejsi.

i v loterii 10/53 je samozrejme mozne generovat kombinace 10 cisel z osudi pouze 49. neni to sice prilis pohodlne, ale muzete si tak overit, jaka shoda se da najit s vylosovanymi cisly sportky.

jak jsem uz uvedl, zkusim program upravit tak, aby podporoval i systemove sazky. nejedna se ale o trivialni zmenu, takze to nebude hned...

[johnsmithx]

Ukládat kombinace na disk je ještě horší než je držet v paměti. Doba potřebná pro načtení dat z disku je o několik řádů delší než prosté znovu-vygenerování požadované kombinace nebo série kombinací.

Během těch 4 dnů, než jste na můj dotaz odpověděl, jsem celý problém naprogramoval. Vygenerování všech 15-kombinací, kterých je celkem 1,575,580,702,584 (1,5 biliónu), není nikterak obtížné ani zdlouhavé, dokáži je generovat rychlostí zhruba 1,000,000,000/s (miliarda kombinací za sekundu). Každá další instrukce smyčku samozřejmě zpomaluje, ke zpracování matching algoritmem se dostávají už jen rychlostí 90 miliónů /s a podle toho, s kolika historickými losováními je porovnávám, se pak celková rychlost snižuje na milióny (porovnání s 100-1000 historickými losováními), statisíce až na 50 tisíc za sekundu v případě porovnání s 5336 losováními (losování za posledních 35 let). Toto vše je však rychlost při použití pouze jednoho jediného jádra jednoho CPU (v tomto případě 3,15 GHz) jednoho počítače. Při použití například 4 jader u quadcore CPU se rychlost lineárně zvyšuje 4 násobně, přičemž lze použít libovolné množství různě rychlých jader, procesorů a dokonce i zcela samostatných počítačů. Navíc výkon lze pravděpodobně ještě znatelně zvýšit další optimalizací kódu.
Tedy když to celé dám do kontextu, tak porovnání všech možných 15-kombinací z čísel 1 až 49 vůči losováním za posledních 35 let a vyhodnocení kombinací s nejvyšší úspěšností (mimochodem někteří jsou názoru, že zajímavé mohou být i kombinace s naopak nejnižší úspěšností v minulosti dle teorie, že stejná kombinace se v blízké budoucnosti nebude opakovat) shody 4 a více číslic dokáži provést na třech 4jádrových procesorech do jednoho jediného měsíce. To není zase taková tragédie, navíc je ještě mnoho prostoru k optimalizaci. Nemám ale ještě onu časovou analýzu, kterou jsem zmiňoval v minulém příspěvku.

Výsledky v praxi jsou docela zajímavé a ne zcela kopírují teorii. Na matematickém fóru mi chytří lidé pomohli vypočítat, že podle vzorců by pravděpodobnost 15-kombinace pro shodu 4 a více čísel vůči libovolnému losování Sportky byla zhruba 0,5% (pro každý ze dvou tahů). To by se za cenu 80 tisíc Kč asi nemusel vyplatit. Ve skutečnosti lze ale najít i obyčejnou 6-kombinaci, která při porovnání s historií dosahovala téměř takovou šanci (např. 0.4121%: 5, 18, 21, 25, 26, 48; 22x 4, 0x 5, 0x 6). U 8-kombinací již jde o 1%, 10-kombinace přesahují 2 procenta, 12-kombinace přesahují 4 procenta, 15-kombinace jsem zatím zkoušel jen velmi zběžně, ale i tak už mám např. kombinaci, která dosahuje 8% úspěšnosti. Dokud si někdo nedá práci generovat a porovnávat miliardy až bilióny kombinací s výsledky tisíců proběhlých losování, tak takováto čísla nemá šanci se vůbec dozvědět.

Takže z programátorského hlediska to žádný velký problém není, samozřejmě výkon u "klikacích" high-level jazyků je ve srovnání s technickým assemblerem optimalizovaným pro core2/sse2/ssse3 pravděpodobně někde jinde. Nedovedu nijak posoudit užitečnost těchto funkcí, o strategiích v loteriích nic nevím, jsem programátor, ale když se podívám, jaké některé poněkud iracionální funkce v současných loterijních softwarech existují - a lidé takovéto funkce využívají, pak v tomto kontextu jde jistě o funkce neméně užitečné

Přeji hodně úspěchů v implementaci v ExpertLotto.

[Aubrecht]

Ukládat kombinace na disk je ještě horší než je držet v paměti. Doba potřebná pro načtení dat z disku je o několik řádů delší než prosté znovu-vygenerování požadované kombinace nebo série kombinací.

Během těch 4 dnů, než jste na můj dotaz odpověděl, jsem celý problém naprogramoval. Vygenerování všech 15-kombinací, kterých je celkem 1,575,580,702,584 (1,5 biliónu), není nikterak obtížné ani zdlouhavé, dokáži je generovat rychlostí zhruba 1,000,000,000/s (miliarda kombinací za sekundu). Každá další instrukce smyčku samozřejmě zpomaluje, ke zpracování matching algoritmem se dostávají už jen rychlostí 90 miliónů /s a podle toho, s kolika historickými losováními je porovnávám, se pak celková rychlost snižuje na milióny (porovnání s 100-1000 historickými losováními), statisíce až na 50 tisíc za sekundu v případě porovnání s 5336 losováními (losování za posledních 35 let). Toto vše je však rychlost při použití pouze jednoho jediného jádra jednoho CPU (v tomto případě 3,15 GHz) jednoho počítače. Při použití například 4 jader u quadcore CPU se rychlost lineárně zvyšuje 4 násobně, přičemž lze použít libovolné množství různě rychlých jader, procesorů a dokonce i zcela samostatných počítačů. Navíc výkon lze pravděpodobně ještě znatelně zvýšit další optimalizací kódu.
Tedy když to celé dám do kontextu, tak porovnání všech možných 15-kombinací z čísel 1 až 49 vůči losováním za posledních 35 let a vyhodnocení kombinací s nejvyšší úspěšností (mimochodem někteří jsou názoru, že zajímavé mohou být i kombinace s naopak nejnižší úspěšností v minulosti dle teorie, že stejná kombinace se v blízké budoucnosti nebude opakovat) shody 4 a více číslic dokáži provést na třech 4jádrových procesorech do jednoho jediného měsíce.

myslim, ze to je hodne optimisticky predpoklad:)
co vlastne ocekavate, ze bude vystupem porovnavani? seznam vsech kombinaci 15 cisel a mira jejich shody s predchozimi tahy? nebo X nejlepsich/nejhorsich kombinaci?

[Aubrecht]

mimochodem, pokud jste taky programator, jak pisete v predchozim prispevku, muzete si do programu expert lotto napsat vlastni funkce. API programu je otevrene pro libovolne rozsireni funkci...

[johnsmithx]

mimochodem, pokud jste taky programator, jak pisete v predchozim prispevku

Žlutá karta.

muzete si do programu expert lotto napsat vlastni funkce. API programu je otevrene pro libovolne rozsireni funkci...

Já jsem skutečně ten program nezkoumal, navíc Java, kterou používáte, není jazyk zaměřený na výkon, což ani zřejmě nebyla vaše priorita (proč ale ve win7 64bit ten program běží ve 32bit režimu, to mi jasné není). Jednoduše mne napadlo (jako programátora mne neustále napadají různé nesmysly k řešení, jakobych neměl své práce dost), že bych chtěl znát, jaká by byla reálná procenta shody pro nejlepší x-kombinace a hledal jsem odpověď. Našel jsem ExpertLotto, ten se bohužel systémovými sázkami vůbec nezabýval, nějaké pochybné jiné programy jsem zkoušet nechtěl, tak jsem si to naprogramoval sám. Jsem programátorem přes 25 let, z toho mj. 22 let v assembleru několika odlišných architektur, z programátorského hlediska toto žádná výzva nebyla, snad jen ta výkonnostní optimalizace, aby to bylo nějak reálně použitelné. Naštěstí jsem zrovna v té době vymýšlel optimalizovaný srovnávací algoritmus, který dokáže zjistit míru shody ze dvou skupin čísel, aniž by cokoliv s čímkoliv porovnal (docela vtipné, přitom ale geniálně jednoduché). Bezesporu by to mnoho lidí naprogramovalo lépe. Nejdříve jsem se zeptal na matematickém fóru, jak by se vůbec vypočítala teoretická pravděpodobnost, protože takové výpočty jsem se učil ještě v době normalizace a nikdy v životě jsem je aplikovat nepotřeboval. Pak, když jsem implementoval blacklist/whitelist, jsem se tam zeptal znovu, podle jakého vzorce bych vypočítal celkové množství kombinací v takovém kontextu (taky docela vtipné - kolik bude kupříkladu všech možných 15-kombinací, ve kterých se 2 zadaná čísla nebudou vyskytovat nikdy a naopak 3 jiná zadaná čísla se tam budou vyskytovat vždy? odpověď je 21090682613), ale než mi tam někdo stihl poradit s tímto, tak jsem si vzorec odvodil sám. Koneckonců jde o veřejná fóra, stačí napsat dvě slova v Googlu a správný link máte hned v prvním místě.

co vlastne ocekavate, ze bude vystupem porovnavani? seznam vsech kombinaci 15 cisel a mira jejich shody s predchozimi tahy? nebo X nejlepsich/nejhorsich kombinaci?

No původně jsem jako výstup naprogramoval "3 best", ale po svém předchozím příspěvku jsem to zobecnil na "x best/worst".

myslim, ze to je hodne optimisticky predpoklad:)

O jakém "předpokladu" to mluvíte? Uvedl jsem zcela jasná a konkrétní čísla z praxe, nikoliv nějaké teoretické "předpoklady". Přeci i školák na základní škole dokáže vypočítat, že pokud něco pracuje rychlostí 50000 kombinací za sekundu na jediném jádru jediného procesoru, pak na třech 4jádrových procesorech to zpracuje 1575580702584 kombinací za 30,39 dní. Nebo mi snad chcete tvrdit, že můj program, o kterém nevíte ani ň, znáte lépe než já, který ho naprogramoval? Koneckonců opět by stačilo jen vygooglovat, na jednom zahraničním fóru jsem ukázal výstupy z tohoto programu. Vám ale jde zřejmě o něco úplně jiného.

Druhá urážka během 2 příspěvků. Toto už není náhoda, to nebyla rozumná reakce rozumného člověka. Tedy dostáváte červenou kartu.

Pokud mi něco připadá složité a potkám člověka, který to bez problémů udělal během několika dní, tak se přeci logicky a pokorně snažím něco přiučit. Ale jsem asi moc zvyklý na zahraniční prostředí a uvažování, ne na čechy, kteří v hospodě dělají machry, ale pak se ohnou, zavřou hubu a snaží se vymyslet, jak co nejlépe zneužít systém, aby měli co nejvíce muziky za co nejméně peněz, a to celé protkané permanentní závistí a nepřejícností ke komukoliv, kdo se zmohl na víc. Pokud šlo o rádoby shovívavý, z výšky pronesený a smajlíkem okořeněný ubohý projev takovéto typické české malosti (když to neumím já, tak to nesmí umět ani on a pokud on to umí, tak ho alespoň urazím, zesměšním a zpochybním, abych ulevil svému nepodloženě zbytnělému egu), tak jste se jen sám zesměšnil. Kdyby jste se takto neprojevil, tak jsem vám mohl poradit s implementací. Já totiž nemám zapotřebí se snažit na každé ptákovině, kterou naprogramuji, vydělat peníze. Nebo bylo možná cílem toho záměrného a opakovaného hulvátství vyprovokovat tuto mou reakci, abyste měl důvod celé vlákno "s klidným svědomím" smazat. V každém případě hodně štěstí s vašimi "netriviálními" změnami, už zde nic psát ani číst nebudu.


P.S.: zde je výstup z programu včetně aktuální rychlosti a z ní vypočítané doby pro zpracování 1% ze všech 15-kombinací. Momentální rychlost 49 tisíc kombinací za sekundu, celkový čas 3,71 dní (3 dny 17 hodin). Program se naváže vždy a pouze na jediné jádro. Lze spustit libovolné množství instancí programu (na stejném počítači nebo na libovolném množství nezávislých i výkonově odlišných počítačů), každou zpracovávající jinou část (jiný start a stop parametr) celého běhu. Více souběžných instancí nezpůsobuje naprosto žádný overhead (režii), protože mezi sebou nijak nekomunikují ani nic nesdílí. Běží mi to již několik dní, abych viděl naprosto prokazatelně, že výkon na x jádrech je zcela a přesně x násobek rychlosti na jednom jádru. I malé dítě si tedy dokáže vypočítat, že pokud za 3,71 dní je zpracováno 1%, pak 100% je zpracováno za 371 dní, na 4 jádrech to činí 92,75 dní a na třech 4jádrových procesorech to znamená 30,92 dní. Mezi mými počítači se minimálně tři počítače nachází, které mají 4jádrové procesory o stejné nebo vyšší frekvenci. Proto jsem jasně napsal, že zpracování všech 1,5 biliónu 15-kombinací dokáži provést do jednoho jediného měsíce a můžete si klidně "myslet" až do aleluja, že to je optimistický "předpoklad". Pane, jste namyšlený samolibý hlupák.

Kód: Vybrat vše

root@ubuntu:/home/johnsmithx/sportka# ./lotto lotto_data_5336_1977w1-2011w39.csv lotto_blacklist.csv lotto_whitelist.csv 15 0.01 0 1
Lotto ver. 1.1
==============

Input data statistics: datafile 5336 rows, blacklistfile 0 numbers, whitelistfile 0 numbers
Requested 15-combinations of 1 - 49: 1575580702584 combinations to compute, 1575580702584 combinations to test
   parameters: start 0.00% stop 1.00% pfreq 0.01% benchmark 10 s

START COMPUTING at 0.00%  (2011-11-22 23:43:41 +0000)
 benchmarking: computed combination no. 500000 (50000/s), tested combination no. 500000 (50000/s)
               elapsed: 10 s, remaining: 3 d 15 h 31 m 46 s  (2011-11-22 23:43:51 +0000)

Progress 0.01%, computed combination no. 157558071 (49098/s), tested combination no. 157558071 (49098/s)
elapsed: 53 m 29 s, remaining: 3 d 16 h 14 m 50 s  (2011-11-23 00:37:10 +0000)
...1st comb: 1, 4, 5, 7, 9, 11, 13, 15, 17, 21, 22, 24, 26, 29, 49 prob: 7.7399% (368x 4, 43x 5, 2x 6)
...2nd comb: 2, 3, 6, 7, 8, 9, 10, 12, 14, 15, 20, 25, 26, 29, 49 prob: 7.7211% (378x 4, 34x 5, 0x 6)
...3rd comb: 4, 5, 6, 9, 11, 13, 15, 17, 20, 21, 22, 26, 27, 29, 49 prob: 7.7024% (368x 4, 41x 5, 2x 6)


P.S.2: zde je test několika algoritmů pro generování kombinací, které jsem se trochu snažil optimalizovat. Opět samozřejmě výkon na jednom jediném jádře a opět na x jádrech a n počítačích bude výkon násobkem x * n. Ten první je ten nejprimitivnější, pro generování kombinací v lexikografickém pořadí, ten s největší pravděpodobností používáte vy, avšak samozřejmě s neporovnatelně nižší rychlostí. O nějakých stovkách miliónů kombinací za sekundu si s tou vaší Javou můžete nechat leda jen zdát, a to navíc jen v těch nejhlubších snech. Já používám ten 4. algoritmus, od Lama, který jej mimochodem publikoval již v roce 1982.
Jak řekl Einstein: "jen 2 věci jsou nekonečné - vesmír a lidská hloupost, a o tom prvním si nejsem jistý".

Kód: Vybrat vše

root@ubuntu:/home/johnsmithx/lotto# ./test_algorithms 49 9
Combinations of 49 taken 9 at a time

lexicon combs: 2054455634, time: 8 s, 256806954/s
revdoor combs: 2054455634, time: 5 s, 410891126/s
knuth   combs: 2054455634, time: 7 s, 293493662/s
lam     combs: 2054455634, time: 2 s, 1027227817/s

root@ubuntu:/home/johnsmithx/lotto# ./test_algorithms 49 10
Combinations of 49 taken 10 at a time

lexicon combs: 8217822536, time: 34 s, 241700662/s
revdoor combs: 8217822536, time: 22 s, 373537388/s
knuth   combs: 8217822536, time: 28 s, 293493662/s
lam     combs: 8217822536, time: 8 s, 1027227817/s

root@ubuntu:/home/johnsmithx/lotto# ./test_algorithms 49 11
Combinations of 49 taken 11 at a time

lexicon combs: 29135916264, time: 124 s, 234967066/s
revdoor combs: 29135916264, time: 73 s, 399122140/s
knuth   combs: 29135916264, time: 102 s, 285646237/s
lam     combs: 29135916264, time: 30 s, 971197208/s


[Aubrecht]

evidentne si nerozumime...

[Aubrecht]

az vam ten program za 30 dni dobehne, zkuste se do naseho fora podivat znovu. poradim vam, jak se k obdobnemu vysledku dobrat za nekolik minut:)