У меня есть текстовый файл 384 МБ с 50 миллионами строк. Каждая строка содержит 2 целых числа, разделенные пробелами: ключ и значение. Файл сортируется по ключу. Мне нужен эффективный способ поиска значений из списка из 200 ключей в Python.
Мой текущий подход включен ниже. Это займет 30 секунд. Должен быть более эффективный Python foo, чтобы добиться максимальной эффективности всего за пару секунд.
# list contains a sorted list of the keys we need to lookup
# there is a sentinel at the end of list to simplify the code
# we use pointer to iterate through the list of keys
for line in fin:
line = map(int, line.split())
while line[0] == list[pointer].key:
list[pointer].value = line[1]
pointer += 1
while line[0] > list[pointer].key:
pointer += 1
if pointer >= len(list) - 1:
break # end of list; -1 is due to sentinel
Кодированный бинарный поиск + поиск решения (спасибо kigurai!):
entries = 24935502 # number of entries
width = 18 # fixed width of an entry in the file padded with spaces
# at the end of each line
for i, search in enumerate(list): # list contains the list of search keys
left, right = 0, entries-1
key = None
while key != search and left <= right:
mid = (left + right) / 2
fin.seek(mid * width)
key, value = map(int, fin.readline().split())
if search > key:
left = mid + 1
else:
right = mid - 1
if key != search:
value = None # for when search key is not found
search.result = value # store the result of the search
Если вам нужно только 200 из 50 миллионов строк, то чтение всего этого в память - это отходы. Я бы отсортировал список ключей поиска, а затем применил двоичный поиск к файлу с помощью функции seek() или чего-то подобного. Таким образом, вы не будете читать весь файл в памяти, который, как мне кажется, должен ускорить процесс.
Незначительная оптимизация ответа S.Lotts:
from collections import defaultdict
keyValues= defaultdict(list)
targetKeys= # some list of keys as strings
for line in fin:
key, value = line.split()
if key in targetKeys:
keyValues[key].append( value )
Поскольку мы используем словарь, а не список, ключи не обязательно должны быть числами. Это сохраняет операцию map() и преобразование строки в целое число для каждой строки. Если вы хотите, чтобы ключи были цифрами, сделайте преобразование завершением, когда вам нужно сделать это только один раз для каждого ключа, а не для каждой из 50 миллионов строк.
Не понятно, что такое "list [pointer]". Однако рассмотрим это.
from collections import defaultdict
keyValues= defaultdict(list)
targetKeys= # some list of keys
for line in fin:
key, value = map( int, line.split())
if key in targetKeys:
keyValues[key].append( value )
Я бы использовал карту памяти: http://docs.python.org/library/mmap.html.
Таким образом, вы можете использовать файл, как если бы он хранился в памяти, но ОС решает, какие страницы должны быть действительно прочитаны из файла.
Если у вас есть какой-либо контроль над форматом файла, ответы "сортировка и бинарный поиск" верны. Деталь заключается в том, что это работает только с записями фиксированного размера и смещения (ну, я должен сказать, что он работает только с фиксированными записями длины).
С фиксированными записями длины вы можете легко искать() вокруг отсортированного файла, чтобы найти свои ключи.
Вот рекурсивный двоичный поиск в текстовом файле
import os, stat
class IntegerKeyTextFile(object):
def __init__(self, filename):
self.filename = filename
self.f = open(self.filename, 'r')
self.getStatinfo()
def getStatinfo(self):
self.statinfo = os.stat(self.filename)
self.size = self.statinfo[stat.ST_SIZE]
def parse(self, line):
key, value = line.split()
k = int(key)
v = int(value)
return (k,v)
def __getitem__(self, key):
return self.findKey(key)
def findKey(self, keyToFind, startpoint=0, endpoint=None):
"Recursively search a text file"
if endpoint is None:
endpoint = self.size
currentpoint = (startpoint + endpoint) // 2
while True:
self.f.seek(currentpoint)
if currentpoint <> 0:
# may not start at a line break! Discard.
baddata = self.f.readline()
linestart = self.f.tell()
keyatpoint = self.f.readline()
if not keyatpoint:
# read returned empty - end of file
raise KeyError('key %d not found'%(keyToFind,))
k,v = self.parse(keyatpoint)
if k == keyToFind:
print 'key found at ', linestart, ' with value ', v
return v
if endpoint == startpoint:
raise KeyError('key %d not found'%(keyToFind,))
if k > keyToFind:
return self.findKey(keyToFind, startpoint, currentpoint)
else:
return self.findKey(keyToFind, currentpoint, endpoint)
Пример текстового файла, созданного в jEdit, кажется, работает:
>>> i = integertext.IntegerKeyTextFile('c:\\sampledata.txt')
>>> i[1]
key found at 0 with value 345
345
Это может быть определенно улучшено путем кэширования найденных ключей и использования кеша для определения будущих начальных точек поиска.
Одна из возможных оптимизаций - сделать немного буферизации с помощью опции sizehint в file.readlines(..). Это позволяет загружать несколько строк в памяти, суммируя приблизительно sizehint байты.
Вам нужно реализовать двоичный поиск с помощью функции seek()