Как ускорить бинарный поиск

Приветствую, сообщество Habr. Я решил рассказать о том, как ускорить обычный бинаный поиск в сотни раз и искать данные в обычном текстовом файле БЫСТРЕЕ, чем при использовании класических баз данных. Сейчас я попробую решить задачу бинарного поиска без них, расскажу об основных способах оптимизации, а в конце проведу сравнение. Это вполне реальная задача, с которой я столкнутся при разработке собственного проекта, а поэтому мне есть что вам рассказать.

Устроен бинарный поиск очень просто - вы сортируете массив данных по алфавиту, а потом ищете в нём нужную информацию так же, как в бумажном словаре - открываете книгу посередине и смотрите, с какой стороны искомое слово - справа или слева. Затем открываете нужную часть посередине и вновь смотрите, куда двигаться. И так до тех пор, пока найдёте нужное слово.

Таким образом можно находить нужную информацию за логарифмическое время, но исключительно в теории.

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [1, 3, 5, 7, 9]
x = 5
print(binary_search(arr, x))

>>2

На практике у нас обычно нет доступа ко всему массиву с данными. Бинарный поиск эффективно использовать тогда, когда данных много и в оперативнуюю память их вместить нельзя. Да и если бы было можно - пришлось бы их считывать с диска, что заняло бы кучу времени. К счастью, в большинстве языков програмирования есть замечательная функция seek(), которая позволяет перемещаться в любое место считываемого файла. При этом время перехода не зависит от расстояния, на которое нужно переместиться (если файл не дефрагментирован). Это значит, что мы можем реализовать бинарный поиск прямо внутри файла, не считывая его.

Но у вас мог возникнуть вопрос - для бинарного поиска нужно перемещаться к строке с определённым номером. Если строки одинаковой длины, задача чисто математическая. Но что если нет? Неужели нужно дополнять их до одной длины пробелами? Или хранить в отдельном индексе длины строк? Разумеется, нет.
Когда вы ищете нужное слово в словаре, вы не нужно открывать его строго на определённой странице. Достаточно уметь открывать его примерно посередине. Действительно, если мы считываем файл посередине, нам неважно, что слева оказалось 995 строк, а справа - 1005. Достаточно знать, что двигаться нужно влево, и мы не пропустим нужную строку.

Так же у вас мог возникнуть другой вопрос - допустим, мы переместились в центр файла. Как нам считать одну строку? Мы же могли попасть в её центр и не знаем, где начало.

Самое простое решение - смещаться по одному символу влево, пока не дойдём до символа новой строки. А потом считать строку целиком через readline.

n = 10000000
with open('text.txt', encoding='utf-8') as file:
    file.seek(n)
    while True:
        n = n-1
        file.seek(n)  # перейти на один символ назад
        char = file.read(1)
        if char == '\n' or file.tell() == 0:  # если дошли до конца строки или начала файла
            break
        S = file.readline()
    print(S)

Однако, у такого решения есть неочевидная проблема - HDD диски не очень любят читать "назад", а поэтому в случае с большими строками это будет работать медленее. Гораздо проще поступить так:

n = 10000000
with open('text.txt', encoding='utf-8') as file:
    file.seek(n)
    file.readline()
    print(file.readline())

Да, можно просто пропускать ту строку, в которую мы попали, и работать уже со следующей. При этом, правда, бинарный поиск не сможет найти самую первую строку в файле, но мы можем поместить туда заголовки столбцов и сказать, что это не баг, а фича. Хотя один баг всё таки стоит исправить:

UnicodeDecodeError: 'utf-8' codec can't decode byte 0x90 in position 0: invalid start byte

Дело в том, что мы попадаем в случайный байт файла. А некоторые символы в юникоде состоят из нескольких байтов и попадая "внутрь" такого символа мы получаем ошибку. Происходят они достаточно редко, так как большинство символов однобайтовые, а поэтому такие эту проблему можно просто игнорировать. Для этого мы можем указать в функции открытия файла параметр errors='ignore'. Либо использовать связку try - except и немного кода. Примерно вот так:

n = 10000000
with open('text.txt', encoding='utf-8') as file:
    file.seek(n)
    while True:
        try:
            file.readline()
            break
        except UnicodeDecodeError:
            n=n+1
            file.seek(n)
    print(file.readline())

Как ещё можно ускорить поиск? Давайте обратим внимание на то, какие именно файлы мы считываем. При каждом поиске мы считываем строку, находящуюся в центре файла. В половине случаев мы считываем строки на 25% и 75% файла. И так далее. Одни и те же позиции считываются многократно. А это плохо. Если мы используем SSD, такой подход может изностить его со временем, а если у нас HDD, то переход от одной позиции к другой занимает относительно много времени, так как считывающей головке физически нужно переместиться в нужное место.

Но зачем нам при каждом поиске считывать центр файла и другие ключевые точки? Можно считать их один единственный раз и запомнить. Такой метод оптимизации называется кэшированием и реализовать его можно при помощи декоратора lru_cache.

from functools import lru_cache

@lru_cache(maxsize=100000)
def get_data_in_position(file_name, point):
    with open(file_name, encoding='utf-8') as file:
        file.seek(point)
        while True:
            try:
                file.readline()
                break
            except UnicodeDecodeError:
                point=point+1
                file.seek(point)
        return(file.readline())

В данном случае переменная maxsize отвечает за максимальное количество строк, сохранённых в кэше. Нам ведь не нужно, что бы он забил всю оперативную память.
Но на этом кэширование не закончено. Ведь сейчас мы на каждой итерации поиска вновь открываем исходный файл, что занимает много времени. Почему бы нам не хранить переменную открытого файла так же в кэше? Тут для разнобразия обойдёмся без готовых решений, что бы показать, что кэширование это совсем не сложно.

open_file_list={} #кэш открытых файлов
def open_file_cashe(name_file):
    global open_file_list
    if open_file_list.get(name_file)!=None:
        return(open_file_list.get(name_file))
    else: 
        t=open(name_file,'r',encoding='utf-8',errors='ignore') #,'\n'.join(a[Min:])
        if len(open_file_list)<10: #кэшируем до 10 открытых файлов
            open_file_list[name_file]=t
        else:
            File = open_file_list.popitem()
            File[1].close()
            open_file_list[name_file]=t
    return(t)

Тут всё просто - функция принимает имя файла и если он уже есть в кэше - он берётся оттуда. Если нет - добавляется туда. При этом в кэше не хранится больше 10 открытых файлов. Во-первых, это ни к чему. А во-вторых максимальное количество открытых файлов тоже ограничено, обычно 2-мя или 8-ю тысячами.

За счёт этой доработки мы можем не открывать один и тот же файл несколько раз. Даже при множестве поисков файлы не придётся открывать больше раз, чем требуется. Есть ещё много способов оптимизации. Можно делить файлы на части, сохранять в кэше первую и последнюю строку, кэшировать размер файлов в байтах (он нужен для бинарного поиска). Можно хранить большие файлы на HDD, а маленькие на SSD, можно соединять разные файлы вместе используя индексы и не только. Но обо всём этом я расскажу в следующий раз. А пока покажу обещаное сравнение моего алгоритма поиска и класической базы данных.

Для Сравнения я создал базу данных MySQL, содержащую числа от 1 до 1000000 и их хэши MD5.

Обычный текстовый файл

Индекс для поиска по хэшам

Так же заметим интересную особенность - база данных весит вдвое больше, чем обычный текстовый файл! Довольно существенная разница, которая вызвана хранением дополнительного поискового индекса.

Но давайте сравним скорость поиска при помощи вот таких простых функций:

def find_hashes_sql():
    # открываем соединение с базой данных
    conn = sqlite3.connect('hashes.db')
    cursor = conn.cursor()
    # генерируем 10000 случайных чисел и ищем их хэши
    total_time = 0
    for i in range(100000):
        # выбираем случайное число
        num = random.randint(1, 1000000)
        # получаем хэш числа
        hash_value = hashlib.md5(str(num).encode()).hexdigest()
        # засекаем время перед запросом
        start_time = time.time()
        # выполняем запрос по хэшу
        cursor.execute('''SELECT id FROM hashes
                          WHERE hash_value = ?''', (hash_value,))
        # получаем результаты и добавляем время запроса к общему времени
        result = cursor.fetchone()
        end_time = time.time()
        total_time += end_time - start_time
    # закрываем соединение
    conn.close()
    # выводим общее время запросов
    print(f'Total time taken: {total_time} seconds')

def find_hashes_csv():
    # генерируем 10000 случайных чисел и ищем их хэши
    total_time = 0
    for i in range(100000):
        # выбираем случайное число
        num = random.randint(1, 1000000)
        # получаем хэш числа
        hash_value = hashlib.md5(str(num).encode()).hexdigest()
        # засекаем время перед запросом
        start_time = time.time()
        find_in_file('hashes.csv',hash_value) #функция нашего поиска
        end_time = time.time()
        total_time += end_time - start_time
    # выводим общее время запросов
    print(f'Total time taken: {total_time} seconds')

Результаты:

SQL

CSV

Таким образом мы на коленке собрали систему поиска, вдвое более быструю, чем в настоящих базах данных! Да ещё и более экономную по памяти!
Но этому есть простое объяснение - базы данных это мультитул, универсальный инструмент с десятками возможностей, с различными вариациями поиска и со сложными алгоритмами добавления и удаления данных. При их разработке пожертвовали скоростью работы в пользу удобства и универсальности. Поэтому более простой алгоритм вполне может быть более быстрым.

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

Когда я реализовывал поиск, база данных SQL для меня не подходила потому что я не люблю SQL потому что размер всех файлов 2,5 TB и вместе с индексами они просто не помещались на мой диск. Поэтому я изучил всё то, о чём написал выше и в итоге реализовал бота так, как и хотел изначально.

Этот бот может выполнять 20 запросов в секунду при размере базы данных в 40 миллиардов строк! И всё это ислючительно на бинарном поиске. Никакого SQL, обычные текстовые файлы и максимальное количество способов оптимизаций. Не только те, которые я рассказал в этой статье, но и некоторые другие, о которых я напишу в следующих статьях.
А вот и этот бот, вы сами можете проверить как он работает: DataLeakAlertBot

И надеюсь, что вам была интересна эта статья. Готов ответь на любые вопросы, которые у вас могли возникнуть.