?

Log in

No account? Create an account
Записи Друзья Календарь Профиль назад назад далее далее
Записки одного программиста
stkorn
stkorn
Задачка
   Сегодня товарищ загадал мне интересную задачку на программирование. А я, как известно, обожаю задачки на программирование! И вовсе не потому, что математику я всю уже забыл, а физику никогда толком не знал. ;))

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



   Вообщем, вот условие:

•  Дан скалярный массив из, например, 10.000 элементов.
•  Нужно обеспечить перебор всех элементов массива - произвольным случайным образом. Но так, чтобы каждый элемент встретился в переборе только один раз.

   И прежде чем вы начнёте её решать, одно примечание: В задаче критично время перебора - то есть выбирать элементы надо как можно быстрее.



   Жду ваших решений в коментах.. ;)
 

Метки:

21 комментарий или Оставить комментарий
Comments
spamsink From: spamsink Date: Июль, 15, 2008 03:43 (UTC) (Ссылка)
Какие ограничения на дополнительную память, на модификацию массива? А то ведь есть стандартный метод тасования: от 1 до N поменять i-й элемент со случайным.
stkorn From: stkorn Date: Июль, 15, 2008 05:30 (UTC) (Ссылка)
Хорошее решение :)
Но есть ещё красивее, когда заранее тасовать массив не надо, и каждый элемент выбирается налету..
spamsink From: spamsink Date: Июль, 15, 2008 05:37 (UTC) (Ссылка)
Да, есть и такое, причем заранее знать размер массива необязательно - работает для выдачи случайной строки из файла. Берем в переменную первый элемент, с вероятностью 1/2 меняем на второй, с вероятностью 1/3 - на третий... Какой останется в момент окончания данных, тот и возвращаем.
spamsink From: spamsink Date: Июль, 15, 2008 05:39 (UTC) (Ссылка)
Ой, о чем это я?
stkorn From: stkorn Date: Июль, 15, 2008 05:41 (UTC) (Ссылка)
Как это "с вероятностью 1/2 меняем на второй"?
Выборка должна быть равномерно-случайной!
spamsink From: spamsink Date: Июль, 15, 2008 06:15 (UTC) (Ссылка)
Этот метод очень хорош для возврата равновероятной случайной строки из файла произвольной длины.
spamsink From: spamsink Date: Июль, 15, 2008 05:43 (UTC) (Ссылка)
Если массив все еще можно менять, то примерно то же самое: выбираем случайный из N (его и вернем), меняем с последним. В следующий раз выбираем случайный из N-1, меняем с предпоследним, и т.п.
stkorn From: stkorn Date: Июль, 15, 2008 06:02 (UTC) (Ссылка)
Зачот! :)
Временно скрыл, пусть остальные подумают..
o4kapuk.ru From: o4kapuk.ru Date: Июль, 15, 2008 06:05 (UTC) (Ссылка)
Бля… Поздно, у меня теперь не получится подумать :(
stkorn From: stkorn Date: Июль, 15, 2008 06:07 (UTC) (Ссылка)
:((
stkorn From: stkorn Date: Июль, 15, 2008 14:57 (UTC) (Ссылка)
Все, тайна раскрыта! :)
o4kapuk.ru From: o4kapuk.ru Date: Июль, 15, 2008 05:57 (UTC) (Ссылка)
select item from table order by rand();
stkorn From: stkorn Date: Июль, 15, 2008 06:03 (UTC) (Ссылка)
:))) Нифига, у нас скалярный массив, а не таблица в базе данных!
frolin From: frolin Date: Июль, 15, 2008 06:42 (UTC) (Ссылка)
Я не программист, но попробую - я создал бы еще один массив из десяти тыщ упорядоченных чисел (1,2,3 и так далее) потом запустил бы цикл тыщ на пять который бы брал два числа c индексом rnd и менял бы их местами. Потом просто выдал бы цифры из первого массива с индексом из второго массива. фигня конечно бы получилась - но она бы работала.
stkorn From: stkorn Date: Июль, 15, 2008 06:47 (UTC) (Ссылка)
Мне кажется, так перемешивание было бы меньшим, чем если запустить цикл на все 10.000 и каждый i-й элемент поменять местами со случайным. Но есть красивое решение без предварительного упорядочивания, когда каждый следующий элемент выбирается случайно налету :)
happybullshit From: happybullshit Date: Июль, 15, 2008 09:30 (UTC) (Ссылка)
Двусвязный список, rand() % (10000 - номер итерации), удаляем элемент из списка.
happybullshit From: happybullshit Date: Июль, 15, 2008 09:40 (UTC) (Ссылка)
не, не в кассу...
naid From: naid Date: Июль, 15, 2008 12:55 (UTC) (Ссылка)

хм, а если так?

взять элемент рандомно
записать в отдельный array в [0]
свопнуть ячейку с последней ячейкой массива
сделать массив меньше на 1 (то есть затереть первую)
взять элемент рандомно.... :)

если бы random умел обрабатывать числа в диапазоне от n до m, то вместо пп.2 и 4 можно было бы m присвоить m-1 - или, если нам нужна хронологически упорядоченная выборка, ячейку свопать с array[n], n=n+1. я не знаю, умеет ли он это делать, но написать такой рандом выгодней, чем перетряхивать массив.
stkorn From: stkorn Date: Июль, 15, 2008 14:53 (UTC) (Ссылка)

Re: хм, а если так?

Абсолютно верно!
naid From: naid Date: Июль, 15, 2008 18:38 (UTC) (Ссылка)

простая задачка.

я, кстати, ошиблась в формулировке - затирать надо не первую, а последнюю, ту, в которую мы перенесли уже найденный элемент. но это именно в формулировке ошибка :)

а ещё задач, посложнее, нет? *)
variate From: variate Date: Июль, 15, 2008 15:14 (UTC) (Ссылка)
Если взять большое "случайное" простое число p, то выдавая вместо n-ого элемента элемент под номером np mod length(A) реализуем требуемое в задаче. Вместо простого числа можно видимо брать любое взаимопростое с length(A). Это если я конечно помню теорию чисел. Весь вопрос в требуемой случайности. А так получится что генерация индекса требует одно умножение и одно деление с остатком. Если повезет, то на суперскалярных архитектурах это реализуется за время пока предыдущий элемент вытягивается из памяти.
21 комментарий или Оставить комментарий