DevProTalk - random koji favorizuje

DevProTalk (http://www.devprotalk.com/index.php)

- Programiranje (http://www.devprotalk.com/forumdisplay.php?f=23)

- - random koji favorizuje (http://www.devprotalk.com/showthread.php?t=2799)

random koji favorizuje

pozdrav ekipo

nije da sam bas toliko los sa matematikom koliko mi se spava :)

elem problem:

potreban mi je specijalan random koji ce raditi na sledecem principu:

spec_rand($from,$to,$factor);

elem to bi radilo otprilike ovako

spec_random(10,100,3);
to bi znacilo da je 3x veca mogucnost da funkcija vrati veci broj tj blizi 100
a ako bi faktor bio -3 znaci veca verovatnoca da ce biti manji broj, tj blizi 10

any ideas?

p.s. ne, nisam googlao :D

p.s.2

kratko objasnjenje, imacu neku tabelu sa nekim proizvodima, gde ce svaki imati neki faktor recimo od 1-100, a na glavnoj stranici ce se prikazivati recimo 20 proizvoda stim sto ce biti favorizovani ovi sa vecim faktorom..
a ako u spec_rand funkciju unesem 0 kao faktor onda da radi kao obican random, tj da ne favorizuje...

hmm sad razmisljam 1 i -1 faktor bi bili takodje kao obican random....

Citat:

Originalno napisao kodi

to bi znacilo da je 3x veca mogucnost da funkcija vrati veci broj tj blizi 100
a ako bi faktor bio -3 znaci veca verovatnoca da ce biti manji broj, tj blizi 10

Теби треба генерисање псеудо-случајног целог броја на задатом интервалу, са произвољном расподелом. Програмски језици обично нуде генерисање псеудо-случајног целог броја са униформном расподелом.

Срећом па се то лако ради ако имаш на лагеру генератор униформне расподеле, можеш да направиш ма који други.

Међутим овако како си ти дефинисао неће да може, или бар не може директно. Бољи начин је да одредиш функцију расподеле која ти врши посао, а онда да пробаш некако ту функцију да пресликаш у твој параметар.

Почиње се од функције расподеле за униформну случајну променљиву на интервалу 0 до 1. За друге интервале можеш да скалираш, али овај је најједноставнији. Означи са U ту случајну променљиву.

Њена функција расподеле је:

F_U(x) = P( U < x) = { 0, x <0 ; x, x E [0, 1]; 1, x > 1

Претпостави сад да знаш која ти функција расподеле G(x) треба. Она ти зависи од примене, тако да је дефинисање G(x) твој посао. Претпостављам из твог описа да се ради о линеарној функцији густине расподеле, према томе о квадратној функцији расподеле, на опсегу који те занима. То је зато што је функција расподеле интеграл функције густине расподеле, а како је густина вероватно линеарна, то је расподела квадратна. Али о овом касније.

Све што треба јесте да генеришеш случајну променљиву Y = G^-1(U), где је G^-1 инверзна функција од G, а U случајна променљива са униформном расподелом. Тако добијена променљива има управо расподелу G(x). Доказ следи:

F_Y(x) = P ( Y < x) = P( G^-1(U) < x) = P [U < G(x)]= G(x).

Дакле добили смо да је тачно: F_Y(x) = G(x) а то је оно што нам треба.

Због појављивања инверза функције расподеле G, она мора да буде монотона. Уколико није, у овом случају то може да се реши накнадним пермутовањем елемената, а у општем случају можда треба да се потражи други генератор.

ф

Само да допуним горњу причицу једним примером, да не буде да лупам у празну шерпу.

Пробаћу да набодем шта ти је потребно, мада то није тако добро дефинисано.

Претпостављам да је густина расподеле g(x) на интервалу (f,t) (from->to) таква да је
g(t) = n * g(f), што је отприлике оно што си рекао горе. Једино је фактор мало другачији јер је инверз мултипликативан а не адитиван као у твом случају. Тојест, обрнути случај од n = 3 добио би се са n' = 1/3, а не са n = -3. Али то ваљда није неки проблем.

Претпоставићу да је интерполација између крајњих тачака линеарна. Овај део ниси навео у поставци, тако да провери да ли ти одговара. Тада је:

g(x) = { 0, x < f; ax + b, x E [f, t]; 0, x > t

Треба нам да одредимо a и b у функцији од n да бисмо добили g(x). Онда ћемо да инвертујемо g(x) и то је оно што нам треба.

Линеарном интерполацијом се добија да је:

a = (n-1) / (t-f) * q
b = (t - nf) / (t-f) * q

што су вредности које добијете ако протурите праву ax+b кроз тачке: (f, q) и (t, nq). Овде нам је n параметар кога задаје корисник, а q мора да се одреди из интегралног услова за расподелу.

Пошто g(x) мора да задовољи интегрални услов за расподелу да је \int_{-\infty}^{+\infty} = 1, интеграљењем функције g(x) по целом домену добије се:

q = 2/[(n+1)(t-f)]

(паде ми напамет мало касније па да допуним: вредност за q добио сам формално интеграљењем, али може да се добије и на бржи начин тако што се уочи да је средња вредност функције тачно на средини интервала. Штос је сличан ономе ког је Гаус искористио да срачуна брзо збир свих бројева од 1 до 100)

Сада треба да пређемо на функцију расподеле G(x). По дефиницији,

G(x) = \int_{\infty}^x g(x) dx

а интеграљењем део по део у овом случају добија се:

G(x) = { 0, x< f; a/2(x^2-f^2) + b(x-f), x \in [f, t]; 1, x > t

Налажењем инверза G^{-1}(x) добија се, за интервал [0,1] ово:

G^{-1}(y) = H(y) = 1/a * ( -b + \sqrt{ b^2 + 2a(a/2 f^2 + bf)})

где су нам све величине или познате од пре, или зависе од параметра n.

H(y) је у ствари функција и од параметра n, па ћу да забележим: H(y; n).

И сад је лако.

Ако имаш функцију rand() која генерише реални број од 0 до 1 са униформном расподелом, радиш следеће:

u = rand();
y = H(u; n)

И број y је извучен тачно из расподеле коју си хтео.

ф

u prevodu za one koji nisu sa ETF-a ili PMF-a, poenta je da podelis interval na konacan broj delova (tj. cele brojeve u ovom slucaju) i da onda napravis funkciju koja ce da oslika to "favorizovanje". Posto imas na raspolaganju funkciju koja daje (pseudo) uniformnu raspodelu, odnosno svi brojevi na intervalu imaju iste sanse, ono sto treba da se uradi je da se prosiri interval na kome je odredjeni rezultat. Ako 1 ima 5 puta vece sanse od 5 onda, da bi dobio tvoju verovatnocu na intervalu (1,5) treba da ti je interval za rezultat "1" od 0-4, za rezultat "2" od 5-8, "3" je od 9-11, "4" od 12-13 i "5" je 14. Onda izvuces rand (0,14) i vidis u koji interval ti upada dobijeni rezultat. "1" ti ima verovatnocu 5/15, "2" je 4/15, "3" je 3/15, "4" je 2/15 i "5" je 1/15, odnosno dobio si trazeno..

Mozda mozes da iskoristis (PHP manual):

Citat:

Here's an algorithm to make a weighted selection of an item from an array.
Say we have an array $items with keys as items and values as corresponding weights.
For example:

Kôd:

<?php

$items = array(

    item1 => 3,

    item2 => 4,

    item3 => 5,

);

?>

i.e. we want to choose item1 25% of the time, item2 33.3% of the time and item3 41.6% of the time.
Here's a function that works when the weights are positive integers:

Kôd:

<?php

function array_rand_weighted($values) {

    $r = mt_rand(1, array_sum($values));

    foreach ($values as $item => $weight) {

        if  ($r <= $weight) return $item;

        $r -= $weight;

    }

}

?>

i ja sam razmisljao nesto kao ivanhoe, na kraju sam nacrtao grafik i vidm da je to manje-vise neka logaritamska funkcija...

sad ja znam da je ovo daleko od idealnog, al radi posao
(pod pretpostavkom da je range 1 <-> x i da je n >= 2 )

Kôd:



function spec_rand($from,$to,$n){



    $new_to=($n * ($to/2 + 0.5));

    $u=rand($from,$new_to);

    $final=round($to*(log(($u+(triag(1)*($n/$to))),($new_to))));

    if($final==0){ $final=1; }

    return $final;   



}

-spec_rand(1,30,5) vraca mnogo vise brojeva blizih 30 nego spec_rand(1,30,2) gde mnogo cesce izbacuje brojeve manje od 15;

-spec_rand(1,30,100) vraca skoro uvek 22 i vece.. bas se retko zadesi manji od 20

naravno glavni je nedostatak sto se neki brojevi zbog zaokruzivanja ne pojavljuju redje, vec nikad :(

dve stvari

1) gornji kod treba da bude::

Kôd:

function spec_rand($from,$to,$n){



    $new_to=($n * ($to/2 + 0.5));

    $u=rand($from,$new_to);

    $final=round($to*(log(($u+($n/$to)),($new_to))));

    if($final==0){ $final=1; }

    return $final;   



}

2) uh, zakomplikovah ga bez potrebe, ovo resava stvar
(tako mi se bar cini)

Kôd:



$n=3;

$SQL="select  id, name, (FLOOR(1 + (RAND() * 99)) * (product_factor*$n)) as new_ord 

from products 

order by new_ord desc 

limit 0,20";

Očigledno se nisi potrudio da pročitaš šta su ti ljudi napisali nego teraš svoje... ;)

Da probam da približim ovo što Ivanhoe kaže (filmil je i za mene previše stručan ;)), prenoseći ideju u svet baza.

Dakle, na raspolaganju ti je npr. najobičnija unfiormna random funkcija rand(n), koja vraća ceo broj između 0 i n.

Imaš tabelu T sa nekim ID-jem i nekim slogovima. Svaki slog ima polje težina, koja je neki integer. Hoćeš da polje sa 5 puta većom težinom od drugog bude 5 puta verovatnije izvučeno iz random bubnja. Uradiš sledeće:

n := select sum(težina) from T

x := rand(n)

Upit koji ti vraća traženi slog je:

Kôd:

select top 1 t1.id, sum(t2.težina) from tabela t1

inner join tabela t2 on t1.težina > t2.težina

group by t1.id

having sum(t2.težina) <= x

order by sum(t2.težina) desc

Citat:

Originalno napisao kodi

i ja sam razmisljao nesto kao ivanhoe, na kraju sam nacrtao grafik i vidm da je to manje-vise neka logaritamska funkcija...

Није мање-више логаритамска, него је тачно квадратни корен, тј. константа плус квадратни корен из нечега. Логаритамска функција ти даје експоненцијални инверз који брзо оде у засићење, отуд ти се неки бројеви не појављују.

Пробај са квадратним кореном, не мораш нужно да наместиш све параметре као што сам показао, него направи неколико проба са разним параметрима, па узми шта ти се највише свиђа.

ф