AOP_Tom2 (1021737), страница 44
Текст из файла (страница 44)
Обычно Х очень велико, поэтому невозможно хранить сразу все данные в памяти, да и отдельные записи часто настолько большие, что в памяти нельзя содержать даже и записей. Поэтому необходима эффективная процедура для выбора и записей, которая определяла бы одно из двух - — принимать или отбрасывать каждую запись при ее появлении, записывая принятую запись в выходной файл. Для решения данной проблемы разработано несколько методов. Наиболее очевидным подходом является выбор каждой записи с вероятностью и/Х. Возможно, иногда такой подход оправдан, но он дает в среднем только и записей в выборке. срр».р'с-/л),бр либо слишком большой либо слишком малой, чтобы дать необходимые результаты.
К счастью, простое преобразование "очевидной" процедуры позволяет получить то, что нужно: (1 + 1)-я запись будет выбрана с вероятностью (и — т)((Ж вЂ” Г), если т записей уже выбраны. Эта вероятность обоснована, поскольку среди всех возможных способов такого выбора и записей из Х, чтобы точно т записей было выбрано из первых ~, доля способов, когда при этом выбирается также и (г + 1)-я запись, равна (Иначе говоря, это вероятность выбора (Г+1)-й записи при условии, что и записей из У выбирались так, что среди первых г было выбрано ровно т записей. — Прим.
ред.) Идея, развитая в предыдущем разделе, немедленно приводит к следующему алгоритму. Алгоритм Б (Техника подбора выборки). Выбрать и записей случайным образом из множества Х, где О < и < Х. Б1. (Инициализация.] Присвоить ~ <- О, т ~ — О. (В этом алгоритме ги является числом записей, выбранных ранее, а г — общим числом введенных записей, с которыми мы работаем.) Б2. (Генерировать П.] Генерировать случайное число У, равномерно распределенное между О и 1. БЗ.
(Проверка.] Если (Х вЂ” г) У > и — т, перейти к шагу Бб. Б4. [Выбор.] Включить следующую запись в выборку и увеличить т и 1 на 1. Если т < и, перейти к шагу Б2. Иначе выборка является полной и алгоритм завершен. Бб. (Пропустить.] Пропустить следующую запись (не включать ее в выборку), увеличить Г на 1 и вернуться к шагу Б2.
1 На первый взгляд, алгоритм может показаться ненадежным и на самом деле неправильным, но тщательный анализ (см, упражнение, приведенное ниже) показывает, что он вполне надежен. Нетрудно проверить следующие факты. а) Вудет введено максимум )У записей (мы никогда не достигнем конца файла, пока не выберем п элементов). Ь) Выборка полностью беспристрастна. В частности, вероятность того, что любой заданный элемент выбран, как, например, последний элемент файла, равна и/Х. Утверждение (Ь) справедливо несмотря на то, что выбран (1+ 1)-й элемент ие с вероятностью и/)т', а с вероятностью, заданной в (1)! Это послужило причиной некоторой неразберихи в опубликованной литературе.
Может ли читатель объяснить это кажущееся противоречие? (Замечание. Используя алгоритм Б, следует позаботиться о наличии различных источников случайных чисел П при каждом выполнении программы во избежание зависимости между выборками, полученными в разные дни. Это можно сделать, например, выбирая каждый раз различные значения Хо в линейном конгруэнтном методе. Начальному значению Хе может быть присвоено число месяца в день выполнения программы или последнее случайное число Х, которое генерировалось при предыдущем прогоне программы.) Обычно мы не проходим все Ж записей.
В самом деле, так как указанное выше утверждение (Ь) гласит, что последняя запись выбирается с вероятностью и/1У, вероятность того, что работа алгоритма завершится да выбора последней записи, точно равна (1 — и/М). Среднее число рассмотренных записей, когда и = 2, приблизительно равно —.'Х: общие формулы даны в упр. 5 и б. Алгоритм Я и другие подобные методы обсуждаются в работе Ч. Т. Фана, Мервина Э. Мюллера и Ивана Резуха (С. Т. Рап, Мегт1п Е. Мпйег, апб 1хап ВехпсЬа, Х Ашег.
З1аа Аээос. 57 (19б2). 357 — 402). Независимо этот метод был открыт Т. Г. Джонсом (Т. С. 3опеэ, САСМ 5 (19б2), 343). Если значение У заранее неизвестно, то возникают трудности, поскольку знание точного значения о' является решающим для выполнения алгоритма Я. Допустим, необходимо случайно выбрать и записей из файла, если точно неизвестно, сколько записей в настоящее время содержится в этом файле. Можно сначала пересчитать все записи, а затем перейти к выбору и записей, но лучше так выбрать т > и начальных записей на первом проходе, чтобы гп было намного меньше У.
Тогда на втором проходе нужно будет рассмотреть только гп записей. Искусство состоит, конечно, в том, чтобы при подобном выборе в результате получить истинную случайную выборку из исходного файла. Так как заранее неизвестно, когда завершится ввод, "модель" случайной выборки из записей следует хранить на входе при первом просмотре, чтобы всегда быть готовым к его окончанию. При чтении файла мы строим "резервуар", содержащий только записи, которые образуют предварительные выборки. Первые и записей всегда будут входить в резервуар. Когда (1+ 1)-я запись введена для 1 > и, в памяти формируется таблица и индексов записей, которые были рыбраны среди первых 1 записей.
Проблемой является сохранение этого состояния с 8, увеличенным на единицу, т. е. поиск новой случайной выборки среди 1+ 1 имеющихся известных сейчас записей. Нетрудно видеть, что новую зались следует включить в выборку с вероятностью и/(1+ 1); при этом она заменит случайный элемент предыдущей выборки. Итак, описанную работу выполняет следующий алгоритм. Алгоритм К (Резервуар выбора). Выбрать случайно п записей из файла неизиестного размера > и, п > 0 задано. Дополнительный файл назовем резервуаром, содержащим все записи, которые являются кандидатами для окончательной выборки.
Алгоритм использует таблипу различных индексов 1[Я для 1 < у < и, каждый из которых указывает на одну из записей в резервуаре. К1. [Инициализация,] Введем первые и записей и скопируем их в резервуар. Присвоим 1[/] т — у для 1 < т < и и присвоим 1 т- т т — и. (Если файл бусдет выборкой, имеющей меньше и записей, то, конечно, необходима будет прервать выполнение алгоритма и сообщить о неблагоприятном исходе. В алгоритме индексы 1[1], ..., 1[п] указывают записи в текущей выборке; тп является размерностью резервуара, а 1 — номером входных записей, .рассмотренных до сих пор.) К2. (Конец файла?] Если записей на ввод больше нет, то перейти к шагу Кб.
КЗ. [Генерирование и проверка.] Увеличить 1 на 1, затем генерировать случайное целое число Аб между 1 и С (вк;почительно). Если ЛХ > и, перейти к шагу К5. К4. [Увеличить ре,эервуар.] Копировать следуюнтую запись входного файла в резервуар, увеличить т на 1 и присвоить 1[А(] т — тп.
(Запись, предварительно указанная как 1[тт1], заменяется в выборке новой записью,) Возврат к шагу К2. Кб. [Пропустить.] Пропустить следуюшую запись входного файла (не включать ее в резервуар) и возвратиться к шагу К2, Кб. [Следующий просмотр.] Упорядочить индексы 1 таблицы входов так, чтобы 1(1] « . 1[п], затем тщательно разобрать резервуар, копируя записи с этими индексами в выходной файл, который фиксирует окончательный выбор. 1 Алгоритм В предложен Аланом Дж.
Вотерманом,(А1ап О. ЪУагегшап). Читатель при желании может вьпюлнить упр. 9. используя эти операции. Если 'записи достаточно короткие, конечно, излишне помещать их в резервуар. п записей текущего файла можяо постоянно хранить в памяти, и алгоритм станет более простым (см. упр. 10). Относительно алгоритма К возникает естественный вопрос: "Какова предполагаемая размерность резервуара?". В упр. 11 показано. что среднее значение ттт точно равно тт(1+ Нтх — Н„), т. е. приблизительно п(1-ь 1п(А//и)).
Так, если Ат/п = 1000. в резервуаре будет содержаться лишь окало 1/125 целых записей исходного файла. Заметим, что алгоритмы Я и К можно применять, чтобы получать выборки для различных независимых классов одновременно. Например, если есть большой файл фамилий н адресов постоянных жителей СШЛ, можно случайным образам сделать выборку точно 10 жителей из каждого иэ 50 штатов, не просматривая 50 раэ файл и не выпалния первую сортировку файла по штатам. Возможно значительное улучшение шпаритмов Я и К, когда п/Ат малб.
Скажите, сколько записей можно пропустить, вместо того чтобы решать, пропускать ли каждую запигть если генерируется единственная случайная величина? (См. упр. 5.) Проблема выборки может быть рассмотрена как вычисление случайного со"теитапил в соответствии с обычным определением сочетания Ат по и (см. раздел 1.2.6). Рассмотрим задачу вычисления случайной пврестпанввки 1 обьектов. Назовем ге задачей перемешиванил (тасоваиил), так как, например, тасование колоды карт является ничем иным, как ее случай»ной перестановкой. Достаточно легко убедить любого игрока в карты, что традиционная процедура тасования карт ужасно несовершенна.
Нет надежды получить таким методом каждую из 1! перестановок с примерно равными вероятностями. Рассказывают, что знаток игры в бридж использует это обстоятельство, когда принимает решение, стоит ли ему блефовать. По крайней мере семь "перемешиваний" колоды из 52 карт происходит с вероятностью, примерно равной 10% от вероятности получить эти перемешивания при равномерном распределении, в то время как 14 гэучайных перемешивапий имеют вероятность появления, примерно равную вероятности их назучения при равномерном распределении [см. А!«!опэ а»»«! П»асопнб АМ51 93 (1986), 333-348]. Если 1 малб, можно получить случайную перестановку очень быстро, генерируя случайное целое число между 1 и г!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
