Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 45
Текст из файла (страница 45)
3 Алгоритм В предложен Аланом Дж. Ватерманом (А!ап 6. 1рагегшап). Читатель при желании может выполнить упр. 9, используя зти операции. Если записи достаточно короткие, конечно, излишне помещать их в резервуар. п записей текущего файла можно постоянно хранить в памяти, и алгоритм станет более простым (см. упр. 10). Относительно алгоритма В возникает естественный вопрос: "Какова предполагаемая размерность резервуара?". В упр, 11 показана. что среднее значение т точно равно п(1 + Ньт — Н„), т.
е, приблизительно и[1+ 1п(Х/и)). Так, если Х/ц = 1000, в резервуаре будет содержаться лишь около 1/125 целых записей исходного файла. Заметим, что алгоритмы Б и К можно применять, чтобы получать выборки для различных независимых классон одновременно. Например, если есть большой файл фамилий и адресов постоянных жителей США, можно случайным образом сделать выборку точно 10 жителей из каждого из 50 штатов, не просматривая 50 раз файл и не выполняя первую сортировку файла по штатам.
Возможно значительное улучшение алгоритмов Б и Н, когда и/!У малб. Скажите, сколько записей можно пропустить, вместо того чтобы решать, пропускать ли каждую заппсь, если генерируется единственная случайная величина? (См. упр. 6.) Проблема выборки может быть рассмотрена как вычисление случайного сочетания в соответствии с обычным определением сочетания Х по и (см. раздел 1,2.6). Рассмотрим задачу вычисления случайной перестановки 1 объектов. Назовем ее задачей перамешиваиил (шасоеаиия). гак как, например, тасование колоды карт является ничем иным, как ее случайной перестановкой.
Достаточно легко убедить любого игрока в карты, что традиционная процедура тасоваиия карт ужасно несовершенна. Нет надежды получить таким методом каждую из В перестановок с примерно равными вероятностями. Рассказывают, что знаток игры в бридж использует это обстоятельство, когда принимает решение, стоит ли ему блефовать. По крайней мере семь "перемешиваний" колоды из 52 карт происходит с вероятностью, примерно равной 10% от вероятности получить эти перемешивания при равномерном распределении, в то время как 14 случайных перемешиваний имеют вероятность появления, примерно равную вероятности их получения при равномерном распределении (см.
А!8оив ап»! В!асан!в, АММ 93 (1986), 333 — 348). Если ! малб, можно получить случайную перестановку очень быстро, генерируя случайное целое число между 1 и В. Например, когда ! = 4, случайного числа между 1 и 24 достаточно, чтобы выбрать случайную перестановку из табл|и»ы всех возможностей. Но для больших ! необходимо быть более осторожным, если требуется, чтобы каждая перестановка была равновероятной, так как !! намного больше точности отдельного случайного числа. Подходящая процелура перемешиваиия мажет быть получена с помощью уже упоминаемого алгоритма 3.3.2Р, который дает простое соответствие между каждой из !! воз»1ож1гых перестановок и последовательностью чисел (сост,, ..,с» 1) с 0 < сз < З. Можно легко получить такое множество случайных чисел, и это соответствие можно использовать для получения случайных перестановок.
Алгоритм Р (Перемешиваиие). Пусть Х,„Хю ..., Х~ — множество ! чисел для перемешиааиия. Р1. [Инициализация.) Присвоить»»- 6 Р2. (Генерирование !7.) Генерировать случайное число ~', равномерно распределенное между О и 1. РЗ. (Замена.) Присвоить /с +- (7(7) + 1. (Сейчас Ь вЂ” случайное целое число между 1 и ~'. В упр. 3.4.1-3 объясняется. что деление на 7' ие следует использовать для вычисления Ь.) Заменим Х» +э Х . Р4.
!Уменыпение 7'.] Уменьшить > на 1. Если ! > 1, возвратиться к шагу Р2. 1 Впервые этот алгоритм опубликовали Р. А. Фишер и Ф. Ятс (В. А. РВЬег апд Е. Ъагев, В!а»!яНса! ТаЫек (1люйоп, 1938). Ехашр!е 12) на обычном языке, а Р. Дурстеифелд — иа языке компьютерном (В.. Впгвтеп(е!6, САСМ 7 (1964), 420). Чтобы просто генерировать случайную перестановку (1,...,!) вместо перемешивания заданной последовательности (Хы... „Л,), можно избежать операции замены Х»»+ Х,, выполнив увеличение 7' ат 1 до ! и присвоин Хт +- Л», Х»»- ~' (см.
О. Е. Кпи»Ь, ТЬе Вгапуаг»! СгарЬВаэе (Неи Уогра АСМ Ргеав, 1994), 104). Р. Салфи (В, Ва!6, СОЛГРВТАТ 1974 (Ъ!еппа, 1974), 28-35) указал, что алгоритм Р не имеет возможности генерировать более и» различных перестаиоиок, когда мы получаем равномерно распределенные о' из линейной конгруэнтной последовательности по модулю и» или используем рекуррентное соотношение (7„.~~ = 7((7„), для которого (/» может дать только гп различных значений, потому что окончательная перестановка в таком случае полностью определяется первыми генерированными значениями с/, Так, например, если гп = 2эз, определенные перестановки из 13 элементов никогда не появятся, поскольку 13! ж 1.4о х 2ээ.
В большинстве случаев на самом деле нет иеобходнмосгпи получать все 13! перестановок, но огорчает, что исключение данных перестановок определяется фактически простым математическим правилом, таким как решетчатая структура (см. раздел 3.3.4). Эта проблема не возникает, когда используется генератор Фибоначчи с запаздыванием, цодобный 3.2.2-(7), с достаточно длинным периодом. Но даже таким метопом невозможно получать все перестановки постоянно, если нельзя точно закать по крайней мере П различных начальных значений для инициализации генератора. Другими словами, не существует возможности получить 1БВ истинно случайных двоичных разрядов на выходе, если не получить )31! истинно случайных двоичных разрядов на вхоле.
Как говорится в разделе 3.5, не стоит из-за этого огорчаться. Алгоритм Б можно легко преобразовать для получения случайной перестановки случайных сочетаний (см. упр. 15). Случайные объекты комбинаторики других видов (например, разбиения) рассматриваются в разделе 7.2 н в книге СотЫпагаг)а) А)яогйбшэ Ьу К([еп)1п)э апс[ %11( (Неж Ъог[с Асв$еш1с Ргеээ, 1975). УПРАЖНЕНИЯ 1. [Мтэ[ Объясните (1). 2. [во[ .Докажите, что алгоритм Б никогда ие пытается прочесть более Х записей своего входного файла, ь 3, [йй[ (1+1)-я запись в алгоритме Б выбирается с вероятностью (и-гп)/(51-1), а не и/Х, аднако алгоритм требует, чтобы выборка была беспристрастной, поэтому каждая запись должна выбираться с одинаковой вероятностью.
Почему оба эти утверждения правильны? 4. [МЮ) Пусть р(ш,т) — вероятность того, что выбрано точно ш записей среда первых 1 в методе отбора выборок. Покажите непосредственно нз алгоритма Б, что р(т1)=( )~ )//( ) Л эО<1<Х 5. [ЛИэ') Чему равно среднее значение Г по завершении алгоритма Б? (Другимн словами, скалько из ?э' записей будет просмотрено в среднем, прежде чем выборка станет полной?) 6. [мйэ[ чему равно среднеквадратичное отклонение значении, вычисленного в упр.
5? 7. [Мяб] Докажите, что любой заданный выбор 0 записей из множества Х записей может быть получен алгоритмом Б с вероятностью 1/('~). Следовательно, выборка является совершенно беспристрастной. 8. [Мзэ[ (Д. С. Виттер (Л. Б. Пыег).) Алгоритм Б производит одну равномерно распределенную случайную величину лля каждой входной записи. Цель этого упражнения— рассмотреть балее эффективный подход, при котором можно быстрее вычислить точное число Х входных записей, которые следует пропустить, прежде чем сделать первый выбор. э) Чему равна вероятность того, что Х > э, э задано? Ь) Покажите, что результат (а) позволяет выполнить вычисление Х, генерируя только одну равномерно распределенную случайную величину 11, и произвсдит 0(Х) других вычислений.
с) Покажите, что можно также присвоить Л 4- ппп(ук,Ук-!,...,УА- -!!), где 2! незавнсимь! и каждое 1'", является случайным целым числом в области 0 < И < 2, 6) Найдите максимэльную скорость, т. е. покажите, что Х также может быть вычислено в среднем за О(1) шагов, если использовать "метод втискивания", подобный 3.4,1 — (18).
9. [16] Пусть и = 3. Если алгоритм В. применяется к файлу, содержащему 20 записей, которые пронумерованы от 1 до 20, н если случайные числа, генерированные на шаге КЗ, равны соответственно 4, 1,6, 7, 5, 3, 5, 11, 11, 3, 7, 9, 3, 11, 4, 5, 4, какая запись попадет в резервуар? Какая из ннх окажется в окончательной выборке? 10. (15] Преобразуйте алгоритм К так, чтобы обойтись без резервуара, предполагая, что и записей текущей выборки можно хранить в памяти. ь 11.
(М65] Пусть р — вероятность того, что точно пз элементов занесены в резервуар в течение первого прохода алгоритма к. Определите производящую функцию с(3) = р 3 и найдите среднее значение и среднеквадратичное отклонение. (Используйте ндеи из раздела 1.2.10.) 12, (МЯб] Суть алгоритма Р состоит в том, что любую перестановку т можно однозначно записать ввк результат транспонирования в виде т = (а!2)... (азз)(022), где 1 < 07 < 2 для 2 > 7' > 1. Докажите, что существует также единственное представление вида к = (522ИЬ33)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
