Удаление дубликатов на очень больших наборах данных

Я работаю над 13,9 ГБ CSV-файла, который содержит около 16 миллионов строк и 85 столбцов. Я знаю, что потенциально есть несколько сотен тысяч строк, которые являются дубликатами. Я запустил этот код, чтобы удалить их

import pandas

concatDf=pandas.read_csv("C:\\OUT\\Concat EPC3.csv")
nodupl=concatDf.drop_duplicates()
nodupl.to_csv("C:\\OUT\\Concat EPC3- NoDupl.csv",index=0)
low_memory=False

Однако это приводит меня к MemoryError. Мой баран 16 ГБ и не может идти выше. Есть ли более эффективный способ удаления дубликатов, который, возможно, использует куски без необходимости разбивать файл csv на более мелкие файлы?

Источник

4 ответа

Решение

По сути, та же идея, что и у zwer, но проверка на равенство в строках с одинаковым хешем (вместо автоматического отбрасывания дублированных хешей).

file_in = "C:\\OUT\\Concat EPC3.csv"
file_out = "C:\\OUT\\Concat EPC3- NoDupl.csv"

with open(file_in, 'r') as f_in, open(file_out, 'w') as f_out:
    # Skip header
    next(f_in)
    # Find duplicated hashes
    hashes = set()
    hashes_dup = {}
    for row in f_in:
        h = hash(row)
        if h in hashes:
            hashes_dup[h] = set()
        else:
            hashes.add(h)
    del hashes
    # Rewind file
    f_in.seek(0)
    # Copy header
    f_out.write(next(f_in))
    # Copy non repeated lines
    for row in f_in:
        h = hash(row)
        if h in hashes_dup:
            dups = hashes_dup[h]
            if row in dups:
                continue
            dups.add(row)
        f_out.write(next(f_in))
Источник

Простейшим решением было бы создание хеш-таблицы для каждой строки в файле - хранение 16M хешей в вашей рабочей памяти не должно быть проблемой (зависит от размера хеша, хотя), - тогда вы можете снова выполнить итерацию по своему файлу и убедиться, что что вы записываете только одно вхождение каждого хэша. Вам даже не нужно анализировать ваш CSV, и вам не нужны панды.

import hashlib

with open("input.csv", "r") as f_in, \
        open("output.csv", "w") as f_out:
    seen = set()  # a set to hold our 'visited' lines
    for line in f_in:  # iterate over the input file line by line
        line_hash = hashlib.md5(line.encode()).digest()  # hash the value
        if line_hash not in seen:  # we're seeing this line for the first time
            seen.add(line_hash)  # add it to the hash table
            f_out.write(line)  # write the line to the output

При этом в качестве хэша используется MD5, поэтому для каждой строки потребуется около 16 Б + накладных расходов, но это все равно намного меньше, чем для хранения всего в памяти - можно ожидать ~500 МБ использования памяти для файла CSV с 16 МБ.

Источник

А как насчет симулятора UNIX?

uniq <filename> >outputfile.txt

(что-то вроде того)

Источник

Чтобы расширить мой комментарий к исходному сообщению, иногда можно сохранить СЕРЬЕЗНУЮ память, просто указав типы данных для столбцов. Предположим, у меня есть пример CSV:

chr1, 108000, 25
chr1, 109000, 20
chr1, 110000, 21
chr1, 111000, 26
...
* ~39,000,000 lines (this is a human genome csv coverage file)

Предположим, у меня есть 2 функции, одна из которых определяет dtype, а другая - нет:

import pandas as pd
import numpy as np
import sys

cov_file = sys.argv[1] # command-line file input    
def df_creator_nodtype(infile):
    df = pd.read_csv(infile, names = ['Chr', 'Pos', 'Coverage'])
    return df
def df_creator_dtype(infile):
    df = pd.read_csv(infile, names = ['Chr', 'Pos', 'Coverage'], dtype ={'Chr': 'category', 'Pos': np.float32, 'Coverage': np.float32})
    return df
def mem_usage(pandas_obj):
    if isinstance(pandas_obj,pd.DataFrame):
        usage_b = pandas_obj.memory_usage(deep=True).sum()
    else: # we assume if is not a df it's a series
        usage_b = pandas_obj.memory(deep=True):
    usage_mb = usage_b /1024 ** 2 # bytes to mbytes
    return "{:03.2f} MB".format(usage_mb)
# categories assigned to first column, since they are very repetitive.
df_lowmem = df_creator_dtype(cov_file)
print(len(df_lowmem)) # 38,872,464
print(mem_usage(df_lowmem)) # 333.65 MB

# no categories assigned to first column, pandas tries to guess dtype assigns object
df_highmem = df_creator_nodtype(cov_file)
print(len(df_highmem)) # 38,872,464
print(mem_usage(df_highmem)) # 1974.02 MB

# I don't have many duplicates but here is an example:
df_highmem_dup_dropped = df_highmem.drop_duplicates()
df_lowmem_dup_dropped = df_lowmem.drop_duplicates()
print(len(df_lowmem_dup_dropped)) # 31,332,535
print(len(df_highmem_dropped)) # 31,332,535

Как мы видим, просто изменив назначение dtype столбцу, чтобы pandas интерпретировал его как категорию, а не строку, мы получаем примерно 6-кратное снижение использования mem! Это может быть очень важно при работе с файлами в диапазоне гигабайт. Если у вас есть один избыточный столбец, назначьте его в качестве категории и наблюдайте, как память волшебным образом (или нет) исчезает.

Источник
Другие вопросы по тегам