IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Avatar
František Pastorek
Člen
Avatar
František Pastorek:3.6.2017 21:06

Dobrý večer,

mám taký problém, že mám niekoľko objektov a každý ma inú pravdepodobnosť (hodnotu). Snažím sa vytvoriť algoritmus, ktorý vyberie nejaký objekt. Rád by som to spravil v konštantnom čase.

Príklad:

objekt1: 2
objekt2: 2
objekt3: 4
objekt4: 8
objekt5: 3

Ja chcem vybrať objekt tak, že objekt s najvyššou hodnotou bude mať najvyššiu pravdepodobnosť výberu a naopak, objekt s najmenšou hodnotou bude mať najmenšiu pravdepodobnosť výberu.

Algoritmus, v ktorom sčítam všetky hodnoty a následne vygenerujem náhodné číslo v rozmedzí 1 a súčtu hodnôt a následne prechádzam objekty tak, že hľadám hodnotu hodnotu objektu menšiu ako číslo, ktoré som vygeneroval a to takým spôsobom, že mám premennú do ktorej pričítavam hodnotu objektu, som zobral do úvahy. Problém je ten, že vždy keď chcem vybrať objekt tak v najhoršom prípade musím prejsť celé pole objektov. Ak je teda vybratý objekt posledný. A toto opakovať vždy pri výbere objektu.

Pri algoritme, kde vytvorím počet objektov ekvivalentný k hodnote, ktorú má je problém ten, že pri veľkom počte objektov bude pole veľmi veľké. Ďalším problémom je, že pri zmene hodnoty musím celé pole nanovo vytvoriť.

Vopred ďakujem za akúkoľvek radu.

 
Odpovědět
3.6.2017 21:06
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na František Pastorek
Jan Vargovský:3.6.2017 21:36

Osobně neznám nějaký algoritmus, který by to uměl udělat rychleji, než v lineárním čase. Jestliže často ty pravděpodobnosti měníš, tak si je můžeš ukládat mezivýsledky (jestli se bavíme o fitness proportionate/rou­lette wheel selection).

 
Nahoru Odpovědět
3.6.2017 21:36
Avatar
František Pastorek
Člen
Avatar
František Pastorek:3.6.2017 21:42

Ou. Hej hovorím o tom. Síce programujem niečo úplne iné ale princíp je rovnaký. Ako, na začiatku ak musím sčítať všetky fitness tak to je ešte v pohode lebo pri ďalších výpočtoch by som iba upravil interval náhodného generovania čísla. Ja si myslím, že existuje. Minimálne umelou inteligenciou. Skúsim vysvetliť o čo sa vlastne pokúšam.

Snažím sa spraviť testovanie v ktorom má každá otázka na začiatku rovnakú pravdepodobnosť výberu. Po nesprávnom odpovedaní na otázku, sa zväčší pravdepodobnosť výberu danej otázky. Takže sa pravdepodobnosti menia iba trochu, nič drastické.

Roymýšlal som aj nad nejakým AVL stromom ale nič rozumné mi nenapadlo.

 
Nahoru Odpovědět
3.6.2017 21:42
Avatar
gcx11
Tvůrce
Avatar
Odpovídá na František Pastorek
gcx11:3.6.2017 22:54

Můžeš to udělat tak, že si vyrobíš nové pole, kde budou předpočítané hodnoty a toto pole pak projdeš binárním vyhledáváním, čímž se dostaneš na logaritmickou složitost.

Pro 1000 objektů -> max 11 porovnání, což není tak špatné.

Editováno 3.6.2017 22:54
 
Nahoru Odpovědět
3.6.2017 22:54
Avatar
František Pastorek
Člen
Avatar
František Pastorek:6.6.2017 16:17

Hmm. To by bolo už asi lepšie, miesto predgenerovania všetkých čísel predgenerovať pozície v poli. Teda miesto 1, 2, 3, 4, 5, 6, 7, 8, 9, 10... by vygenerované číslo zodpovedalo pozícií v poli, v ktorom by boli reálne pozície objektov. Teda napriklad, 0, 0, 0, 1, 1, 2, 3, 3, 3, 3, 3, 4, 4, 4... Z binárneho by som spravil konštantné. Chcel som sa však vyhnúť generovaniu veľkého pola.

 
Nahoru Odpovědět
6.6.2017 16:17
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 5 zpráv z 5.