Ускоренный поиск по файлам в Perl

Question

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

Это что-то вроде этого (псевдокод):

while count < total number of files
     open current file
     extract line from this file
     build an arrayofStrings from this line

     foreach string in arrayofStrings
          foreach file in arrayofDataReferenceFiles
               search in these files

     close file
     increment count

Для большой реальной работы процесс может занять около 6 часов.

В основном у меня есть большой набор строк, который использует программу для поиска по тому же набору файлов (например, 10 в 1 экземпляре и может быть 3 в следующем случае, когда программа запускается). Поскольку файлы справочных данных могут изменяться, я не думаю, что было бы разумно создавать постоянный индекс этих файлов.

Я в значительной степени новичок и не знаю каких-либо более быстрых методов для несортированных данных.

Я думал, так как поиск через некоторое время становится повторяющимся, возможно ли предварительно создать индекс местоположений определенных строк в ссылочных файлах данных без использования каких-либо внешних библиотек perl, как только массив файлов будет создан (файлы известны)? Этот скрипт будет перенесен на сервер, на котором, вероятно, установлен только стандартный Perl.

Я подумал, что, возможно, стоит потратить 3-5 минут на создание своего рода индекса для поиска перед обработкой задания.

Существует ли конкретная концепция индексации / поиска, которая применима к моей ситуации?

Спасибо всем!

Answer 1

Трудно понять, чего именно вы пытаетесь достичь.

Я предполагаю, что набор данных не помещается в ОЗУ.

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

С другой стороны, если сопоставление занимает то время, которое вам, вероятно, лучше использовать библиотеку, которая может одновременно сопоставлять множество шаблонов.

Answer 2

Как сказал MarkR, вы хотите прочитать каждую строку из каждого файла не более одного раза.Псевдокод, который вы разместили, выглядит так, как будто вы читаете каждую строку каждого файла несколько раз (по одному разу для каждого искомого слова), что значительно замедляет процесс, особенно при большом поиске.Изменение порядка двух самых внутренних циклов должно (судя по опубликованному псевдокоду) исправить это.

Но вы также сказали: " Поскольку файлы справочных данных могут измениться, я не думаю, что этоУмно построить постоянный индекс этих файлов."Это, скорее всего, неправильно.Если производительность вызывает беспокойство (если вы получаете 6-часовое время выполнения, я бы сказал, что это, вероятно, делает это проблемой), и в среднем каждый файл читается более одного раза между изменениями этого конкретного файла, а затем создается индексна диске (или даже ... используя базу данных!) было бы очень разумно сделать.Дисковое пространство очень дешево в наши дни;время, которое люди тратят на ожидание результатов, не равно.

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

Answer 3

Вы, вероятно, могли бы заменить это:

foreach file in arrayofDataReferenceFiles
    search in these files

этапом предварительной обработки для создания файла DBM (то есть хэша на диске) в качестве обратного индекса, который отображает каждое слово в ваших ссылочных файлах в списокфайлов, содержащих это слово (или все, что вам нужно).Ядро Perl включает поддержку DBM :

HASH, DBNAME, MASK

Это связывает dbm (3), ndbm (3), файл sdbm (3), gdbm (3) или Berkeley DB для хэша.

Обычно вы получаете доступ к этому материалу через tie, но это не такважно, чтобы каждый Perl имел некоторую поддержку хотя бы одной библиотеки хэширования на диске без необходимости устанавливать неосновные пакеты.