10 случайных, неповторяющихся чисел

WP · 9 Июл 2008

HraKK
> с одной н.
надо менять клаву.. западает н и й.
В моем случае rand() зависит только от seed, а не от других rand()'ов. А в твоем зависит от других.

kruglov
Подумал об этом, но лень.

HraKK · 9 Июл 2008

WP
Зависимость от неопределенного числа это не зависимость)
Но имхо это холивар.

Результат один - в твоем варианте имеет места более тонкая балансировака равнораспределенности на уровне нативной поддержки rand. В моем же постоянная быстрая скорость(как показали тесты до 5х раз) и не зависимость ни от чего.

Если автору надо приближение к мифической равнораспределености - тогда твой. Во всех остальных - мой.

dimagolov · 9 Июл 2008

народ, перестаньте. раз накладывается ограничение на неповторяемость значений, значит такого же ровного распределения, как дает начальная ф-я, вы не получите ну никак.

HraKK · 9 Июл 2008

dimagolov
+1

grigori · 9 Июл 2008

интересно поискать в мире практическую непредсказуемую равнораспределенность

Думаю, вопрос в цене - каков максимальный уровень предсказуемости для данной задачи?
Ответить на это может лишь автор темы...

Моё решение единственное верное, и самое быстрое

"Решение WP всесильно потому что оно верно" (С) В.И. Ленин, Полное собрание сочинений, 5 изд., т. 23, с. 43
=))))

dimagolov · 9 Июл 2008

тут вообще надо делать пороговую оценку - соотношение кол-ва выбираемых значений к их диапазону, при котором вероятность повторений ниже заданной.

WP, есть вариант твоего алгоритма, чтобы он работал быстро. генерим не K чисел случайных, а K + M или скорее K * n чисел, складываем их в массив, убиваем (один раз!!) неуникальные и все, победа, отдаем из него K нужных. параметр n будет зависить от порога описанного выше.

kruglov · 9 Июл 2008

убиваем (один раз!!) неуникальные

Мне кажется, сложность этого метода не сильно уступает банальному сравнению нового числа с массивом уже придуманных чисел. Ибо все равно каждое с каждым сравнивается.

А если мы этот массив еще и упорядоченным сделаем и поиском через недолет-перелет будем искать...

vovanium · 9 Июл 2008

HraKK

В моем же постоянная быстрая скорость(как показали тесты до 5х раз)

Вообще-то тесты не совсем корректные, т.к. ты сравнивал вариант с in_array в виде функции, а миллион вызовов юзерской функции занимают приличное время. Реально isset при десятке элементов будет лишь немного медленнее твоего варианта, но при это более равномерный.

grigori

интересно поискать в мире практическую непредсказуемую равнораспределенность

Для этого и делают равномерное распредение, чтобы выпадение любого числа было равновероятным. В случаи алгоритма HraKK даже после апдейта dimagolov, получается что одни числа выпадают в 5 раз чаще других, т.е. это уже даще не псевдослучайность. И если по этому алгоритму делать к примеру игровой автомат, то можно немплохо пролететь

HraKK · 9 Июл 2008

vovanium
да ну? проверь при единичном срабатывании
8.70227813721E
2.28881835938E
теже 4х.

примеру игровой автомат,

А если сделать на алгоритме WP управление ракетой, и скорость отклика не будет достаточной и она разобьецца

((

WP · 9 Июл 2008

grigori
Брось монетку. Вот тебе и непредсказуемая равнораспределенность.

dimagolov
Он и так работает быстро.

HraKK · 9 Июл 2008

WP
А вот и не правда. Монета падает неравномерно.

WP · 9 Июл 2008

HraKK
Это почему? Равная вероятность.

-~{}~ 09.07.08 19:56:

Я попробовал, равномерно.

vovanium · 9 Июл 2008

А вот и не правда. Монета падает неравномерно.

В теории как раз одинаково падает в обе стороны

Вот что у меня вышло при сравнении

Код:

-----------------------------------------------------
| n |     HraKK |  rotoZOOM | dimagolov |  in_array |
-----------------------------------------------------
| 0 |    168060 |    100677 |    149219 |    100668 |
| 1 |    195383 |     99235 |    161005 |     99239 |
| 2 |    200216 |    100476 |    149061 |    100480 |
| 3 |    193790 |     99938 |    131885 |     99938 |
| 4 |    155824 |     99666 |    112684 |     99671 |
| 5 |     72197 |    100684 |     94759 |    100674 |
| 6 |     13808 |     99236 |     75815 |     99233 |
| 7 |       722 |    100473 |     58332 |    100472 |
| 8 |         0 |     99934 |     34995 |     99939 |
| 9 |         0 |     99681 |     32245 |     99686 |
-----------------------------------------------------
| s |  1.183823 |  0.996315 |  1.164428 |  1.408776 |
-----------------------------------------------------

Желающие могу затестить сами

PHP:

<?php
$a = $b = $d = $e = array_fill(0, 100, 0);
$max_num = $max = 99; // Максимальное число в выбоке
$iteration = 10; // Количество выбираемых чисел

$repeat = 100000; // Повторов

$start_a = microtime(1);
for($c = 0; $c < $repeat; $c++){
    $increace= $max/$iteration; 
    $step=1; 
    $array[0]=rand(0,$increace); 
    $a[floor($array[0] / 10)]++;
    while($step < $iteration) { 
        $array[$step]=rand($array[$step-1]+1,$array[$step-1]+$increace); 
        $a[floor($array[$step] / 10)]++;
        ++$step; 
    }
    shuffle($array);
}
$end_a = microtime(1);

$start_b = microtime(1);
for($c = 0; $c < $repeat; $c++){
    $used_nums = array();
    $limit = $iteration;  
    while($limit) { 
        $random = rand(0, $max_num);
        if (!isset($used_nums[$random])){
            $used_nums[$random]=true;
            $b[floor($random / 10)]++; 
            $limit--;
        }
    } 
}
$end_b  = microtime(1);

$start_d = microtime(1);
for($c = 0; $c < $repeat; $c++){
    for($step= 0, $start= 0; $step<$iteration; $step++) { 
       $increase= ($max-$start)/($iteration-$step); 
       $array[$step]=mt_rand($start+1,$start+$increase); 
       $start= $array[$step]; 
       $d[floor($start / 10)]++; 
    }
    shuffle($array);
}
$end_d = microtime(1);

$used_nums = array(); 
$start_e = microtime(1);
for($c = 0; $c < $repeat; $c++){
    $used_nums = array();
    $limit = $iteration;  
    while($limit) { 
        $random = rand(0, $max_num);
        if (!in_array($random, $used_nums)){
            $used_nums[$limit] = $random;
            $e[floor($random / 10)]++;
            $limit--; 
        }
    }
}
$end_e = microtime(1);

// Вывод результатов
echo "<pre>";
$line = str_repeat('-', 53). "\n";
echo $line;
printf("| %s | %9s | %9s | %9s | %9s |\n", 'n', 'HraKK', 'rotoZOOM', 'dimagolov', 'in_array');
echo $line;
for($i = 0; $i < 10; $i++){
    printf("| %d | %9d | %9d | %9d | %9d |\n", $i, $a[$i], $b[$i], $d[$i], $e[$i]);
}
echo $line;
printf("| %s |  %.6f |  %.6f |  %.6f |  %.6f |\n", 's', $end_a-$start_a, $end_b-$start_b, $end_d-$start_d, $end_e-$start_e); 
echo $line;
?>

dimagolov · 9 Июл 2008

В случаи алгоритма HraKK даже после апдейта dimagolov, получается что одни числа выпадают в 5 раз чаще других

vovanium, ты вроде не публиковал результат с последней версией, которая берет равные интервалы и в каждом берет одно случайное. можешь выложить?
я понимаю, что каждое конкретное распределение будет совсем не такое, как если просто последовательно генерировать и проверять случайное, но вот сумарное кол-во по даже более мелким интервалам при множестве повторений должно быть близкое.

HraKK · 9 Июл 2008

WP
Потому что стороны имею разный вес и/или рельеф.

vovanium · 9 Июл 2008

Выложил, алгоритмы немного подправленные, чтобы можно было считать распредение, конечно floor вносит свою погрешность в скорость работы, но тут для всех условия равные. Можете убрать floor и вывести распределение по всему диапазону.

Кстати интересно я сделал вывод для всего диапазона от 0-99, твой dimagolov не выдает 0

dimagolov · 9 Июл 2008

vovanium, ну с 0 понятно, там всегда начинается с +1 от начала.
поставил для всех ф-ю mt_rand и поставил свой вариант с равными отрезками, плюс для наглядности взял распределение по 4 а не по 10.

Код:

-----------------------------------------------------
| n |     HraKK |  rotoZOOM | dimagolov |  in_array |
-----------------------------------------------------
| 0 |      7286 |     39898 |     33163 |     40087 |
| 1 |     32150 |     39580 |     44442 |     39901 |
| 2 |     64939 |     39793 |     33378 |     40003 |
| 3 |     78569 |     39980 |     44541 |     39770 |
| 4 |     80456 |     40191 |     44476 |     40055 |
| 5 |     79685 |     39876 |     33142 |     40037 |
| 6 |     80241 |     40227 |     44559 |     40175 |
| 7 |     79651 |     40152 |     33406 |     39850 |
| 8 |     78714 |     39892 |     44322 |     40073 |
| 9 |     75535 |     39911 |     44571 |     39991 |
| 10 |     70083 |     39705 |     33354 |     39736 |
| 11 |     60060 |     40146 |     44470 |     39603 |
| 12 |     46898 |     40131 |     33202 |     39761 |
| 13 |     32204 |     39909 |     44336 |     40060 |
| 14 |     18810 |     39780 |     44638 |     40181 |
| 15 |      9558 |     40342 |     33548 |     39636 |
| 16 |      3699 |     39851 |     44468 |     40096 |
| 17 |      1160 |     39918 |     32978 |     40217 |
| 18 |       254 |     39982 |     44108 |     40078 |
| 19 |        47 |     40043 |     44898 |     39939 |
| 20 |         1 |     40039 |     33334 |     40036 |
| 21 |         0 |     40153 |     44556 |     40170 |
| 22 |         0 |     40299 |     33125 |     39807 |
| 23 |         0 |     40164 |     44447 |     40225 |
| 24 |         0 |     40038 |     44538 |     40513 |
-----------------------------------------------------
| s |  1.768678 |  1.685388 |  1.707598 |  2.356826 |
-----------------------------------------------------

PHP:

<?php
set_time_limit (300);

$a = $b = $d = $e = array_fill(0, 100, 0);
$max_num = $max = 99;
$iteration = 10;

$repeat = 100000;

$start_a = microtime(1);
for($c = 0; $c < $repeat; $c++){
    $increace= $max/$iteration; 
    $step=1; 
    $array[0]=mt_rand(0,$increace); 

    while($step < $iteration) { 
        $array[$step]=mt_rand($array[$step-1]+1,$array[$step-1]+$increace); 
        $a[floor($array[$step] / 4)]++;
        ++$step; 
    }
    shuffle($array);
}
$end_a = microtime(1);

$start_b = microtime(1);
for($c = 0; $c < $repeat; $c++){
    $used_nums = array();
    $limit = $iteration;  
    while($limit) { 
        $random = mt_rand(0, $max_num);
        if (!isset($used_nums[$random])){
            $used_nums[$random]=true;
            $b[floor($random / 4)]++; 
            $limit--;
        }
    } 
}
$end_b  = microtime(1);

$start_d = microtime(1);
$increase= $max/$iteration;
for($c = 0; $c < $repeat; $c++){

    for($step= 0; $step<$iteration; $step++) {
       $array[$step]=mt_rand($step*$iteration+1,($step+1)*$increase);
       $d[floor($array[$step] / 4)]++; 
    } 
    shuffle($array);
}
$end_d = microtime(1);

$used_nums = array(); 
$start_e = microtime(1);
for($c = 0; $c < $repeat; $c++){
    $used_nums = array();
    $limit = $iteration;  
    while($limit) { 
        $random = mt_rand(0, $max_num);
        if (!in_array($random, $used_nums)){
            $used_nums[$limit] = $random;
            $e[floor($random / 4)]++;
            $limit--; 
        }
    }
}
$end_e = microtime(1);


echo "<pre>";
$line = str_repeat('-', 53). "\n";
echo $line;
printf("| %s | %9s | %9s | %9s | %9s |\n", 'n', 'HraKK', 'rotoZOOM', 'dimagolov', 'in_array');
echo $line;
for($i = 0; $i < 25; $i++){
    printf("| %d | %9d | %9d | %9d | %9d |\n", $i, $a[$i], $b[$i], $d[$i], $e[$i]);
}
echo $line;
printf("| %s |  %.6f |  %.6f |  %.6f |  %.6f |\n", 's', $end_a-$start_a, $end_b-$start_b, $end_d-$start_d, $end_e-$start_e); 
echo $line;
?>

HraKK · 9 Июл 2008

vovanium
а еще интереснее можно увидить при MAX = 9;

Код:

-----------------------------------------------------
| n |     HraKK |  rotoZOOM | dimagolov |  in_array |
-----------------------------------------------------
| 0 |   1000000 |   1000000 |    900000 |   1000000 |
| 1 |         0 |         0 |    100000 |         0 |
| 2 |         0 |         0 |         0 |         0 |
| 3 |         0 |         0 |         0 |         0 |
| 4 |         0 |         0 |         0 |         0 |
| 5 |         0 |         0 |         0 |         0 |
| 6 |         0 |         0 |         0 |         0 |
| 7 |         0 |         0 |         0 |         0 |
| 8 |         0 |         0 |         0 |         0 |
| 9 |         0 |         0 |         0 |         0 |
-----------------------------------------------------
| s |  2.392210 |  3.350443 |  2.451910 |  5.417143 |
-----------------------------------------------------

vovanium · 9 Июл 2008

dimagolov
там только в алгоритме HraKK, я пропустил первое число, как-то проглядел что оно же не в цикле, после

$array[0]=rand(0,$increace);

поставь

$a[floor($array[0] / 10)]++;

-~{}~ 09.07.08 19:43:

HraKK

а еще интереснее можно увидить при MAX = 9;

Да у dimagolov что-то вылезло интересное

fixxxer · 9 Июл 2008

нифига же себе топик, в рот мне ноги

ну вот вам вариант с равномерным распределением и предсказуемым временем выполнения. неоптимальный. оптимизируйте, по идее деревья те же но мне лениво

PHP:

$range = array(0, 1<<15);
$amount = 10;

$r = array();

for ($i=0; $i<$amount; ++$i) {
    $rnd = mt_rand($range[0], $range[1] - count($r));
    foreach ($r as $v) {
        if ($rnd >= $v) ++$rnd;
    }
    $r[] = $rnd;
    sort($r);
}
shuffle($r);
var_dump($r);

10 случайных, неповторяющихся чисел

^_^

Мудак

Новичок

Мудак

( ͡° ͜ʖ ͡°)

Новичок

Новичок

Новичок

Мудак

^_^

Мудак

^_^

Новичок

Новичок

Мудак

Новичок

Новичок

Мудак

Новичок

К.О.