python, Как удалить дубликаты из списка быстрее?

Question

Как можно оптимизировать мою функцию по удалению дубликатов строк из текстового файла используя нативный python?

Пока логика такая, что текст разбивается на строки и если элемент(строка) уникален(ещё нет в списке), то он добавляется в список. но с большими текстовыми файлами(100мб и больше) процесс может затягиваться по времени, что неудивительно исходя из алгоритма. Как ускорить процесс?

inp = input('файл:\n')
file = r'C:\projects\deletestring\examples\''[:-1] + inp
unique = list()
remove_index = list()
with open(file, 'r', encoding="utf-8") as fp:
    data = fp.read()
    for ln_index, ln in enumerate(data.split('\n')):
        if ln not in unique:
            unique.append(ln)
        else:
            remove_index.append(ln_index)

exp = input(
    'название для ред. копии файла:\n'
    'Enter, чтобы вывести результат в консоль:\n')
save_time = time.time()
if exp and not exp.isspace():
    with open(r'C:\projects\deletestring\result\''[:-1] + exp, 'w')as fp:
        for x in unique:
            fp.write(x + '\n')

else:
    for x in unique:
        print(x)

print('Индексы повторяющихся строк: ')
print(remove_index)

Answer 1

как вариант используйте хэши, т.е. алгоритм такой:

вариант 1: практически гарантированный результат

последовательно извлекаются строки из текста
для каждой строки вычисляется хэш с низким шансом коллизии (например md5)
в словарь записывается хэш
если хэш уже есть в словаре - это дубликат

вариант 2: практически гарантированный результат, но быстрее скорость

алгоритм аналогичен предыдущему, но

последовательно извлекаются строки из текста
для каждой строки вычисляется хэш с низким шансом коллизии (например md5)
в массив записываем связку (номер строки, хэш)
сортируем массив по хэшу
удаляем все строки с одинаковым хэшем кроме первой

увеличение скорости из-за того, что однократная сортировка списка работает быстрее, чем запись в словарь

вариант 3: 100% гарантированный результат, но медленнее 1 варианта

последовательно извлекаются строки из текста
для каждой строки вычисляется хэш с низким шансом коллизии (например md5)
в словарь записывается хэш
если хэш уже есть в словаре - сравниваем строки побуквенно

По идее хэши с низкими коллизиями для текста могут быть и очень быстрые, например crc32 или crc64, правда для них все таки лучше использовать вариант 3, т.е. строки надо будет или побайтно сравнивать (если хэши совпадут), но если коллизий мало - то терпимо

Answer 2

Итак - проверил разные подходы на тексте "Война и Мир" :)

упростил код, чтобы не делать ничего лишнего

Код с хэшами от автора

import hashlib
import time

inp = 'd:\\text.txt'

unique = list()
remove_index = list()
hash_dict = {}
i = 1

with open(inp, 'r', encoding="utf-8") as fp:
    data = fp.read()

    start_time = time.time()
    for ln_index, ln in enumerate(data.split('\n', )):

        hash_object = hashlib.md5(ln.encode('utf-8'))

        if hash_object.hexdigest() not in hash_dict.values():
            hash_dict[i] = hash_object.hexdigest()
            i += 1
            unique.append(ln)
        else:
            remove_index.append(ln_index)

    print("---Выполнено за %s секунд ---" % (time.time() - start_time))

---Выполнено за 0.3352799415588379 секунд ---

тут не нравится несколько моментов:

hexdigest() вычисляется до двух раз на строку, вместо одного
запись в словарь хэшей идет по индексу, а не просто добавлением через append

скорректированный код, хэш-функция - md5

import hashlib
import time

inp = 'd:\\text.txt'

unique = list()
remove_index = list()
hashes = set()

with open(inp, 'r', encoding="utf-8") as fp:
    data = fp.read()

    start_time = time.time()

    for ln_index, ln in enumerate(data.split('\n', )):

        hash_object = hashlib.md5(ln.encode('utf-8'))
        hash_value = hash_object.hexdigest()

        if hash_value not in hashes:
            hashes.add(hash_value)
            unique.append(ln)
        else:
            remove_index.append(ln_index)

    print("---Выполнено за %s секунд ---" % (time.time() - start_time))

---Выполнено за 0.024428367614746094 секунд ---

скорректированный код, хэш-функция - crc32

import zlib
import time

inp = 'd:\\text.txt'

unique = list()
remove_index = list()
hashes = set()

with open(inp, 'r', encoding="utf-8") as fp:
    data = fp.read()

    start_time = time.time()

    for ln_index, ln in enumerate(data.split('\n', )):

        hash_value = zlib.crc32(ln.encode('utf-8'))

        if hash_value not in hashes:
            hashes.add(hash_value)
            unique.append(ln)
        else:
            remove_index.append(ln_index)

    print("---Выполнено за %s секунд ---" % (time.time() - start_time))

---Выполнено за 0.016609907150268555 секунд ---

скорректированный код, без хэш-функций (т.е. в качестве хэша сама строка)

import time

inp = 'd:\\text.txt'

unique = list()
remove_index = list()
hashes = set()

with open(inp, 'r', encoding="utf-8") as fp:
    data = fp.read()

    start_time = time.time()

    for ln_index, ln in enumerate(data.split('\n', )):

        if ln not in hashes:
            hashes.add(ln)
            unique.append(ln)
        else:
            remove_index.append(ln_index)

    print("---Выполнено за %s секунд ---" % (time.time() - start_time))

---Выполнено за 0.007816791534423828 секунд ---

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

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

БЛОГ НА HUSL

python, Как удалить дубликаты из списка быстрее?

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