Python-сообщество

Приветствую.

Перейду сразу к делу, есть очень большой текстовый файл (65ГБ) который содержит строки.
И мне нужно ускорить процесс поиска в этом файле, потому-что grep нужно ждать несколько минут.

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

А то уже 2 часа потратил в поисках гугла и stackoverflow.

Единственcтвенный приближенный к рабочему код что я находил:
Но судя по xrange он написан под 2 питон. И у меня он не работает.
К тому-же я совсем не понимаю, как он должен работать

 import os
 
def line_binary_search(filename, matchvalue, key=lambda val: val):
    """
    Binary search a file for matching lines.
    Returns a list of matching lines.
    filename - path to file, passed to 'open'
    matchvalue - value to match
    key - function to extract comparison value from line
 
    >>> parser = lambda val: int(val.split('\t')[0].strip())
    >>> line_binary_search('sd-arc', 63889187, parser)
    ['63889187\t3592559\n', ...]
    """
 
    # Must be greater than the maximum length of any line.
 
    max_line_len = 2 ** 12
 
    start = pos = 0
    end = os.path.getsize(filename)
 
    with open(filename, 'rb') as fptr:
 
        # Limit the number of times we binary search.
 
        for rpt in xrange(50):
 
            last = pos
            pos = start + ((end - start) / 2)
            fptr.seek(pos)
 
            # Move the cursor to a newline boundary.
 
            fptr.readline()
 
            line = fptr.readline()
            linevalue = key(line)
 
            if linevalue == matchvalue or pos == last:
 
                # Seek back until we no longer have a match.
 
                while True:
                    fptr.seek(-max_line_len, 1)
                    fptr.readline()
                    if matchvalue != key(fptr.readline()):
                        break
 
               # Seek forward to the first match.
 
                for rpt in xrange(max_line_len):
                    line = fptr.readline()
                    linevalue = key(line)
                    if matchvalue == linevalue:
                        break
                else:
                    # No match was found.
 
                    return []
 
                results = []
 
                while linevalue == matchvalue:
                    results.append(line)
                    line = fptr.readline()
                    linevalue = key(line)
 
                return results
            elif linevalue < matchvalue:
                start = fptr.tell()
            else:
                assert linevalue > matchvalue
                end = fptr.tell()
        else:
            raise RuntimeError('binary search failed')

Отредактировано stratum (Авг. 12, 2020 19:40:32)

stratum
Перейду сразу к делу, есть очень большой текстовый файл (65ГБ) который содержит строки.
И мне нужно ускорить процесс поиска в этом файле, потому-что grep нужно ждать несколько минут.

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

py.user.next

Поконкретнее как не работает и что непонятно. По идее xrange на range меняете и все. Ну и голова нужна чтобы функцию вызвать.

А вообще поступайте проще. суньте файл в sqlite и ищите запросами. Настоящие базы делают не бинарный поиск. Имеет смысл читать сразу большой кусок файла. Так растет вероятность массового засасывания нужных вам вещей.

stratum
Файл обновляется раз в 2 недели, так-что пересортировывать его не проблема.

stratum
Я уже пересмотрел документацию, к grep и не нашел там бинарный поиск.

stratum
К тому-же, код который я приложил, судя по описанию когда-то работал, на 2 питоне.
Только я не могу понять, как именно, но файл там не индекированный подается на вход.

> Само собой файл отсортирован, как иначе я собрался бы в нем использовать бинарный поиск?

Он у тебя отсортирован по нужному признаку?

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

Тебе ни надо ничего в память загружать.
1) Открываешь файл на чтение
2) Смотришь его размер и записываешь в переменную size (size = os.stat(“/path”).st_size)
3) Перемещаешься к середине файла (file.seek(size//2))
3) Считываешь одну строку и сдвигаешься на четверть размера
4) и т.д. в соответствии с алгоритмом

Отредактировано Rodegast (Авг. 14, 2020 13:48:00)

Я сомневаюсь что на питоне можно реализовать выборку быстрее грепа.
Не спорю - после загрузки - получить данные будет быстрее; Но общее время выполнения будет гораздо больше.

вот годное чтиво к осмыслению вашей задачи.
https://habr.com/ru/post/359284/