Бинарный поиск по огромному файлу с неизвестной длиной строки - PullRequest
Новая
       28

Бинарный поиск по огромному файлу с неизвестной длиной строки

3 голосов
/ 03 декабря 2011

Я работаю с огромным файлом данных CSV. Каждый файл содержит миллионы записей, каждая запись имеет ключ. Записи отсортированы по их ключам. Я не хочу просматривать весь файл при поиске определенных данных. Я видел это решение: Чтение огромного файла в Python

Но это предполагает, что вы используете одинаковую длину строк в файле - что не поддерживается в моем случае.

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

Я работаю с питоном

Ответы [ 3 ]

7 голосов
/ 03 декабря 2011

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

bytes = 24935502 # number of entries
for i, search in enumerate(list): # list contains the list of search keys
  left, right = 0, bytes - 1 
  key = None
  while key != search and left <= right:
    mid = (left + right) / 2
    fin.seek(mid)
    # now realign to a record
    if mid:
        fin.readline()
    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
2 голосов
/ 03 декабря 2011

Чтобы решить эту проблему, вы также можете использовать бинарный поиск, но нужно немного изменить:

  1. Получить размер файла.
  2. Поиск до середины размера с File.seek.
  3. И найдите первый символ EOL. Тогда вы найдете новую строку.
  4. Проверьте ключ этой строки и, если не хотите, обновите размер и перейдите к 2.

Вот пример кода: 

fp = open('your file')
fp.seek(0, 2)
begin = 0
end = fp.tell()

while (begin < end):
    fp.seek((end - begin) / 2, 0)
    fp.readline()
    line_key = get_key(fp.readline())
    if (key == line_key):
        pass # find what you want
    elif (key > line_key):
        begin = fp.tell()
    else:
        end = fp.tell()

Может быть, в коде есть ошибки. Проверьте себя. И, пожалуйста, проверьте производительность, если вы действительно хотите самый быстрый способ.

1 голос
/ 03 декабря 2011

Ответ на указанный вопрос, в котором говорится, что бинарный поиск работает только с записями фиксированной длины, неверен.И вам вообще не нужно выполнять поиск, поскольку у вас есть несколько элементов для поиска.Просто пройдитесь по всему файлу по одной строке за раз, создайте словарь key:offset для каждой строки, а затем для каждого элемента поиска перейдите к интересующей записи, используя os.lseek со смещением, соответствующим каждому ключу.

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

...