Поиск строки в большом текстовом файле - профилирование различных методов в python

Question

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

• У меня есть файл 600 МБ с 6 миллионами строками строк (пути категорий из проекта DMOZ).
• Запись в каждой строке уникальна.
• Я хочу загрузить файл один раз & продолжить поиск совпадений в данных

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

---

1) set :
    (i)  data   = set(f.read().splitlines())
    (ii) result = search_str in data   

Время загрузки ~ 10 с, Время поиска ~ 0,0 с, Использование памяти ~ 1,2 ГБ

---

2) list :
    (i)  data   = f.read().splitlines()
    (ii) result = search_str in data

Время загрузки ~ 6 с, Время поиска ~ 0,36 с, Использование памяти ~ 1,2 ГБ

---

3) mmap :
    (i)  data   = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
    (ii) result = data.find(search_str)

Время загрузки ~ 0 с, Время поиска ~ 5,4 с, Использование памяти ~ NA

---

4) Hash lookup (using code from @alienhard below):   

Время загрузки ~ 65 с, Время поиска ~ 0,0 с, Использование памяти ~ 250 МБ

---

5) File search (using code from @EOL below):   
   with open('input.txt') as f:
       print search_str in f #search_str ends with the ('\n' or '\r\n') as in the file

Время загрузки ~ 0 с, Время поиска ~ 3,2 с, Использование памяти ~ NA

---

6) sqlite (with primary index on url): 

Время загрузки ~ 0 с, Время поиска ~ 0,0 с, Использование памяти ~ NA

---

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

1. A лучшая альтернатива например sqlite?
2. Способы улучшить время поиска с помощью mmap . У меня есть 64-битная установка. [редактировать] например фильтры Блума
3. Поскольку размер файла увеличивается до пары ГБ, есть ли способ, которым я могу продолжать использовать 'set', например разбить его на партии ..

[править 1] П.С. Мне нужно часто искать, добавлять / удалять значения и не могу использовать только хэш-таблицу, потому что мне нужно получить измененные значения позже.

Любые комментарии / предложения приветствуются!

[править 2] Обновление с результатами методов, предложенных в ответах [править 3] Обновление с результатами sqlite

Решение : Основываясь на профилировании и обратной связи, я думаю, я пойду с sqlite. Второй альтернативой является метод 4. Недостатком sqlite является то, что размер базы данных более чем в два раза превышает исходный файл csv с URL-адресами. Это связано с первичным индексом на URL

Answer 1

Вариант 1 отлично подходит, если вам нужно запустить много последовательных поисков.Поскольку set внутренне является хеш-таблицей, он довольно хорош при поиске.Однако на сборку уходит время, и она хорошо работает, только если ваши данные помещаются в ОЗУ.

Вариант 3 подходит для очень больших файлов, поскольку у вас достаточно адресного пространства для их сопоставления и ОС кэширует достаточно данных.Вы делаете полное сканирование;он может стать довольно медленным, когда ваши данные перестают помещаться в ОЗУ.

SQLite - определенно хорошая идея, если вам нужно выполнить несколько поисков подряд и вы не можете поместить данные в ОЗУ.Загрузите ваши строки в таблицу, создайте индекс, а SQLite создаст для вас красивое b-дерево.Дерево может уместиться в ОЗУ, даже если данные этого не делают (это немного похоже на то, что предложил @alienhard), и даже если это не так, объем необходимых операций ввода-вывода значительно ниже.Конечно, вам нужно создать базу данных SQLite на основе диска.Я сомневаюсь, что основанный на памяти SQLite значительно превзойдет Вариант 1.

Answer 2

Поиск пользовательских хеш-таблиц с внешними строками

Чтобы получить быстрое время доступа и при меньшем потреблении памяти, вы можете сделать следующее:

• для каждой строки вычисляет хеш-строку и добавляет ее в хеш-таблицу, например, index[hash] = position (не сохраняйте строку ).Если есть столкновение, сохраните все позиции файла для этого ключа в списке.
• , чтобы найти строку, вычислить ее хеш и найти ее в таблице.Если ключ найден, прочитайте строку из файла position из файла, чтобы убедиться, что у вас действительно есть совпадение.Если есть несколько позиций, проверяйте каждую из них, пока не найдете совпадение или ничего.

Редактировать 1: номер строки заменен позицией (как указано комментатором, очевидно, что нужна фактическая позиция, а не номера строк))

Редактировать 2: предоставить код для реализации с настраиваемой хэш-таблицей, которая показывает, что этот подход более эффективен по сравнению с другими упомянутыми подходами:

from collections import namedtuple 
Node = namedtuple('Node', ['pos', 'next'])

def build_table(f, size):
    table = [ None ] * size
    while True:
        pos = f.tell()
        line = f.readline()
        if not line: break
        i = hash(line) % size
        if table[i] is None:
            table[i] = pos
        else:
            table[i] = Node(pos, table[i])
    return table

def search(string, table, f):
    i = hash(string) % len(table)
    entry = table[i]
    while entry is not None:
        pos = entry.pos if isinstance(entry, Node) else entry
        f.seek(pos)
        if f.readline() == string:
            return True
        entry = entry.next if isinstance(entry, Node) else None
    return False

SIZE = 2**24
with open('data.txt', 'r') as f:
    table = build_table(f, SIZE)
    print search('Some test string\n', table, f)

Хэш строки используется только для индексации в таблице (если бы мы использовали обычный dict, хеши также были бы сохранены как ключи).Положение файла в строке сохраняется по заданному индексу.Столкновения разрешаются цепочкой, т. Е. Мы создаем связанный список.Однако первая запись никогда не переносится в узле (эта оптимизация делает код немного более сложным, но экономит довольно много места).

Для файла с 6 миллионами строк я выбрал размер хеш-таблицы 2 ^ 24.С моими данными испытаний я получил 933132 столкновений.(Хеш-таблица, вдвое меньшая по размеру, была сопоставима по потреблению памяти, но привела к большему количеству коллизий. Поскольку больше коллизий означает больший доступ к файлам для поиска, я бы предпочел использовать большую таблицу.)

Answer 3

Вы также можете попробовать

with open('input.txt') as f:
    # search_str is matched against each line in turn; returns on the first match:
    print search_str in f

с search_str, заканчивающимся правильной последовательностью новой строки ('\n' или '\r\n'). Это должно использовать мало памяти, так как файл читается постепенно. Это также должно быть довольно быстро, так как читается только часть файла.

Answer 4

Я предполагаю, что многие пути начинаются одинаково на DMOZ.Вы должны использовать структуру данных trie и хранить отдельные символы на узлах.

У попыток есть O (m) время поиска (где m - длина ключа), также экономьте много места,при сохранении больших словарей или древовидных данных.

Вы также можете хранить части пути на узлах, чтобы уменьшить количество узлов - это называется Patricia Trie.Но это делает поиск медленнее на время сравнения средней длины строки.См. SO question Trie (Дерево префиксов) в Python для получения дополнительной информации о реализациях.

Существует несколько простых реализаций в индексе пакетов Python, но они не очень хороши.Я написал один на Ruby и Common Lisp, который особенно хорошо подходит для этой задачи - если вы спросите, я мог бы опубликовать его как открытый исходный код ...: -)

Answer 5

Без создания индексного файла ваш поиск будет медленным, и это не так просто.Так что лучше использовать уже разработанное программное обеспечение.Лучше всего будет использовать Sphinx Search Engine .

Answer 6

как насчет решения для индексирования текста?

Я бы использовал Lucene в мире Java, но есть движок Python, который называется Whoosh

https://bitbucket.org/mchaput/whoosh/wiki/Home