Python - предложения по фильтрации / сортировке большого файла?

Question

У меня есть файл, содержащий ~ 20 миллионов строк (~ 1,5 ГБ).Каждая строка имеет вид:

entry_1 entry_2 entry_3 ......... entry_5

Файл содержит дубликаты, но в форме:

entry_2 entry_1 entry_3 ......... entry_5

Содержимое некоторых строк идентично, но первые два элемента часто (возможно,всегда) переключился.

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

Спасибо.

Answer 1

Подходящее решение будет зависеть от того, какие у вас есть ограничения и как часто вам нужно запускать эту операцию.

Если это однократная (или нечастая) операция и если использование памяти не является большой проблемой, то что-то вроде этого будет достаточно:

visited = set() # use set for faster lookups
with open(out_filename, "w") as outfile:
    with open(in_filename, "r") as infile:
        for line in infile:
            x = line.split()
            k = (tuple(sorted(x[:2])), tuple(x[2:]))
            if k not in visited:
                outfile.write(line)
                visited.add(k)

Использование памяти зависит от количества уникальных записей, которые мы должны отслеживать в visited. Если дубликатов не так много, вы получите почти все данные в памяти.

Если использование памяти становится проблемой , вы можете сделать это в несколько этапов:

1. Сначала предварительно обработайте файл, отсортировав первые 2 элемента в каждой строке.
2. Сортировка всего файла по строкам
3. Удаление дубликатов теперь прямое, так как дублирующиеся записи будут появляться вместе.

Шаг 2 и 3 можно объединить, так как вы можете просто отбросить дубликаты при сравнении записей при выполнении сортировки.

Если вы не возражаете против использования оболочки, шаги 2 и 3 можно выполнить с помощью sort -u yourfile.

Обратите внимание, что это меняет порядок строк в файле (который вы упомянули не проблема).

Чтобы значительно сократить использование памяти за счет некоторой производительности, вы можете использовать базу данных на основе файлов для хранения и поиска посещенных записей (вместо set()).

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

Это займет некоторое усилие, чтобы найти оптимальное решение. Только стоит начинать, если вам нужно часто выполнять эту операцию.

Answer 2

separator = " "
aSet = set()
with open('myfile', 'rU') as infile:
    for line in infile:
        tempLine = line.split(separator)
        tempLine = tempLine[1:2] + tempLine[0:1] + tempLine[2:]
        tempLine = separator.join(tempLine)
        if line not in aSet and tempLine not in aSet:
            aSet.add(line)

Теперь aSet содержит список уникальных строк независимо от того, были ли поменяны местами entry_1 и entry_2.

РЕДАКТИРОВАТЬ : Если все записи можно поменять местами и строка все еще считается уникальной, то:

separator = " "
aSet = set()
with open('myfile', 'rU') as infile:
    for line in infile:
        aSet.add(frozenset(line.split(separator)))