python - repeated - pandas duplicated

Eliminar filas duplicadas de un archivo grande en Python

Question

Tengo un archivo csv del que quiero eliminar filas duplicadas, pero es demasiado grande para caber en la memoria. Encontré una manera de hacerlo, pero creo que no es la mejor manera.

Cada fila contiene 15 campos y varios cientos de caracteres, y todos los campos son necesarios para determinar la singularidad. En lugar de comparar toda la fila para encontrar un duplicado, comparo hash(row-as-a-string) en un intento de guardar memoria. Establecí un filtro que divide los datos en un número aproximadamente igual de filas (por ejemplo, días de la semana), y cada partición es lo suficientemente pequeña como para que una tabla de búsqueda de valores hash para esa partición se ajuste a la memoria. Paso el archivo una vez para cada partición, comprobando filas únicas y escribiéndolas en un segundo archivo (pseudo código):

import csv

headers={''DayOfWeek'':None, ''a'':None, ''b'':None}
outs=csv.DictWriter(open(''c:/dedupedFile.csv'',''wb'')
days=[''Mon'',''Tue'',''Wed'',''Thu'',''Fri'',''Sat'',''Sun'']

outs.writerows(headers)

for day in days:
    htable={}
    ins=csv.DictReader(open(''c:/bigfile.csv'',''rb''),headers)
    for line in ins:
        hvalue=hash(reduce(lambda x,y:x+y,line.itervalues()))
        if line[''DayOfWeek'']==day:
            if hvalue in htable:
                pass
            else:
                htable[hvalue]=None
                outs.writerow(line)

Una forma en que estaba pensando acelerar esto es encontrar un filtro mejor para reducir el número de pases necesarios. Suponiendo que la longitud de las filas se distribuye uniformemente, tal vez en lugar de

for day in days: 

y

if line[''DayOfWeek'']==day:

tenemos

for i in range(n):

y

if len(reduce(lambda x,y:x+y,line.itervalues())%n)==i:

donde ''n'' tan pequeño como la memoria lo permita. Pero esto sigue usando el mismo método.

Wayne Werner proporcionó una buena solución práctica a continuación; Tenía curiosidad de si había una forma mejor / más rápida / más simple de hacer esto desde la perspectiva del algoritmo.

PD: estoy limitado a Python 2.5.

Answer 1

Su solución original es ligeramente incorrecta: puede tener hashing de diferentes líneas con el mismo valor (una colisión hash), y su código dejaría fuera una de ellas.

En términos de complejidad algorítmica, si esperas relativamente pocos duplicados, creo que la solución más rápida sería escanear el archivo línea por línea, agregar el hash de cada línea (como lo hiciste), pero también almacenar la ubicación de esa línea . Luego, cuando encuentre un hash duplicado, busque el lugar original para asegurarse de que sea un duplicado y no solo una colisión hash, y si es así, busque y omita la línea.

Por cierto, si los valores CSV están normalizados (es decir, los registros se consideran iguales si las filas CSV equivalentes son byte por byte equivalentes), no es necesario involucrar el análisis CSV aquí, simplemente trate las líneas de texto sin formato.

Answer 2

Su método actual no está garantizado para funcionar correctamente.

En primer lugar, existe la pequeña probabilidad de que dos líneas que son realmente diferentes puedan producir el mismo valor hash. hash(a) == hash(b) no siempre significa que a == b

En segundo lugar, está haciendo que la probabilidad sea mayor con su alcaparra "reducir / lambda":

>>> reduce(lambda x,y: x+y, [''foo'', ''1'', ''23''])
''foo123''
>>> reduce(lambda x,y: x+y, [''foo'', ''12'', ''3''])
''foo123''
>>>

Por cierto, would not "" .join ([''foo'', ''1'', ''23'']) ser algo más claro?

BTW2, ¿por qué no usar un set lugar de un dict para htable ?

Aquí hay una solución práctica: obtenga el paquete "core utils" del sitio GnuWin32 e instálelo. Entonces:

1. escriba una copia de su archivo sin los encabezados para (por ejemplo) infile.csv
2. c:/gnuwin32/bin/sort --unique -ooutfile.csv infile.csv
3. lea outfile.csv y escriba una copia con los encabezados añadidos

Para cada uno de los pasos 1 y 3, puede usar un script de Python o algunas de las otras utilidades de GnuWin32 (head, tail, tee, cat, ...).

Answer 3

¿Qué le parece usar el módulo heapq para leer fragmentos de archivo hasta el límite de memoria y escribirlos en las piezas ordenadas (heapq mantiene las cosas siempre ordenadas).

O podría tomar la primera palabra en línea y dividir el archivo en pedazos por eso. Luego puede leer las líneas (tal vez hacer '''' .join (line.split ()) para unificar las separaciones / pestañas en línea si está bien cambiar el espaciado) en orden alfabético despejando el conjunto entre las piezas (el conjunto elimina duplicados) para ordenar las cosas a medias (el conjunto no está en orden, si lo deseas puedes leerlo para almacenar y escribir para obtener el orden ordenado, la última ocurrencia en el juego reemplazando los valores anteriores sobre la marcha) Alternativamente también puedes ordenar la pieza y elimine las líneas duplicadas con la solución groupby de Joe Koberg. Por último, puede unir las piezas (por supuesto, puede escribir a medida que avanza pieza por pieza hasta el archivo final durante la clasificación de las piezas)

Answer 4

Básicamente estás haciendo un tipo de combinación y eliminando entradas duplicadas.

Romper la entrada en piezas de tamaño de memoria, clasificar cada pieza, luego fusionar las piezas y eliminar duplicados es una buena idea en general.

En realidad, hasta un par de conciertos, dejaría que el sistema de memoria virtual lo maneje y simplemente escriba:

input = open(infilename, ''rb'')
output = open(outfile, ''wb'')

for key,  group in itertools.groupby(sorted(input)):
    output.write(key)

Answer 5

Como supongo que tendrás que hacer esto de manera regular (o habrías pirateado un guión de repetición), y mencionaste que te interesaba una solución teórica, esta es una posibilidad.

Lea las líneas de entrada en B-Trees, ordenadas por el valor hash de cada línea de entrada, y escríbalas en el disco cuando se llene la memoria. Nos ocupamos de almacenar, en los B-Trees, las líneas originales unidas al hash (como conjunto, ya que solo nos importan las líneas únicas). Cuando leemos un elemento duplicado, verificamos las líneas establecidas en el elemento almacenado y lo agregamos si se trata de una nueva línea que pasa al hash con el mismo valor.

¿Por qué B-Trees? Requieren menos lecturas de disco cuando solo puede (o desea) leer partes de ellas en la memoria. El grado (número de hijos) en cada nodo depende de la memoria disponible y el número de líneas, pero no desea tener demasiados nodos.

Una vez que tenemos esos B-Trees en el disco, comparamos el elemento más bajo de cada uno de ellos. Eliminamos el más bajo de todos, de todos los B-Trees que lo tienen. Fusionamos sus conjuntos de líneas, lo que significa que no tenemos duplicados para esas líneas (y también que no tenemos más líneas que hash para ese valor). Luego escribimos las líneas de esta fusión en la estructura csv de salida.

Podemos separar la mitad de la memoria para leer B-Trees, y la mitad para mantener la salida csv en la memoria durante un tiempo. Descargamos el csv al disco cuando su mitad está llena, añadiendo lo que ya se ha escrito. La cantidad de cada B-Tree que leemos en cada paso se puede calcular aproximadamente por (available_memory / 2) / number_of_btrees, redondeando para que podamos leer los nodos completos.

En pseudo-Python:

ins = DictReader(...)
i = 0
while ins.still_has_lines_to_be_read():
    tree = BTree(i)
    while fits_into_memory:
        line = ins.readline()
        tree.add(line, key=hash)
    tree.write_to_disc()
    i += 1
n_btrees = i

# At this point, we have several (n_btres) B-Trees on disk
while n_btrees:
    n_bytes = (available_memory / 2) / n_btrees
    btrees = [read_btree_from_disk(i, n_bytes)
              for i in enumerate(range(n_btrees))]
    lowest_candidates = [get_lowest(b) for b in btrees]
    lowest = min(lowest_candidates)
    lines = set()
    for i in range(number_of_btrees):
        tree = btrees[i]
        if lowest == lowest_candidates[i]:
            node = tree.pop_lowest()
            lines.update(node.lines)
        if tree.is_empty():
        n_btrees -= 1

    if output_memory_is_full or n_btrees == 0:
        outs.append_on_disk(lines)

Answer 6

Si quieres una forma realmente simple de hacerlo, simplemente crea una base de datos sqlite:

import sqlite3
conn = sqlite3.connect(''single.db'')
cur = conn.cursor()
cur.execute("""create table test(
f1 text,
f2 text,
f3 text,
f4 text,
f5 text,
f6 text,
f7 text,
f8 text,
f9 text,
f10 text,
f11 text,
f12 text,
f13 text,
f14 text,
f15 text,
primary key(f1,  f2,  f3,  f4,  f5,  f6,  f7,  
            f8,  f9,  f10,  f11,  f12,  f13,  f14,  f15))
"""
conn.commit()

#simplified/pseudo code
for row in reader:
    #assuming row returns a list-type object
    try:
        cur.execute(''''''insert into test values(?, ?, ?, ?, ?, ?, ?, 
                       ?, ?, ?, ?, ?, ?, ?, ?)'''''', row)
        conn.commit()
    except IntegrityError:
        pass

conn.commit()
cur.execute(''select * from test'')

for row in cur:
    #write row to csv file

Entonces usted no tendría que preocuparse por la lógica de comparación usted mismo, simplemente deje que sqlite se encargue de eso. Probablemente no sea mucho más rápido que usar las cuerdas, pero probablemente sea mucho más fácil. Por supuesto, modificaría el tipo almacenado en la base de datos si quisiera, o no según sea el caso. Por supuesto, dado que ya está convirtiendo los datos en una cadena, podría tener un campo en su lugar. Un montón de opciones aquí.