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

3 случайный значение из заданного диапазона

belbek

Новичок
3 случайный значение из заданного диапазона

Как правильно (наиболее эффективно) решается следующая задача:

из заданного диапазона нужно выбрать и отобразить на одной странице одновременно 3 разных случайных целых числа.
Недопустимо отображение скажем 2х одинаковых чисел одновременно.

1 3 2
3 4 8
1 1 3 - недопустимо

Всегда ли необходима повторная генерация после сравнения и обнаружения совпадения?

Спасибо.
 
Wicked

Wicked

Новичок
можно генерировать без совпадений, что-то типа такого:

PHP: 
$min = 1;
$max = 5;
$count = 3;
$numbers = array();
for ($i = 0; $i < $count; $i++) {
  $number = rand($min, $max - $i);
  sort($numbers);
  for($j = 0; $j < $i; $j++) {
    if ($numbers[$j] <= $number) {
      $number++;
    }
  }
  $numbers[] = $number;
}

var_dump($numbers);
-~{}~ 13.03.09 14:27:

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

в конце не помешает array_shuffle().
 
zerkms

zerkms

TDD infected
Команда форума
Wicked
ну согласись, что на примитивной задаче гораздо проще решение с перегенерацией. а человек как всегда думает, что у него это самое узкое место и будет хайлоад с 1b hits/day.

-~{}~ 13.03.09 18:34:

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

Wicked

Новичок
zerkms
равномерная.

насчет хайлоада - не знаю, зачем ты это сюда приплёл :)
 
HraKK

HraKK

Мудак
Команда форума
Уже была забавная тема в поиск. Там где WP выложил единственное правильное и самое быстрое решение! ( которая почему-то сливала в 4+ раза моему :( наверно звезды не в том знаке задиака были )
 

dadoc

Новичок
Тоже как то озадачивался такой проблемой и остановился вот на током коде:

$min = 1; $max = 50;

$a = array_flip(range($min, $max));

print_r(array_rand($a, 3));
 
antson

antson

Новичок
Партнер клуба
dadoc
выкини свой код. при большом диапазоне У вас
Allowed memory size of XXXXXXX bytes exhausted (tried to allocate 35 bytes)
 

dadoc

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

bakla

Новичок
PHP: 
$min = 1;
$max = RAND_MAX;

$i = $max/3;
if ($i <= $min) {
    $i = $min + 1;
}
$j = $i<<1;
if ($j >= $max) {
    $j = $max - 1;
}

$a = array(
    rand($min, $i-1),
    rand($i, $j),
    rand($j+1, $max)
);
shuffle($a);
По идее как у Wicked, но побыстрее. Единственный минус, это то, что числа не совсем случайные..
 
zerkms

zerkms

TDD infected
Команда форума
По идее как у Wicked, но побыстрее.
Нажмите для раскрытия...
у тебя решение совсем не правильное.

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

Royal Flash

-=MaestrO=-
Автор оригинала: Wicked
$count = 3;
Нажмите для раскрытия...
Зачем нужна переменная? В задаче четко определено количество = 3.

Предлагаю свой вариант, с рекурсией. Чем больше диапозон, тем меньше шансов отработки рекурси. В диапозоне от 1 до 3 рекурсия происходила более 10 раз в 2 случаях из ста. Если диапозон от 1 до 100 вероятность повторного запуска функции ничтожно мала.

PHP: 
$min = 1;
$max = 3;

function random($min, $max)
  {
  for ($i = 1; $i <= 3; $i++)
    {
    $out[$i] = rand ($min, $max);
    }
  if ($out[1] == $out[2] OR $out[1] == $out[3] OR $out[2] == $out[3])
    {
    $out = random($min, $max);
    }
  return $out;  
  }

$array_out = random($min, $max);
print_r($array_out);
Просто, нересурсоемко и работает 100%.
 

vovanium

Новичок
Royal Flash
Чесно говоря более дурацкую функцию наверное сложно придумать. Крутое условие, а если еще учесть что, в случае повторения одной цифры ты начинаешь все сначала...
Что касается ресурсоемкости, то твой вариант почти в 2 раза медленее варианта Wicked, и памяти явно больше сожрет.

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

Вот ради интереса набросал простенький вариант
PHP: 
$number = array();
$i = $count * 4;
while($i-- > 0 && count($number) < $count && $number[rand($min, $max)] = 1){}
print_r(array_keys($number));
Довольно шустрый при $max - $min <= $count, почти одинаково с алгоритмом Wicked, в случае большого диапазона мой вариант быстрее, причем с увеличиненим выборки, разница растет
min = 1, max = 100
Код: 
count | разница
3     | +25%
5     | +60% 
10    | +138%
15    | +206% 
20    | +280%
 

vovanium

Новичок
И в чем же оно "совсем" не правильно?
Нажмите для раскрытия...
В том что у тебя неравномерное распределение.
У тебя не могут выпасть числа из одной трети диапазона, плюс числа на границах диапазонов будут проседать.
 

Royal Flash

-=MaestrO=-
vovanium
Прежде чем называть чужой код дурацким - я бы на твоем месте проверил до конца свой.
PHP: 
$min = 1; $max = 3

$i = $count * 4;
В таком диапозоне какова вероятность правильной отработки твоего скрипта? Да и вывод данных кривой до ужаса: обычно ключ - это ключ, а не значение...

Что касается ресурсоемкости, то твой вариант почти в 2 раза медленее варианта Wicked, и памяти явно больше сожрет.
Нажмите для раскрытия...
Не верно. Ты хоть это проверил, чтобы написать?! Вот я проверил:
$min = 1;
$max = 3;
Royal Flsh: 0.000163058;
vovanium: 0.000130251;
Wicked: 0.000136726

$min = 1;
$max = 10000000;
Royal Flsh: 0.000113045 сек.
vovanium: 0.000123264 сек.
Wicked: 0.000118309 сек.

Усредненные данные из 1000 попыток. Т.е. из этого можно сделать вывод, что при не большом диапозоне значений мой код НЕМНОГО медленнее, а при значительном - все три варианта работают с практичесски одинаковой скорсостью.

Перед использованием любого из предложеных вариантов, необходимо проверить входящие данные, воизбежание зацикливания функций (в моем) и неккоректных ожидаемых на выходе данных (в других).
 
antson

antson

Новичок
Партнер клуба
суть генерировать случайно первое число и шаг до следующего, после перетосовать массив
потребуется сгенерировать
N случайных чисел и
если еще нужна перетосовка дополнительно 2*LOG(N)
<?
$s=0;$e=100;$c=10;

$rnd=array();
$s=$s-1;$d=$e-$s;
while($c>0 && $d>0){
$step=intval($d/$c);
$x=rand(1,$step);
$s=$s+$x;
$rnd[]=$s;
$d=$e-$s;
$c--;
}
// снуфле аррай

-~{}~ 16.03.09 21:29:

неравномерность кортежей
так при выборки 2 чисел из 100
(1,2) может быть (51-99,100) никогда
 

vovanium

Новичок
Royal Flash
$i у меня это страховка от зацикливания, которой у тебя нет
В таком диапозоне какова вероятность правильной отработки твоего скрипта?
Нажмите для раскрытия...
близка к 100%, можно увеличить ограничение по своему усмотрению, я же исходил из того что в реальной задаче диапазон будет больше количества нужных элементов, но если это будет не так, то ничего смертельного не произойдет.

Усредненные данные из 1000 попыток.
Нажмите для раскрытия...
Кто же так учил делать тесты? :) Ты про такие вещи как погрешность слышал? Особенно при измерениях времени в 100 тысячных долей секунды

Вот измерение при max = 5 (цикл 1 млн. вызовов, каждого алгоритма)
Код: 
      Wicked: 4.4464
 Royal Flash: 7.8315
    vovanium: 4.5577<br>
Вот при max = 100
Код: 
      Wicked: 4.4740
 Royal Flash: 3.8052
    vovanium: 3.7721
Твоя же функция дурацкая потому что она может зациклиться и повесить сервер, плюс вместо поиска одного числа совпавшего числа, ты ищешь 3, а теперь представь что ты захотел увеличить количество нужных чисел до 5 или 10
обычно ключ - это ключ, а не значение...
Нажмите для раскрытия...
Это всего лишь быстрый вариант исключения повторений для универсализации. Интересно было сделать однострочнуюю функциию ради эксперимента.

Ну и чтобы показать насколько "нересурсоемка" твоя функция, вот пример
PHP: 
$i = $count * 4;
do{$i1 = rand ($min, $max); $i2 = rand ($min, $max); $i3 = rand ($min, $max);} 
while($i-- > 0 && ($i1 == $i2 || $i1 == $i3 || $i2 == $i3));
то, что написал ты, но без рекурсии
при том же max = 100 выпоняется за 1.57, против твоих 3.80, при мах = 5, твоя функция выполняется 2,5 раза медленнее.
 
Войдите или зарегистрируйтесь для ответа.
Сверху