Nickolay.info. Алгоритмы. Выбор случайной строки за 1 проход по файлу

Думаю, актуальность задачи сомнений не вызывает - выдача пользователю случайных сообщений из базы, всякого рода "шутки дня" на Web-страницах, и ещё миллионы приложений.

Разумеется, не проблема на любом языке прочитать весь массив строк в файл, подсчитав заодно их количество, потом выбрать номер случайной строки стандартной функцией с именем вроде rand или random, потом показать нужную строку. Однако, во-первых, читать весь файл очень неэкономно, во-вторых, такой подход (чтение-то происходит в оперативную память, причём всего файла) просто не будет работать на действительно больших базах (а что, если у нас миллион строк?).

Рецепт очень краток: читать файл построчно и с вероятностью, обратно пропорциональной числу прочитанных строк, сохранять текущую строку в качестве случайной.

Расшифруем его и покажем примеры.

Применив минимум теории вероятностей, получим, что вероятность выпадения любого числа из N имеющихся чисел равна 1/N. Это означает, в частности, что если мы будем читать строки по одной и подсчитывать в переменной i количество уже прочитанных строк, то мы можем с вероятностью 1/i считать текущую строку случайной. Иначе говоря, заведём для искомой случайной строки переменную res, а очередную строку файла s будем сохранять в res при условии, что случайное число из диапазона [0,кол-во прочитанных строк-1] (нумерация в большинстве языков ведётся с нуля!) равно нулю. При таком подходе, после чтения первой строки файла мы с вероятностью, равной единице, сохраним в переменной res эту строку. После чтения второй строки она запишется в переменную res с вероятностью в 50%, третья строка - с вероятностью 33% и т.д.

Конечно, мы всё равно прочитаем весь файл - но построчно! Да, наверное, и нельзя придумать алгоритма, который выбирает строку из файла, никуда её не читая. Особенно если не узнавать заранее общее число строк.

Реализуем сказанное на Паскале. Сначала запишем в текущую папку файл, состоящий из 10000 строк. Для простоты тестирования каждая строка будет содержать только свой номер в файле, начиная с единицы.

const n=10000; {Число строк}
var f:text;
    i:integer;
begin
 assign (f,'data.txt');
 rewrite (f);
 for i:=1 to n do writeln (f,i);
 close (f);
end.

Теперь напишем программку, выбирающую случайные строки. Реализация выбора вынесена в отдельную функцию randomstring, она вызывается 100 раз, чтобы получить 100 случайных чисел. Как и во многих языках, на Паскале перед генерацией цепочки случайных чисел нужно инициализировать генератор вызовом стандартной процедуры randomize;.

uses crt;
const k=100;
var f:text;
    i:integer;

function randomstring:string;
var s,res:string;
    i:integer;
begin
 i:=0;
 while not eof(f) do begin
  readln (f,s);
  inc(i);
  if random (i) = 0 then res:=s;
 end;
 randomstring:=res;
end;

begin
 randomize;
 assign (f,'data.txt');
 for i:=1 to k do begin
  reset (f);
  delay (20);
  write (randomstring,' ');
 end;
 close (f);
 reset (input);
 readln;
end.

Вот одна из выдач этой программы.

1079 1507 2037 710 1849 3348 4727 1853 3956 9397 1097 1489 3080 7978 7876 123 59
11 9502 1575 3764 5617 8348 9555 4905 216 3653 5308 1437 8670 6249 4729 9429 5699 
431 8755 3675 5207 6263 9348 5145 4212 9637 3360 1006 7851 5027 3352 4287 8144
 3376 2032 1304 679 2732 6040 6935 2801 3758 5702 4041 7501 8881 9412 1456 2934
4771 2639 8412 6887 5794 1597 3930 4759 5336 2278 6829 1980 640 1595 3037 62 305
 3080 1570 1172 648 3783 7137 1859 4877 7138 5222 5730 8346 2355 4757 42 1988 325 180

Реализация алгоритма в виде скрипта на PHP тоже не создаст трудностей. Кинем файл data.txt в папку локалхоста Windows c:\Inetpub\wwwroot и создадим там же файл со скриптом frandn.php, который потом можно выполнить из браузера строкой

http://127.0.0.1/frandn.php

Об установке PHP и настройке локалхоста сказано, например, в этой моей статье. Инициализация генератора случайных чисел в PHP, начиная с версии 4.2.0, не нужна.

<?
 $f = fopen('data.txt', 'rt');
 $k=100;
 
 function randomstring ($f) {
  $i = 0; 
  $res = '';
  while(!feof($f)) { 
   $str = trim(fgets($f, 128)); 
   if (rand(0,$i++)==0) $res=$str;
  }
  return $res;
 }
 
 print '<html><p>';
 for ($i=0; $i<$k; $i++) {
  fseek ($f, 0, SEEK_SET);
  print randomstring($f).' ';
 }
 fclose($f); 
 print '</html>';
?>

Вот что может выдать такой скрипт:

4547 3401 8198 1602 4307 9805 4367 7072 3705 7132 9837 1695 8925 677 2601 9257 
2661 5366 1999 5426 8131 94 7219 3900 2754 9984 957 3660 9158 3720 6425 3058 6485 
9190 1048 8278 4959 1954 8610 2014 4719 1352 4779 7484 10 7544 6416 2107 9337 700 
3013 9669 3073 5778 2411 5838 8543 401 7631 4312 3166 7963 1367 4072 9570 4132 6837 
3470 6897 9602 1460 8690 5371 2366 9022 2426 5131 1764 5191 7896 285 7956 3665 2519 
9749 1112 3425 8923 3485 6190 2823 6250 8955 813 8043 4724 3578 8375 1779 4484 

Думаю, круче всего наш алгоритм будет выглядеть на Perl, что-то вроде

open(DATA, "$filename"); #Имя файла - в $filename
srand (time); 
rand ($.)<1 && ($line=$_) while <DATA>;
# строка записана в $line
close(DATA);

Но Perl вообще самый красивый язык.

Если строки файла упорядочены "по важности", легко модифицировать алгоритм так, чтобы они выдавались с частотой, обратно пропорциональной номеру строки. В этом случае алгоритм станет работать намного быстрее, ведь в огромном большинстве случаев нам не придётся читать весь файл.

Для программы на Паскале изменится только функция randomstring:

function randomstring:string;
var s:string;
    i:integer;
begin
 i:=0;
 while not eof(f) do begin
  readln (f,s);
  inc(i);
  if random (i+1) = 0 then break;
 end;
 randomstring:=s;
end;

Вот что выдалось при таком подходе:

1 1 19 2 1 1 1 2 2 3 6 1 3 1 1 2 1 11 1 1 2 1 2 6 3 1 2 1 107 1 1 1 2 4 2 1 9 2
4 6 2 1 1 7 20 1 2 1 6 2 1 1 1 3 1 4 1 1 1 1 2 1 1 2 2 3 1 1 1 1 7 2 1 3 2 3 9 5
 12 10 1 2 3 2 5 1 2 1 1 7 1 1 1 3 2 1 3 2 13 4

Для реализации на PHP, аналогично, изменится код функции randomstring:

 function randomstring ($f) {
  $i = 0;
  $str = '';
  while(!feof($f)) { 
   $str = trim(fgets($f, 128)); 
   if (rand(0,++$i)==0) break;
  }
  return $str;
 }

А вот выдача:

1 1 27 862 1 1 2 1 1 1 2 2 3 1 1 2 1 1 1 1 3 1 1 2 20 1 21 7 10 5 1 3 1 1 1 1 4 
1 4 31 1 1 1 1 2 3 2 3 1 1 4 1 1 9 2 1 1 1 43 1 1 14 1 2 4 1 1 2 3 1 2 4 4 3 9 2 
1 7 1 1 2 1 2 1 3 16 1 42 24 3 5 3 1 22 2 2 1 1 3 1 

P.S. Если сделать в последней функции не ++$i, а $i++, будут одни единички - подумайте, почему?

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

Рейтинг@Mail.ru

вверх гостевая; E-mail