Как сделать моментальный бинарный поиск в txt файле?

Question

Есть файл с миллионами отсортированных строк file.txt (1,2 ГБ) вот пример

NrdL9TwD3P2ePvUNzjuzEkHgMF
VtaQZoDxaYKWg6zN2eyysPgWxyzpeuS
VtqndxgoBoSgabMS2Hi8vikLuwBsGov
yNNXkWxa3ACnJnE29Z9qzUnM6eA
ZWZ8yutjQ7xnRMwXKKQviMxSU
VvEY1uxWp3zGdPqv5L7Q1CQ1VzA8nfE
VvLjsvzcga5cfwqQZpXAxEDhVuQY5vP
VvRVzPfn7PuQgkFcmMYQHcnzKN7yVk
vkyZ1p6yuk6cWWDoSHMzm13FMyWUbD
wMCwXk2sYZ3NyJjMBhWzJwcxqHxiLm
wZVQiZMKPzHLcj72cF8dK1mtNMDpsd
Zt7hQJZQb7k43SvxDnYQrdpTiNLQh
VwZvfgXo9TAreDhexjauK7vu2D62DF8
JxAE8XZjE5b4bYuV9KZghka6eHN

И мне нужно моментально определить, есть ли например wZVQiZMKPzHLcj72cF8dK1mtNMDpsd в этом файле. Вот я нашел пример из интернета: https://stackoverflow.com/questions/58140529/binary-search-in-large-txt-with-python-ordered-by-hash

FIELD_SIZE=40+1
def binarySearch(mm, l, r, x):
    while l <= r:
        mid = int(l + (r - l)/2);
        mid_slice = mm[mid*FIELD_SIZE:(mid+1)*FIELD_SIZE]
        mid_slice = mid_slice.decode('utf-8').strip()
        if mid_slice == x:
            return mid
        elif mid_slice < x:
            l = mid + 1
        else:
            r = mid - 1

    return -1

with open('file.txt', 'r+b') as f:
    mm = mmap.mmap(f.fileno(), 0)
    f.seek(0, os.SEEK_END)
    size = f.tell()
    result = binarySearch(mm, 0, size/FIELD_SIZE, 'wZVQiZMKPzHLcj72cF8dK1mtNMDpsd')
    if result != -1:
        print("Element is present at index % d" % result)
    else:
        print("Element is not present in array")

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

Answer 1

Можно модифицировать алгоритм, чтоб он:

когда делил пополам и искал mid, то делал сдвиг до ближайшего начала строки
когда вырезал кусок mid_slice, то брал не фиксированный размер FIELD_SIZE, а опять же искал следующий конец строки.

Сейчас не работает потому, что при делении попадаете внутрь строки.

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

На 220MB файле со строками ~20 символов ищет за 100ms.

import mmap
import os
import sys


eol_bytes = list(enumerate(os.linesep.encode('utf-8')))

def is_eol(mm, i, size):
    # логика для определения конца строки
    return i + len(eol_bytes) <= size \
        and all(b == mm[i + n] for n, b in eol_bytes)


def binarySearch(mm, l, r, x, size):
    while l <= r:
        mid = int(l + (r - l)/2);
        prev_eol = mid
        while prev_eol >= 0 and not is_eol(mm, prev_eol, size):
            prev_eol -= 1
        next_eol = mid + 1
        while next_eol < size and not is_eol(mm, next_eol, size):
            next_eol += 1
        mid_slice = mm[prev_eol+1:next_eol]
        mid_slice = mid_slice.decode('utf-8').strip()
        if mid_slice == x:
            return prev_eol + 1
        elif mid_slice < x:
            l = next_eol + 1
        else:
            r = prev_eol - 1
    return -1

filename = sys.argv[1]
search_string = sys.argv[2]

with open(filename, 'r+b') as f:
    mm = mmap.mmap(f.fileno(), 0)
    f.seek(0, os.SEEK_END)
    size = f.tell()
    result = binarySearch(mm, 0, size, search_string, size)
    if result != -1:
        print("Element is present at index % d" % result)
    else:
        print("Element is not present in array")

Answer 2

По мотивам ответа @RomanKonoval ...

def binarySearch(mm, l, r, x, size):
    eol_bytes = os.linesep.encode()
    x = x.encode()
    while l <= r:
        mid = l + (r - l)//2
        prev_eol = mm.rfind(eol_bytes, 0, mid + len(eol_bytes))
        if prev_eol == -1: prev_eol = 0
        next_eol = mm.find(eol_bytes, mid + 1)
        if next_eol == -1: next_eol = size
        pos = prev_eol+len(eol_bytes) if eol_bytes == mm[prev_eol:prev_eol+len(eol_bytes)] else prev_eol
        mid_slice = mm[pos:next_eol]
        if mid_slice == x:
            return pos
        elif mid_slice < x:
            l = next_eol + len(eol_bytes)
        else:
            r = prev_eol
    return -1

Работает корректно с нативными окончаниями строк под любой ОС.
Также раза в 3-4 быстрее оригинала. Хотя это не существенно, ибо у меня поиск занимал около полторы тысячных секунды на файле 2ГБ с 46.6 миллионами случайных строк длиной 40-50 символов каждая.

Orig:  1.51013 ms
New :  0.39095 ms

БЛОГ НА HUSL

Как сделать моментальный бинарный поиск в txt файле?

Ответы (2 шт):