Поиск строки в большом текстовом файле - профилирование различных методов в python
Этот вопрос задавался много раз. Потратив некоторое время на чтение ответов, я быстро профилировал, чтобы опробовать различные методы, упомянутые ранее...
- У меня есть файл размером 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
Для моего случая использования кажется, что использование набора - лучший вариант, если у меня достаточно доступной памяти. Я надеялся получить некоторые комментарии по этим вопросам:
- Лучшая альтернатива, например, sqlite?
- Способы улучшить время поиска с помощью mmap. У меня есть 64-битная установка. [править] Например, фильтры Блума
- Поскольку размер файла увеличивается до пары ГБ, есть ли способ, которым я могу продолжать использовать 'set', например, разбить его на партии...
[edit 1] PS Мне нужно часто искать, добавлять / удалять значения и не могу использовать только хэш-таблицу, потому что мне нужно получить измененные значения позже.
Любые комментарии / предложения приветствуются!
[править 2] Обновление с результатами методов, предложенных в ответах [править 3] Обновление с результатами sqlite
Решение: на основании всех профилей и обратной связи, я думаю, что я пойду с sqlite. Второй альтернативой является метод 4. Недостатком sqlite является то, что размер базы данных более чем в два раза превышает исходный файл csv с URL-адресами. Это связано с первичным индексом по URL
6 ответов
Вариант 1 хорош, если вам нужно запустить много последовательных поисков. поскольку set внутренне хеш-таблица, она довольно хороша при поиске. Однако на сборку уходит время, и она хорошо работает, только если ваши данные помещаются в оперативную память.
Вариант 3 хорош для очень больших файлов, потому что у вас достаточно адресного пространства для их сопоставления, а ОС кэширует достаточно данных. Вы делаете полное сканирование; это может стать довольно медленным, когда ваши данные перестают помещаться в ОЗУ.
SQLite - определенно хорошая идея, если вам нужно выполнить несколько поисков подряд и вы не можете поместить данные в оперативную память. Загрузите ваши строки в таблицу, создайте индекс, а SQLite создаст для вас красивое b-дерево. Дерево может уместиться в ОЗУ, даже если данные этого не делают (это немного похоже на то, что предложил @alienhard), и даже если это не так, объем необходимых операций ввода-вывода значительно ниже. Конечно, вам нужно создать базу данных SQLite на основе диска. Я сомневаюсь, что основанный на памяти SQLite значительно превзойдет Вариант 1.
Пользовательский поиск по хеш-таблице с внешними строками
Чтобы получить быстрое время доступа и меньшее потребление памяти, вы можете сделать следующее:
- для каждой строки вычислите строковый хеш и добавьте его в хеш-таблицу, например,
index[hash] = position(не храните строку). Если есть столкновение, сохраните все позиции файла для этого ключа в списке. - чтобы найти строку, вычислить ее хеш и найти ее в таблице. Если ключ найден, прочитайте строку по адресу
positionиз файла, чтобы убедиться, что у вас действительно есть совпадение. Если есть несколько позиций, проверяйте каждую, пока не найдете совпадение или ни одного.
Редактировать 1: заменено line_number позицией (как указывает комментатор, очевидно, что нужна фактическая позиция, а не номера строк)
Редактировать 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 столкновений. (Хеш-таблица, вдвое меньшая по размеру, была сопоставима по потреблению памяти, но привела к большему количеству коллизий. Поскольку больше коллизий означает больший доступ к файлам для поиска, я бы предпочел использовать большую таблицу.)
Hash table: 128MB (sys.getsizeof([None]*(2**24)))
Nodes: 64MB (sys.getsizeof(Node(None, None)) * 933132)
Pos ints: 138MB (6000000 * 24)
-----------------
TOTAL: 330MB (real memory usage of python process was ~350MB)
Вы также можете попробовать
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'). Это должно использовать мало памяти, так как файл читается постепенно. Это также должно быть довольно быстро, так как только часть файла читается.
Я предполагаю, что многие пути начинаются одинаково на DMOZ. Вы должны использовать трехуровневую структуру данных и хранить отдельные символы на узлах.
У попыток время поиска O(m) (где m - длина ключа) также экономит много места при сохранении больших словарей или древовидных данных.
Вы также можете хранить части пути на узлах, чтобы уменьшить количество узлов - это называется Patricia Trie. Но это делает поиск медленнее на время сравнения средней длины строки. См. SO question Trie (Prefix Tree) в Python для получения дополнительной информации о реализациях.
В индексе пакетов Python есть несколько простых реализаций, но они не очень хороши. Я написал один на Ruby и Common Lisp, который особенно хорошо подходит для этой задачи - если вы спросите, я мог бы опубликовать его как открытый исходный код...:-)
Без построения индексного файла ваш поиск будет медленным, и это не так просто. Так что лучше использовать уже разработанное программное обеспечение. Наилучшим способом будет использование поисковой системы Sphinx.
Как насчет решения для индексирования текста?
Я бы использовал Lucene в мире Java, но есть движок Python Whoosh