Re[3]: magic random - Коллеги, улыбнитесь

Как быстро заполнить массив рандомными числами без повторов?

int a[36];
// заполнить рандомно, числа от 0 до 35 включительно.
-----------------
Мой способ занимает несколько минут, можно ли уменьшить время?

отсюда

я нахожусь в некотором замешательстве

Здравствуйте, DTB, Вы писали:

DTB>

DTB>Как быстро заполнить массив рандомными числами без повторов?

DTB>int a[36];
DTB>// заполнить рандомно, числа от 0 до 35 включительно.
DTB>-----------------
DTB>Мой способ занимает несколько минут, можно ли уменьшить время?

DTB>отсюда

DTB>я нахожусь в некотором замешательстве

кейборд скилс надо качнуть парню ...

Здравствуйте, DTB, Вы писали:

DTB>

DTB>Как быстро заполнить массив рандомными числами без повторов?

DTB>int a[36];
DTB>// заполнить рандомно, числа от 0 до 35 включительно.
DTB>-----------------
DTB>Мой способ занимает несколько минут, можно ли уменьшить время?

DTB>отсюда

DTB>я нахожусь в некотором замешательстве

все вполне логично. Он скорей всего генирирует очередное число и проверяет не бы ло ли его в массиве уже. Соответственно последние числа будут подбираться довольно долго, пока генератор не выдаст наконец числа которых небыло.

WBR, K.O.

N_>все вполне логично. Он скорей всего генирирует очередное число и проверяет не бы ло ли его в массиве уже. Соответственно последние числа будут подбираться довольно долго, пока генератор не выдаст наконец числа которых небыло.

если комп не ХТ то даже в этом случае несколько минут не будет ну никак

Но что-то мне кажется что и на ХТ такого не будет даже при таком подходе.

N_>все вполне логично. Он скорей всего генирирует очередное число и проверяет не бы ло ли его в массиве уже. Соответственно последние числа будут подбираться довольно долго, пока генератор не выдаст наконец числа которых небыло.

N_>WBR, K.O.

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

$ cat kard.pl 
my @list = ();
while (scalar(@list) < 36) {
  my $next;
  do {
    $next = int(rand(36));
  } while (scalar(grep($_ == $next, @list)) > 0);
  push(@list, $next);
}
print join(" ", @list) . "\n";



$ time perl kard.pl 
6 15 33 18 19 21 9 11 31 28 10 16 24 22 27 35 7 4 0 29 14 13 23 2 30 32 5 17 12 1 20 25 34 26 3 8

real    0m0.006s
user    0m0.000s
sys     0m0.000s

Здравствуйте, DTB, Вы писали:

DTB>

DTB>Как быстро заполнить массив рандомными числами без повторов?
DTB>int a[36];
DTB>// заполнить рандомно, числа от 0 до 35 включительно.
DTB>-----------------
DTB>Мой способ занимает несколько минут, можно ли уменьшить время?

DTB>отсюда

DTB>я нахожусь в некотором замешательстве

наверно он сначала гененерирует 36 случайных, а потом проверяет, удовлетворяют они или нет условию "без повторов".

Здравствуйте, dilmah, Вы писали:
D>да ладно. Вот тупейший код на перле работающий по твоему методу -- даже не использует хэши а честно линейно проходит много раз списки.

Скорей всего алгоритмы рандома раздные, мож у автора менее равномерный и некоторые числа выдает крайне редко.

Здравствуйте, saturas, Вы писали:

DTB>>я нахожусь в некотором замешательстве

S>наверно он сначала гененерирует 36 случайных, а потом проверяет, удовлетворяют они или нет условию "без повторов".

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

Здравствуйте, Nik_1, Вы писали:

N_>Скорей всего алгоритмы рандома раздные, мож у автора менее равномерный и некоторые числа выдает крайне редко.

автор уточнил:

Я создавал рандомное число, зависимое от времени. Проверял есть ли такое в массиве и повторял снова.

S>>наверно он сначала гененерирует 36 случайных, а потом проверяет, удовлетворяют они или нет условию "без повторов".

DTB>даже если так, минут скорей всего там тоже не будет. можно предположить, что это опечатка, не минут, а секунд, но даже это особо ситуацию не исправляет

такой метод требует примерно 36^36 / (36!) попыток сгенерировать 36 случайных. Даже если такиъх попыток делать миллиард в секунду, то понадобится 80 часов:

$ { printf '36 ^ 36 '; seq 1 36 | xargs printf '/ %d'; echo '/ (10 ^ 9) / 3600'; } | bc -l
79.44240398206811060520

Здравствуйте, saturas, Вы писали:

S>Здравствуйте, Nik_1, Вы писали:

N_>>Скорей всего алгоритмы рандома раздные, мож у автора менее равномерный и некоторые числа выдает крайне редко.

S>автор уточнил:

S>

S>Я создавал рандомное число, зависимое от времени. Проверял есть ли такое в массиве и повторял снова.

интересно как, на ум приходит только такой фейл:

for(;;)
{
   srand(time(NULL));
   printf("%d, ", rand());
}

Здравствуйте, DTB, Вы писали:

S>>наверно он сначала гененерирует 36 случайных, а потом проверяет, удовлетворяют они или нет условию "без повторов".

Если брать случайным числом текущую секунду то примерно в половине случаев такой "алгоритм" будет работать более минуты.

DTB>

DTB>for(;;)
DTB>{
DTB>   srand(time(NULL));
DTB>   printf("%d, ", rand());
DTB>}
DTB>

ведь повторяться будет

Здравствуйте, Kaifa, Вы писали:

K>ведь повторяться будет

раз в секунду будет меняться, о том и речь

Здравствуйте, DTB, Вы писали:

DTB>

DTB>Как быстро заполнить массив рандомными числами без повторов?

DTB>int a[36];
DTB>// заполнить рандомно, числа от 0 до 35 включительно.
DTB>-----------------
DTB>Мой способ занимает несколько минут, можно ли уменьшить время?

DTB>отсюда

DTB>я нахожусь в некотором замешательстве

при каждом вызове рэндом функции менять диапазон
это работает?

Здравствуйте, yoriсk.kiev.ua, Вы писали:

YKU>Здравствуйте, DTB, Вы писали:

S>>>наверно он сначала гененерирует 36 случайных, а потом проверяет, удовлетворяют они или нет условию "без повторов".

DTB>>даже если так, минут скорей всего там тоже не будет. можно предположить, что это опечатка, не минут, а секунд, но даже это особо ситуацию не исправляет

YKU>Если брать случайным числом текущую секунду то примерно в половине случаев такой "алгоритм" будет работать более минуты.

Отаке способ
1. Сначала честно заполнить по порядку
for (int i = 0; i < 36; i++)
a[i] = i;
2. А теперь какой-нибудь random_shuffle

Здравствуйте, ---Odysseus---, Вы писали:

O>при каждом вызове рэндом функции менять диапазон
O>это работает?

Тут наверное юмор в том, что это классическая задача (перетасовка колоды карт), решения расписаны например в Кнуте.

D>такой метод требует примерно 36^36 / (36!) попыток сгенерировать 36 случайных. Даже если такиъх попыток делать миллиард в секунду, то понадобится 80 часов

В переводе на стандартное центаврийское время это будет несколько минут

Здравствуйте, DTB, Вы писали:

DTB>[q]
DTB>Как быстро заполнить массив рандомными числами без повторов?

DTB>int a[36];
DTB>// заполнить рандомно, числа от 0 до 35 включительно.

Кажется, это было в каком-то фильме, название типа "Карты...

	От:	DTB
	Дата:	31.08.10 11:29
	Оценка:

	От:	sashka
	Дата:	31.08.10 11:34
	Оценка:

	От:	Nik_1
	Дата:	31.08.10 11:37
	Оценка:	-2

	От:	Kaifa
	Дата:	31.08.10 11:48
	Оценка:

	От:	dilmah
	Дата:	31.08.10 11:56
	Оценка:

	От:	saturas
	Дата:	31.08.10 11:59
	Оценка:	2 (2) +1

	От:	yoriсk.kiev.ua
	Дата:	31.08.10 12:14
	Оценка:

От:	bnk	http://unmanagedvisio.com/
Дата:	31.08.10 13:06
Оценка:

	От:	Skleroz
	Дата:	01.09.10 01:07
	Оценка:

От:	midcyber	肏
Дата:	01.09.10 07:20
Оценка: