random + mysql

[filmil]

Originalno napisao mega023

Poznato je da order by rand() dosta spora fukcija, pa u zelji da je izbegnem trazim neko drugo resenje kako da iz tabele od par hiljada podataka, dobijem n random podataka (recimo da mi treba 20 random podataka).

Постоји метода која захтева да се секвенцијално прочитају сви уноси у табелу, која се користи за јако велике скупове података (стотине милијарди мерења на пример), и која даје N случајно изабраних уноса, са тачно униформном расподелом.

Претпоставимо да имаш M уноса у табелу (рецимо M=100.000.000.000) и да ти треба N = 20 случајно (са униформном расподелом) изабраних уноса у табелу. Пошто је М јако велико, не долази у обзир прављење великог низа, већ читамо један по један елемент из табеле, обрадимо га и идемо даље.

Алгоритам је следећи:

1. Одвоји низ A од N елемената и крени редом да учитаваш податке из табеле
2. Првих N елемената ишчитаних из табеле само ископирај истим редом у низ
3. P = 1
4. Понављај док P не буде веће од M:
   1. Прочитај број P по реду из табеле.
   2. Генериши случајан цео B број са унифромном расподелом у интервалу 1..P.
   3. Ако је добијени број мањи или једнак N, елемент са редним бројем P убаци у низ А на позицију B. У супротном не убацуј елемент, већ га занемари.
   4. Увећај P за један.

Кога не мрзи може да докаже да је добијени низ изабран са тачно униформном расподелом (оно на шта се често мисли кад се каже „рандом“) од свих уноса из табеле.

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

Посолити према укусу.

ф