Encuentra todos los números en un archivo que no están en otro archivo en Python

arrays file

Question

Hay dos archivos, digamos FileA y FileB y necesitamos encontrar todos los números que están en FileA que no están en FileB. Todos los números en el Archivo A están ordenados y todos los números en el Archivo B están ordenados. Por ejemplo,

Entrada:

FileA = [1, 2, 3, 4, 5, ...]
FileB = [1, 3, 4, 6, ...]

Salida:

[2, 5, ...]

La memoria es muy limitada e incluso un archivo completo no se puede cargar en la memoria a la vez. También se necesita una complejidad lineal o menor en el tiempo.

Entonces, si los archivos son lo suficientemente pequeños como para caber en la memoria, podríamos cargarlos e inicializar su contenido como dos conjuntos y luego tomar una diferencia de conjunto para que el problema se resuelva en O (1) o complejidad de tiempo constante.

set(contentsofFileA)-set(contentsofFileB)

Pero como los archivos son tan grandes, no podrán cargarse completamente en la memoria, por lo que esto no es posible.

Además, otro enfoque sería utilizar un método de fuerza bruta con procesamiento por lotes. Entonces, cargamos un fragmento o lote de datos de FileA y luego un lote de FileB y luego lo comparamos y luego el siguiente fragmento de FileB y así sucesivamente. Luego, después de verificar el fragmento FileA sobre todos los elementos en FileB, cargue el siguiente lote de FileA y esto continúa. Pero esto crearía una O (n ^ 2) o una complejidad de tiempo cuadrática y no eficiente para un archivo muy grande con entradas grandes.

El problema debe resolverse en una complejidad lineal o menor y sin cargar todos los archivos en la memoria. ¿Alguna ayuda?

Answer 1

A medida que se ordenan los archivos, puede iterar a través de cada línea a la vez, si la línea del archivo A es menor que la línea del archivo B, entonces sabe que A no está en B, entonces incremente el archivo A solo y luego verifique nuevamente. Si la línea en A es mayor que la línea en B, entonces sabe que B no está en A, por lo que solo incrementa el archivo B. Si A y B son iguales, entonces sabe que la línea está en ambos, así que incremente ambos archivos. mientras que en su pregunta original declaró que estaba interesado en las entradas que están en A pero no en B, esta respuesta extenderá eso y también dará entradas en B y no A. Esto extiende la flexibilidad pero aún le permite imprimir solo las de A y B .

def strip_read(file):
    return file.readline().rstrip()

in_a_not_b = []
in_b_not_a = []
with open("fileA") as A:
    with open("fileB") as B:
        Aline = strip_read(A)
        Bline = strip_read(B)
        while Aline or Bline:
            if Aline < Bline and Aline:
                in_a_not_b.append(Aline)
                Aline = strip_read(A)
            elif Aline > Bline and Bline:
                in_b_not_a.append(Bline)
                Bline = strip_read(B)
            else:
                Aline = strip_read(A)
                Bline = strip_read(B)

print("in A not in B", in_a_not_b, "/nin B not in A", in_b_not_a)

SALIDA para mis archivos de muestra

in A not in B [''2'', ''5'', ''7''] 
in B not in A [''6'']

Answer 2

Puede combinar itertools.groupby ( doc ) y heapq.merge ( doc ) para iterar a través de FileA y FileB perezosamente (¡funciona mientras los archivos estén ordenados!)

FileA = [1, 1, 2, 3, 4, 5]
FileB = [1, 3, 4, 6]

from itertools import groupby
from heapq import merge

gen_a = ((v, ''FileA'') for v in FileA)
gen_b = ((v, ''FileB'') for v in FileB)

for v, g in groupby(merge(gen_a, gen_b, key=lambda k: int(k[0])), lambda k: int(k[0])):
    if any(v[1] == ''FileB'' for v in g):
        continue
    print(v)

Huellas dactilares:

2
5

EDITAR (Lectura de archivos):

from itertools import groupby
from heapq import merge

gen_a = ((int(v.strip()), 1) for v in open(''3k.txt''))
gen_b = ((int(v.strip()), 2) for v in open(''2k.txt''))

for v, g in groupby(merge(gen_a, gen_b, key=lambda k: k[0]), lambda k: k[0]):
    if any(v[1] == 2 for v in g):
        continue
    print(v)

Punto de referencia:

Generando archivos con 10_000_000 elementos:

seq 0 3 10000000 > 3k.txt
seq 0 2 10000000 > 2k.txt

El guión tarda unos 10 segundos en completarse:

real    0m10,656s
user    0m10,557s
sys 0m0,076s

Answer 3

Si desea leer los archivos línea por línea, ya que no tiene mucha memoria y necesita una solución lineal, puede hacerlo con iter si sus archivos están basados ​​en líneas, de lo contrario, vea this :

Primero en su terminal puede hacer esto para generar algunos archivos de prueba:

seq 0 3 100 > 3k.txt
seq 0 2 100 > 2k.txt

Luego ejecutas este código:

i1 = iter(open("3k.txt"))
i2 = iter(open("2k.txt"))
a = int(next(i1))
b = int(next(i2))
aNotB = []
# bNotA = []
while True:
    try:
        if a < b:
            aNotB += [a]
            a = int(next(i1, None))
        elif a > b:
            # bNotA += [a]
            b = int(next(i2, None))
        elif a == b:
            a = int(next(i1, None))
            b = int(next(i2, None))
    except TypeError:
        if not b:
            aNotB += list(i1)
            break
        else:
            # bNotA += list(i1)
            break
print(res)

Salida:

[3, 9, 15, 21, 27, 33, 39, 45, 51, 57, 63, 69, 75, 81, 87, 93, 99] Si desea tanto el resultado para aNotB como bNotA, puede descomentar esos dos líneas.

Comparación de tiempos con la respuesta de Andrej Kesely:

$ seq 0 3 1000000 > 3k.txt
$ seq 0 2 1000000 > 2k.txt
$ time python manual_iter.py        
python manual_iter.py  0.38s user 0.00s system 99% cpu 0.387 total
$ time python heapq_groupby.py        
python heapq_groupby.py  1.11s user 0.00s system 99% cpu 1.116 total

Answer 4

Una solución simple basada en la lectura de archivos (asumiendo que cada línea contiene un número):

results = []
with open(''file1.csv'') as file1, open(''file2.csv'') as file2:
        var1 = file1.readline()
        var2 = file2.readline()
        while var1:
            while var1 and var2:
                if int(var1) < int(var2):
                    results.append(int(var1))
                    var1 = file1.readline()
                elif int(var1) > int(var2):
                    var2 = file2.readline()
                elif int(var1) == int(var2):
                    var1 = file1.readline()
                    var2 = file2.readline()
            if var1:
                results.append(int(var1))
                var1 = file1.readline()
print(results)
output = [2, 5, 7, 9]