CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Вычисление эксцесса и коэффициентов асимметрии заданной выборки. (42617 hits)
#Замена символа строки. (437947 hits)
#Поразрядная сортировка массива подсчетом. (127369 hits)
#Доступ ко всем полям и методам. (54062 hits)
#Сортировка выбором, общий подход. (67812 hits)
#Улучшение быстрой сортировки. (71154 hits)
#Выборка всех записей таблицы. (29827 hits)
#Обертки для массивов. (35761 hits)
#Циклический сдвиг массива или строки - 3 уникальных алгоритма. (370966 hits)
#Бинарный поиск в массиве и его разновидности. (158787 hits)
#Вычисление значения полинома. (57606 hits)
#Постепенное затемнение. (47070 hits)
#Рисование линии (по Брезенхэму). (30234 hits)
#Создание простейшей таблицы. (33488 hits)
#Загрузчик классов. (39600 hits)
#Преобразование сумм из цифрового представления в строковое. (167259 hits)
#Вычисление минимального / максимального значения. (70401 hits)
#Перестановка фрагментов строки(или одномерного массива). (56163 hits)
#Рисование линии. (35400 hits)
#Программное создание ссылок. (96371 hits)


Главная >> Каталог задач >> Числа >> Случайные числа >>

Случайный выбор элемента при неизвестном их количестве

Aвтор:
Дата:
Просмотров: 33134
реализации(php: 1шт...) +добавить

Как можно выбрать один из n объектов случайным образом, если объекты предъявляются последовательно, но их количество n заранее неизвестно?

Задача достаточно актуальна в программировании при работе с файловой системой: как наиболее быстро выбрать случайный файл в директории?

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

Для таких случаев существует быстрый и красивый алгоритм:

Первую строку мы выбираем всегда, вторую — с вероятностью 1/2, третью — с вероятностью 1/3 и так далее. К концу процесса вероятность выбора всех строк окажется одинаковой(1/n, где n - неизвестное общее количество элементов)!

Таким образом, получим:
 псевдокод: случайный выбор при неизвестном количестве  ссылка
  1. i = 0
  2. while (<пока есть непройденные элементы>)
  3. /* randint - случайное число "от" и "до" */
  4. if randint(1, ++i) == 1
  5. choice = i
  6.  
  7. /* после выполнения имеем в choice -
  8. искомый случайный выбор */

Реализации:

php(1)   +добавить

1) Чтение случайного файла в директории на php, code #83[автор:this]