CodeLAB
на главную карта сайта обратная связь
каталог | задачи | паттерны | исходники | стат | форумы | ссылки
 гость
искать в
Главная >> Каталог задач >> Числа >> Случайные числа >> Случайный выбор элемента при неизвестном их количестве

<< назад
распечатать обсудить >>


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

Aвтор: this
Дата: 10.06.2004
Просмотров: 24240
Рейтинг: 3/7,4.9(3018)
+
реализации(исходники) +добавить

Как можно выбрать один из 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) Чтение случайного файла в директории, code #83[автор:this]


<< назад наверх
распечатать обсудить >>

 
каталог | задачи | паттерны | исходники | стат | форумы | карта сайта | контакты | ссылки 
© 2000-2018 CodeLAB Group
  Все права защищены
Страница сгенерирована за 0.012625 секунд
Количество запросов к БД: 14, gzip: 9.5kb/32.6kb(71%)