Самый быстрый и эффективный способ поиска большого отсортированного текстового файла - PullRequest
Новая
       57

Самый быстрый и эффективный способ поиска большого отсортированного текстового файла

2 голосов
/ 03 апреля 2019

У меня большой статический текстовый / CSV-файл, который содержит около 100 тыс. Строк (2 МБ).По сути, это словарь, и мне нужно регулярно выполнять поиск этих данных в Python.

Формат файла: 

    key         value1       value2     
    alpha       x1           x2
    alpha beta  y1           y2
    gamma       z1           z2  
    ...
  • Ключи могут быть несколькими словамиstrings.
  • Список отсортирован в алфавитном порядке по ключу
  • Значения представляют собой строки

Это часть веб-приложения, в котором каждый пользователь будет искатьдо 100-300 ключей за раз, и будет ожидать получить как значение 1, так и значение 2 для каждого из этих ключей.В приложении будет до 100 пользователей, каждый из которых ищет эти 100-300 ключей по одним и тем же данным.

Мне просто нужно вернуть первое точное совпадение.Например, если пользователь искал ключи [alpha, gamma], мне просто нужно вернуть [('x1','x2'), ('z1','z2')], который представляет первое точное совпадение 'alpha' и 'gamma'.

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

  1. Считайте файл один раз в упорядоченный набор и выполните 200 или около того поисков.Однако для каждого пользователя, использующего приложение (~ 100), файл будет загружен в память.

  2. Считайте файл один раз в список и используйте двоичный поиск (например, разрез`ать ).Проблема, аналогичная 1.) файл будет загружен в память для каждого пользователя, которому требуется выполнить поиск.

  3. Не считывайте весь файл в память, а просто читайте файлпо одной строке за раз.Я могу разбить .csv на 26 файлов по каждой букве (a.csv, b.csv, ...), чтобы немного ускорить процесс.

  4. Whoosh это поисковая библиотека, которая привлекла мое внимание, поскольку она однажды создала индекс.Однако я не уверен, применимо ли это для моего варианта использования, так как он выглядит как полнотекстовый поиск, и я не могу ограничиться только просмотром первого столбца.Если эта конкретная библиотека не является опцией, есть ли какой-нибудь другой способ, которым я могу создать повторно используемый индекс в Python для поддержки таких поисков?

Я действительно открыт для идей, и яЯ никоим образом не ограничен четырьмя вариантами выше!

Спасибо:)

1 Ответ

1 голос
/ 03 апреля 2019

Как насчет чего-то похожего на подход № 2. Вы все еще можете прочитать файл в память, но вместо того, чтобы сохранить его в списке и использовать бинарный поиск для поиска ключей, вы можете сохранить файл в хэш-карте .

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

Вы можете сохранить свой файл как 

table = {
    key1: (value1, value2),
    key2: (value1, value2),
    key2: (value1, value2)
}

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

...