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

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

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

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

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


python database large-files io binary-search
person RanZilber    schedule 03.12.2011    source источник
comment
@Mat- сейчас не вариант. У меня очень ограниченный срок и недостаточно времени для создания базы данных из этих данных.   -  person RanZilber    schedule 03.12.2011
comment
Выполните двоичный поиск на уровне байтов и после поиска найдите ближайшую новую строку.   -  person sleeplessnerd    schedule 03.12.2011
comment
stackoverflow.com/a/5942463/616486 у sqlite, похоже, есть опция автоматического импорта csv.   -  person sleeplessnerd    schedule 03.12.2011
comment
Бинарный поиск ни у кого не работает правильно с первого раза. К настоящему моменту у вас уже могло быть готовое и работающее решение для базы данных. Сколько разных больших файлов у вас есть? Каково типичное количество записей? Каков типичный размер файла в ГБ? Является ли ключ числом или строкой?   -  person John Machin    schedule 04.12.2011

Ответы (3)


arrow_upward
8
arrow_downward

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

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
person Gabe    schedule 03.12.2011

arrow_upward
2
arrow_downward

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

  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()

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

person Googol    schedule 03.12.2011
comment
Кажется, никогда не найти первую строку. - person MoreFreeze; 07.11.2017

arrow_upward
1
arrow_downward

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

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

person Dave    schedule 03.12.2011