2

Как можно оптимизировать мою функцию по удалению дубликатов строк из текстового файла используя нативный 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)

2 ответа 2

4

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

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

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

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

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

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

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

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

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

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

6
  • можно ли как-то обойти хэши? до этого с ними не работал, а времени на доработку мало
    – MeinJunior
    8 окт 2020 в 19:54
  • 1
    @MeinJunior, а что с ними работать - python-scripts.com/md5-sha1, к примеру т.е. в свое множество вы записываете не строку myset.add(mystring), а ее хэш myset.add(hashlib.md5(mystring).hexdigest())к примеру, а в остальном все тоже, т.е. вам самим хэш-функции писать не надо - уже есть библиотека в питоне (см. ссылку)
    – Zhihar
    8 окт 2020 в 20:00
  • @Zhihad вернулся к задаче, сделал через хэши и процесс выполнения стал ещё дольше, в чём может быть проблема? Код до хэшей - ссылка, Код с хэшем(писал по 1 варианту) - ссылка , я бы и рад использовать set(он в 10 раз быстрее всего того, что пишу я), но мне нужен именно упорядоченный файл на выходе.
    – MeinJunior
    14 окт 2020 в 22:04
  • @MeinJunior, можно еще раз взглянуть на текстовой файл с которым вы работает, чтобы понять с какими строками приходится иметь дело. md5 - тяжелая функция, лучше использовать что-то попроще (crc32 к примеру)
    – Zhihar
    14 окт 2020 в 22:11
  • @Zhihad , в самом вопросе ссылка на ГД с файлами, в основном провожу тесты на Test_1M_2.txt
    – MeinJunior
    14 окт 2020 в 22:12
3

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

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

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

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 секунд ---

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

  1. hexdigest() вычисляется до двух раз на строку, вместо одного
  2. запись в словарь хэшей идет по индексу, а не просто добавлением через 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 :), очень возможно (скорее всего) он сам хэширует и не надо выполнять за него эту лишнюю работу

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

1
  • блин, стак не любит, когда благодарят за работу, но Cпacибo Огромное, Человечище!
    – MeinJunior
    14 окт 2020 в 22:54

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.