Xpoint
   [напомнить пароль]

Получение строки по номеру в большом массиве

Метки: [без меток]
2009-11-11 15:11:39 [обр] Roin[досье]

День добрый.
Стоит такая задача:
Есть файл, в котором дано 500 000 строк. Получить строку из такого файла имея её номер.
Например в файле 4 строки:

  • Вася
  • Петя
  • Чтото
  • Както

...
Нужно получить строку под номером 4 - "Както".
Всё бы ничего, казалось бы:

$num=4;
$word=file(PATH.'/file.txt');
print( trim($word[($num-1)]) );

Но если массив на пол миллиона строк и скрипт будет вызываться очень часто памяти сервера нехватет так как скрипт слишком ресурсоёмкий. Решение не оптимально. Функция file записывает весь файл в масиив...Нужно как то читать файл и постараться обратиться к нужной строке. Возникли идеи про fgets. Читаем файл, подсчитываем строки, на каждой итерации и смотрим номер:

$num=20000;
$sch=1;
$f=fopen(path.'/file.txt', 'r');
$string='';
while(!feof($f))
 {
  $string=fgets($f);
  if($sch==$num) break;
  $sc++;
 }
echo $string;

Но этот вариант тоже думаю ресурсоёмкий :(
Может кто знает методы поиска оптимальные для данной задчи.
Про БД не советуйте - задача именно с файлом.

спустя 47 минут [обр] Давид Мзареулян(536/1003)[досье]
Читать блоками, в каждом блоке считать число переводов строки. Когда дойдёте до нужного — делать fgets с этого смещения.
спустя 4 минуты [обр] Филипп Ткачев(20/112)[досье]
используйте file_get_contents(), через нее можно читать файл частями, но следить за концами строк намного сложнее, поэтому надо будет создать индекс со смещениями, который тоже можно будет быстро читать используя file_get_contents() и unpack().
если есть возможность безопасно использовать exec(), то можно применить grep, наверняка с ним быстрее получится.
Еще: файл можно разделить на несколько частей один раз и впоследствии работать с фрагментами.
спустя 18 минут [обр] Давид Мзареулян(536/1003)[досье]
Да, если файл не изменяется или данные добавляются только в конец, а искать по нему надо очень часто, то можно отдельно завести индекс — простой линейный список смещений начал строк в основном файле. Тогда поиск строки сведётся к бинарному поиску в файле индекса.
спустя 5 часов [обр] Thirteensmay(17/157)[досье]
Давид Мзареулян[досье] тогда и поиска никакого ненадо, прямое обращение. Смещение строки фиксировано четырехбайтная величина, значит для определения смещения энной строки достаточно обратиться в индексный файл по смещению N*4 Roin[досье] думаю есть смысл рассмотреть этот вариант. Сначала сравниваете номер строки которую вам необходимо получить умноженный на 4, с размером индексного файла, если файл больше значит готовое смещение в нем уже есть, извлекаете смещение, затем строку. Если же готового смещения в индексном файле нет то сперва необходимо достроить индекс начиная с последнего имеющегося, поблочно как описано выше.
спустя 6 минут [обр] Давид Мзареулян(536/1003)[досье]
Thirteensmay[досье] Да, стормозил.
спустя 9 часов [обр] Николай(3/3)[досье]

Почему бы не разделить фаил??? Допустим так:
/data - папка с файлами
/data/a.file - фаил с данными которые начинаються на a
/data/b.file - фаил с данными которые начинаються на b
/data/c.file - фаил с данными которые начинаються на c
...
/data/x.file - фаил с данными которые начинаються на x
/data/y.file - фаил с данными которые начинаються на y
/data/z.file - фаил с данными которые начинаються на z

Можно пойти еще дальше.

/data/a/a.file
/data/a/b.file
...
/data/z/a.file
/data/z/b.file

То есть первая буква это название папки. Вторая название файла.

Чем плох мой способ???
"Получить строку из такого файла имея её номер." Будет работать если мы будем знать запись в файле. Вобщем если подумать то и Ваша проблема наверное сможет вписаться в такое разделение...

Powered by POEM™ Engine Copyright © 2002-2005