Выбор случайной строки из файла
Проблема
Требуется прочитать из файла случайную строку.
Решение
Воспользуйтесь функцией
rand и переменной $. (текущим номером строки):
srand;
rand($.) < 1 && ($line = $_) while <>;
# $line - случайно выбранная строка
Комментарий
Перед вами — изящный и красивый пример неочевидного решения. Мы читаем все строки файла,
но не сохраняем их в памяти. Это особенно важно для больших файлов. Вероятность выбора каждой
строки равна 1/N (где N — количество прочитанных строк).
Следующий фрагмент заменяет хорошо известную программу fortune:
$/ = "%%\n";
$data = '/usr/share/games/fortunes';
srand;
rand($.) < 1 && ($adage = $_) while <>;
print $adage;
Если вам известны смещения строк (например, при наличии индекса) и их общее количество,
можно выбрать случайную строку и перейти непосредственно к ее смещению в файле. Впрочем, индекс
доступен далеко не всегда.
Приведем более формальное пояснение работы данного алгоритма. Функция rand ($.) выбирает
случайное число от 0 до текущего номера строки. Строка с номером N сохраняется в возвращаемой
переменной с вероятностью 1/N. Таким, образом, первая строка сохраняется с вероятностью 100%,
вторая — с вероятностью 50%, третья — 33% и т. д. Вопрос лишь в том, насколько это честно для
любого положительного целого N.
Начнем с конкретных примеров, а затем перейдем к абстрактным.
Разумеется, для файла из одной строки (N = 1) все предельно честно: первая строка сохраняется
всегда, поскольку 1/1 = 100%. Для файла из двух строк N = 2. Первая строка сохраняется всегда;
когда вы достигаете второй строки, она с вероятностью 50% заменяет первую. Следовательно, обе
строки выбираются с одинаковой вероятностью, и для N = 2 алгоритм тоже работает корректно. Для
файла из трех строк N = 3. Третья строка сохраняется с вероятностью 1/3 (33%). Вероятность
выбора одной из двух первых строк равна 2/3 (66%). Но как показано выше, две строки имеют
одинаковую вероятность выбора (50%). Пятьдесят процентов от 2/3 равны 1/3. Таким образом,
каждая из трех строк файла выбирается с вероятностью 1/3.
В общем случае для файла из N+1 строк последняя строка выбирается с вероятностью 1/(N+1),
а одна из предыдущих строк — N/(N+1). Деление N/(N+1) на N дает вероятность 1/(N+1) для каждой
из N первых строк и те же 1/(N+1) для строки с номером N+1. Следовательно, алгоритм корректно
работает для любого положительного целого N.
Нам удалось случайным образом выбрать из файла строку со скоростью, пропорциональной
количеству строк в файле. При этом максимальный объем используемой памяти даже в худшем
случае равен размеру самой длинной строки.
См. также
Proverte kod v komentariyah gde pro list tam oshibki detskie
Оставить комментарий:
|
|