Losowanie liczb, chodzi o wydajność

[zizou15]

Sytuacja jest taka.

Pewne zapytanie SQL zwraca mi pewną ilość rekordów(za każdym razem może to być inna ilość).

Powiedzmy, że są zwracane indeksy(liczby naturalne).

Chciałbym wylosować z tych liczb 3 liczby. Jakie algorytm byłby najbardziej wydajny?

Jedyne co mi przychodzi na myśl to wylosować jedną liczbę z tych zwróconych przez zapytanie, następnie drugą losować dopuki będzie ona inna niż pierwsza, a na końcu trzecią losować tak długo aż będzie ona inna niż pierwsze dwie wylosowane.

Ale taki algorytm wydaje mi się naiwny.

[mkr]

A nie lepiej bezpośrednio w zapytaniu SQL dodać

ORDER BY RAND() LIMIT 3

co zwróci 3 losowe rekordy

W php można jeżeli jest to tablica zrobić

shuffle($arr);

i wyświetlić 3 rekordy

[MMP]

ORDER BY RAND() * RAND() LIMIT 3 <-- Ma dużo większą skuteczność jeżeli chodzi o losowość

[zizou15]

Nie wiedziałem że w języku SQL jest funkcja losująca rekordy.

Wielkie dzieki:)

[mariosoft]

może tak:

$date_i = (int)date("i");

$date_s = (int)date("s");

$date_G = (int)date("G");

$liczba = 100;

$a = ($date_s+$date_i*$date_G)%$liczba;

$b = $a + ($date_s+$date_i+$date_G)%($liczba - $a);

$c = $b + ($date_s*$date_i+$date_G)%($liczba - $;

ale nie sprawdzałem tego.

pozdrawiam.

[mrtn]

A nie lepiej bezpośrednio w zapytaniu SQL dodać

ORDER BY RAND() LIMIT 3

Ja się nie znam, ale ta metoda wydaje mi się typowym błędem ludzi, którzy nie myślą o wydajności. Przecież przy 1 000 000 rekordów Mysql będzie musiał wywołać 1 000 000 razy generator liczb losowych i jescze to posortować.

Zizou15

Lepiej jakbyś podal konkretny przykład może da się zastosować jakiś prostszy algorytm ?

losowanie poejdynczego rekordu na pewno łatwiej zrobic znajac maxymalny ID

wtedy losujemy z przedzialu 1-max_id a w pytaniu uzywamy > zmiast = i LIMIT 1 jakby rekord o wylosowanym ID nie istniał

[yavaho]

Przecież przy 1 000 000 rekordów Mysql będzie musiał wywołać 1 000 000 razy generator liczb losowych i jescze to posortować.

Jesteś pewny że to w ten sposób działa? Czyżby programisci mysql byli aż tak tępi? Polecam zmierzyc czas obydwu sposobów (przy dużej bazie danych). Jestem pewien że nikt nie znajdzie szybszej metody niz poprostu:

ORDER BY RAND() LIMIT 3

[mkr]

Jesteś pewny że to w ten sposób działa?

mrtn ma racje. Przy bazach dużych tzn. 10000+ rekordów nie miał bym odwagi używać tej metody. Jestem pewny, że w takim wypadku 2 zapytania(count,select) do wyboru rekordów były by o wiele szybsze.

Jednak przy mniejszych projektach można pójść na łatwiznę.

[EDDY]

Wykonałem właśnie zapytanie "SELECT * FROM `tabela` ORDER BY RAND() LIMIT 3" na bazie 750 MB i 45k rekordów na domowym komputerze (Athlon 64 X2, RAID 0).

-> Wykonanie zapytania trwało 25.9658 sekund(y)

Powtórne zapytanie 16.0548 sekund(y).

[mkr]

SELECT * FROM `webseo_indicator` ORDER BY RAND() LIMIT 3

Pokaż rekordy 0 - 2 (3 wszystkich, Wykonanie zapytania trwało 0.9341 sekund(y))

SELECT count( * ) 
FROM `webseo_indicator`;# Rekordów: 1
SELECT * FROM `webseo_indicator` LIMIT 25253 , 3

Pokaż rekordy 0 - 2 (3 wszystkich, Wykonanie zapytania trwało 0.0172 sekund(y))

Baza 4,748 MB 67 453 rekordów

Przy okazji wydajności warto pamiętać o indexach Sprawdziłem właśnie co się stanie gdy usune index.

SELECT * FROM `webseo_indicator` WHERE `url` = 'www.wp.pl'

Pokaż rekordy 0 - 0 (1 wszystkich, Wykonanie zapytania trwało 0.1588 sekund(y))

a z indexem ( dla innego URL wiec bez ew. cache )

Pokaż rekordy 0 - 0 (1 wszystkich, Wykonanie zapytania trwało 0.0042 sekund(y))

[weecioo]

losowanie poejdynczego rekordu na pewno łatwiej zrobic znajac maxymalny ID

wtedy losujemy z przedzialu 1-max_id a w pytaniu uzywamy > zmiast = i LIMIT 1 jakby rekord o wylosowanym ID nie istniał

no wlasnie, z RAND() to sie raczej sprawdza przy malej ilosci rekordow i srendiej odwiedzalnosci... 25k rekordow, nie daj Bog z dynamiczną długością krotki + kilka tysięcy uu dziennie i zarypie serwer jak nic

ja bym zrobil cóś w ten deseń

najpierw SELECT min(id),max(id) FROM tabela

$aIdsUsed = Array(-1);
$aIdsSel = Array();
while(count($aIdsSel)<4){

  $iCurId = -1;
  while(!in_array($iCurId,$aIdsUsed))$iCurID = rand(idmin,idmax);

 if( SELECT id  FROM TABELA WHERE id>$iCurID AND ID not in(join(",",$aIdsUsed)))) $aIdsSel[] = row[id]


}

no i tam ewentualnie z poprawkami, bo tutaj np. nigdy sie nie wtylosuje rekord z maksymalnym id

[EDDY]

Baza 4,748 MB 67 453 rekordów

Twoja baza jest malutka. Ja chociaż mam RAID 0 (stripping) słyszałem przez te 25 sekund, jak dyski mielą dane, by wypluć trzy rekordy:D

Przy 4 MB to tylko kwestia procesora, jak jest szybki...

Dla porównania zrobiłem test na bazie dokładnie 20 MB i 39 472 rekordów -> 0.4204 sekund(y).

Oraz 4,7 MB z 43 720 rekordami -> 0.2243 sekund(y).

[mkr]

Co nie zmienia faktu, że już przy tak małej objętościowo bazie widać wyraźne różnice w czasie dostępu.

[EDDY]

Fakt, taka metoda jest bardzo nieoptymalna. Chyba, że bedziemy to buforować na xx godzin, a sama baza ma nie więcej jak kilkadziesiąt MB.

Zrobiłem jeszcze test na bazie 2,2 GB z 1 625 953 rekordami, a wynik to... 75.5999 sekund(y).

[Lizard]

Eddy jaki serwer to wytrzymuje ?