ru.perl

 
 - RU.PERL ----------------------------------------------------------------------
 From : Artem Chuprina                       2:5020/371.32  18 Apr 2000  17:01:36
 To : ronin@comint.net
 Subject : Re: поиск в большом массиве?
 -------------------------------------------------------------------------------- 
 

 rcn> Есть:
 rcn> в текстовом файле ~200000 строк (размер ~6 Mb), каждая строка состоит из 5
 rcn> полей, отсортировано по первому полю по возрост.
 rcn> ( 1 ююю ююю ююю ююю
 rcn>   4 зззз зззз ззз ззз
 rcn>   9 гггг гггг гггг ггггг
 rcn> ...
 rcn> )
 rcn> Hужно:
 rcn> СТАHДАРТHЫМИ методами (без подключения дополнительных модулей)производить
 rcn> поиск по первому полю и выводить всю строку.
 rcn> Условия: критично по времени обработки.
 
 "Базу данных, базу данных" - закричали пьяные пионеры. Хотя бы DBM. То есть ты
 можешь пробовать без неё (идея ниже), но у тебя должны быть на то ОЧЕHЬ веские
 основания.
 
 Собственно идея: поиск как поиск, делением пополам.
 
 seek() на середину файла.
 read() какого-нибудь осмысленного фрагмента в память.
 находим первое начало строки во фрагменте (если это первый фрагмент файла,
   началом первой строки будет начало фрагмента, иначе - первый символ
   после первого конца строки); если не нашли, читаем либо попеременно
   следующий и предыдущий фрагменты.
 читаем первое поле. Если оно больше искомого значения - seek() в середину
   первой половины файла. Если меньше - второй.
 
 Далее по циклу.
 
 -- 
 Счастливо!
   Ран.
 --- ifmail v.2.14.os-p7-tma3
  * Origin: MemoNet (2:5020/371.32@fidonet)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор