Меню
Что нового?

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

dimagolov

Новичок
maxwell, ну когда ты успокоишься?
смысл кода HraKK в том, что кол-во вызовов rand 2 * N - 1 без манипуляций с массивом вообще, а не непонятно сколько с поиском по массивам столько же непонятно сколько раз.

проблема в том, что у автора верхний интервал ограничен, то есть числа от 0 до K, что в таком варианте не учтено.
 
HraKK

HraKK

Мудак
Команда форума
maxwell
Так лучше?
PHP: 
<?php
$max= 10000;
$iteration=10;
$increace= $max/$iteration;
$step=1;
$array[0]=rand(0,$increace);

while($step<10)
{
$array[$step]=rand($array[$step-1]+1,$array[$step-1]+$increace);
++$step;
}
shuffle($array);
print_r($array);
?>
rand*N
без манипуляций.
от 0 до К учтено.
 
maxwell

maxwell

artifex
HraKK, dimagolov,
смысл данного кода в том, что абсолютно не решает проблему автора, а так же генерит числа далеко не случайные и далеко не без повторений.
 
HraKK

HraKK

Мудак
Команда форума
maxwell
Смысл данного кода что он генерирует псевдослучайные числа и без повторений. Ога?
И давай сравним скорость и memory лимит моего и твоего? Теоретик, блин.
 
HraKK

HraKK

Мудак
Команда форума
maxwell
ткни.

-~{}~ 09.07.08 00:29:

$max= 10;
$iteration=10;

Для контроля
 
maxwell

maxwell

artifex
Автор оригинала: HraKK
maxwell
ткни.
Нажмите для раскрытия...
----------step1
26 = rand(15, 115);
----------step2
42 = rand(26, 126);
----------step3
127 = rand(42, 142);
----------step4
215 = rand(127, 227);
----------step5
287 = rand(215, 315);
----------step6
287 = rand(287, 387);
----------step7
334 = rand(287, 387);
----------step8
391 = rand(334, 434);
----------step9
410 = rand(391, 491);

============
----------step1
1 = rand(0, 1);
----------step2
1 = rand(1, 2);
----------step3
1 = rand(1, 2);
----------step4
1 = rand(1, 2);
----------step5
2 = rand(1, 2);
----------step6
3 = rand(2, 3);
----------step7
3 = rand(3, 4);
----------step8
3 = rand(3, 4);
----------step9
3 = rand(3, 4);
 
HraKK

HraKK

Мудак
Команда форума
Вы что-то курите. Или взял мой первый код который я исправил через 3 минуты обновил дописал +1( не то скопировал).
$array[$step-1]+1
Скопируй новый.

-~{}~ 09.07.08 00:34:

Что б не было наездов что жто я потом исправил -
Отредактировано HraKK 09.07.08 в 00:26
Нажмите для раскрытия...
HraKK, без повторений?
Вы уверены? Или ткнуть? 09.07.08 00:27
Нажмите для раскрытия...
-~{}~ 09.07.08 00:39:

вот мой результат на контрольный:
PHP: 
Array ( [0] => 8 [1] => 2 [2] => 7 [3] => 5 [4] => 0 [5] => 3 [6] => 4 [7] => 6 [8] => 9 [9] => 1 )
 

vovanium

Новичок
HraKK
Вообще-то твой алгоритм, мягко говоря неправильный.
Числа получаются зависимыми от предыдущих. Вероятность выпадения чисел в начале диапазона значительно выше, чем в конце. Да и работает медленнее, чем вариант с isset
Вот провел банальный тест, выборка 10 чисел от 0 до 99, 100 000 циклов, т.е. было выбрано 1 млн. чисел, алгоритмы HraKK и rotoZOOM (я хотел такой же предложить, как наиболее толковый, но он меня опередил), в таблице выпадение чисел из каждого десятка и время выполнения.

Код: 
---------------------------
| n |    HraKK | rotoZOOM |
---------------------------
| 0 |    68094 |   100671 |
| 1 |   195331 |    99223 |
| 2 |   200168 |   100488 |
| 3 |   193799 |    99944 |
| 4 |   155857 |    99688 |
| 5 |    72214 |   100671 |
| 6 |    13822 |    99227 |
| 7 |      715 |   100474 |
| 8 |        0 |    99932 |
| 9 |        0 |    99682 |
---------------------------
| s | 1.103358 | 0.994618 |
---------------------------
Как видите числа 80+ не попали в выборку из миллиона чисел ни разу!! В то же время второй алгорим показывает, что у функции rand неплохое распределение чисел по всему диапазону, и отклонения в 0,5-0,6%
 

dimagolov

Новичок
vovanium, не придирайся. ничего не мешает сделать диапазон на каждом шаге динамический, а не фиксированный, тогда распределение должно выравняться.
PHP: 
<?php
$max= 10000;
$iteration=10;

for($step= 0, $start= 0; $step<$iteration; $step++) {
   $increase= ($max-$start)/($iteration-$step);
   $array[$step]=mt_rand($start+1,$start+$increase);
   $start= $array[$step];
}
shuffle($array);
print_r($array);
?>
алгоритм rotoZOOM хорош, но завязан на хеши массива и на сколько я помню имеет время все же выше чем O(N). что на массиве из 10 чисел не заметно, конечно.
 

vovanium

Новичок
dimagolov
что на массиве из 10 чисел не заметно, конечно
Нажмите для раскрытия...
Опять гадание на кофейной гуще? Начнем с того что автору нужно именно 10 чисел. Но специально для тебя проверил, алгоритм HraKK начинает работать быстрее хэша, только при выборке более 4600 чисел. До этой цифры хэши быстрее.

Динамический диапазон конечно улучшает ситуацию, но не решает её. Все равно одни числа встречаются в 5 раз чаще других.

Код: 
-----------------------------------------
| n |     HraKK |  rotoZOOM | dimagolov |
-----------------------------------------
| 0 |     68064 |    100674 |    148899 |
| 1 |    195354 |     99234 |    161133 |
| 2 |    200272 |    100477 |    149062 |
| 3 |    193801 |     99940 |    132103 |
| 4 |    155820 |     99682 |    112695 |
| 5 |     72162 |    100670 |     94513 |
| 6 |     13813 |     99231 |     75796 |
| 7 |       714 |    100484 |     58481 |
| 8 |         0 |     99933 |     35071 |
| 9 |         0 |     99675 |     32247 |
-----------------------------------------
| s |  1.121554 |  1.005704 |  1.194707 |
-----------------------------------------
Ну что следующий алгоритм будет с двух сторон начинать и сходиться к центру? :)
 

dimagolov

Новичок
Ну что следующий алгоритм будет с двух сторон начинать и сходиться к центру
Нажмите для раскрытия...
нет, не правильно. это оптический обман :) если задуматься, то станет очевидно (называй гадание, но думаю прав), что надо каждое число генерировать в своем интервале, вот тогда распределене выравняется.
PHP: 
<?php
$max= 10000;
$iteration=10;
$increase= $max/$iteration;

for($step= 0; $step<$iteration; $step++) {
   $array[$step]=mt_rand($step*$iteration+1,($start+1)*$increase);
}
shuffle($array);
print_r($array);
?>
-~{}~ 09.07.08 01:23:

мне хеши не понравились тем, что они узкоспециализированны для php:
1. во множестве других языков таких цирков с индексами массива не сделаешь
2. это ограничивает генерируемые значения целочисленными величинами. для пхп, где генераторы случайнх чисел исключительно целочисленные, это пракатывает, а вот если надо получать распределение вещественных в 0-1, то прикрутить даже пхп-шные индексы весьма затруднительно (хотя можно извратиться через строки).
 

vovanium

Новичок
dimagolov
нет, не правильно. это оптический обман
Нажмите для раскрытия...
Это я вообще шутил, там даже смайлик стоит ;)
что надо каждое число генерировать в своем интервале, вот тогда распределене выравняется.
Нажмите для раскрытия...
В таких случаях невозможны выпадения нескольких чисел в одном десятке и были бы провалы по границам диапазонов.

Что-то я не въехал что ты хотел сделать своим алгоритмом :)

-~{}~ 09.07.08 07:40:

1. во множестве других языков таких цирков с индексами массива не сделаешь
Нажмите для раскрытия...
Не знаю в каком множестве не сделаешь, но к примеру в JS и Perl без проблем. Да и делать, алгоритм с оглядкой на возможности других языков, не очень рационально.
а вот если надо получать распределение вещественных в 0-1, то прикрутить даже пхп-шные индексы весьма затруднительно
Нажмите для раскрытия...
Что-то не пойму, ты что не выспался или еще не спал? :) Для хэшей без разницы, какой ключ, оно будет работать как и для случайных вещественных, так и для строк. Нам же нужно только точное совпадения, и то что число преобразуется в строку нам неважно.
 

Altex

Новичок
PHP: 
function getRandomArrayElements(&$inputArray, $limit = 10)
{
    $keys = array_keys($inputArray);
    $result = array();
    for ($i = 0; $i < $limit; $i++)
    {
        $rand = mt_rand(0,count($keys)-1);
        $result[$keys[$rand]] = $intputArray[$keys[$rand]];
        unset($keys[$rand]);
    }
    return $result;
}
 
HraKK

HraKK

Мудак
Команда форума
vovanium
Я отнюдь не утверждал что у меня идеальный алгоритм, он решает полностью задачу автора и даже при большом количестве даст выйграш в скорости, но это не важно в текущей ситуации, а вакуумы как известно разные бывают.
 

WP

^_^
Верное решение:
PHP: 
function getnumbers($m,$n)
{
 if ($m < $n-1) {return FALSE;}
 $ns = array();
 for ($i = 0; $i < $n;)
 {
  $r = rand(0,$m);
  if (!in_array($r,$ns)) {$ns[] = $r; ++$i;}
 }
 return $ns;
}
-~{}~ 09.07.08 13:38:

Altex
[m]array_rand[/m]
 

Altex

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

-~{}~ 09.07.08 14:34:

array_rand - кстати да, а чем эта функция не подходит для автора?
 

vovanium

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

WP

^_^
Altex
Моё решение единственное верное, и самое быстрое.
 
HraKK

HraKK

Мудак
Команда форума
WP
Не тупи.

Altex
А ты покажи решение на базе array_rand
 
Войдите или зарегистрируйтесь для ответа.
Сверху