通过cs快速查找字符串

Question

我正在编写一个小程序来比较Python2.7上的两个csv文件。你知道吗

我使用csv模块并执行以下操作：

for row in file1:
"looking if row in file1 is in file2"

这个程序工作得很好，但是速度很慢，因为如果两个文件中都有一个字符串，它必须逐行检查。从第一行到最后一行可能需要2分钟，但如果我使用记事本或任何文本编辑程序中的任何查找工具搜索字符串，它会立即找到。你知道吗

为什么会发生这种情况？
是否有任何方法或模块来实现文件中的快速搜索？你知道吗

import csv
import os

f1 = file('tarifa_ek_tot.csv', 'r') #general
f2 = file('ek.csv', 'r') #filtro
f3 = file('sort_ek_tar.csv', 'w') #archivo salida
f4 = file('informe.csv', 'w') #archivo informe salida

#configuracion
campo_clave = 0 #campo clave
#campo_comp = 5  #campo a comparar
modo_prueba = True
fila = True
num_campos = 4
num_filas_filtro = 601
num_filas_general = 5175
ultima_posicion_encontrada = 0

#cond = 1 #copiar si ha subido
cond = 2 #copiar si ha cambiado
#cond = 3 #copiar si ha bajado

#codi,desc,tar,dte

#declaracion archivos
general = csv.reader(f1)
filtro_nostre = csv.reader(f2)
archivo_salida = csv.writer(f3)
salida_informe = csv.writer(f4)

#variables
filtro = list(filtro_nostre)
list_general = list(general)
fila_filtro = 1
found = False
num_comp_filtro= 0
encontrado = 0
num_coincidencias = 0
num_variaciones = 0
n = 0
num_no_encontrados = 0

#por cada fila en el archivo filtro
for row_filtro in filtro:
    filtro_nostre = csv.reader(f2)
    filtro = list(filtro_nostre)
    num_comp_filtro = num_comp_filtro + 1


    num_comp_general = 0


    #for index,row_general in enumerate(general):
    for i in range(n,num_filas_general):
    #for row_general in range(n,num_filas_general):

        os.system ("cls")
        print "comparando reg general num: "+str(num_comp_general)+" n="+str(n)+" reg filtro a comparar:"+str(num_filas_filtro)
        print " num reg comprobados: "+str(num_comp_filtro)+" num reg coincidentes: "+str(num_coincidencias)
        print "ultima posicion encontrada: "+str(ultima_posicion_encontrada)
        print "comprobando registro:"+str(row_filtro[campo_clave])#+" cod_gen:"+str(list_general[campo_clave])
        print "numero registros no encontrado:"+str(num_no_encontrados)     

        #print "comparem general:"+str(row_general[campo_clave])+" amb filtre:"+str(row_filtro[campo_clave])
        #print "index: "+str(index)#+" num fila: "+str(row_general)


        if list_general[n][campo_clave] == row_filtro[campo_clave]:
            #print "comparem:"+str(row_general[campo_clave])+" amb:"+str(row_filtro[campo_clave])
            num_coincidencias = num_coincidencias + 1       
            i = 0
            fila_copiar = ""
            while i < num_campos:
            #while i < 1:
                print str(i)
                if i == 0:
                    fila_copiar = list_general[n][i]
                    #print str(fila_copiar)
                else:               
                    fila_copiar = fila_copiar+","+list_general[n][i]
                    #print str(fila_copiar)
                i = i + 1


            print "fila a copiar: "+str(fila_copiar)
            archivo_salida.writerow([fila_copiar])
            encontrado = 1
            ultima_posicion_encontrada = n
            break   #salimos del if si lo encuentra
        else:
            encontrado = 0


        num_comp_general = num_comp_general+1            

        n = n + 1 
        #ultima_posicion = n#guardema la ultima posicio     

    if encontrado <> 1 and n == num_filas_general:
        n = ultima_posicion_encontrada
        num_no_encontrados = num_no_encontrados + 1
        #copiamos el campo clave del registro no encontrado del filtro
        codigo_no_encontrado = str(row_filtro[campo_clave])
        salida_informe.writerow(codigo_no_encontrado)

    print ""    
    print "*****************informe resultados *******************************"  
    print "n: "+str(n)
    print "numero registros comparados filtro: "+str(num_comp_filtro)
    print "numero registros coincidentes: "+str(num_coincidencias)     
    print "numero registros no encontrados: " +str(num_no_encontrados)
    print "archivo de salida: "+str(f3.name)
    print "archivo de informe: "+str(f4.name)

    fila_filtro = fila_filtro + 1
    fila_general = 1
    #print 'fila_general:'+str(fila_general)+'  fila_filtro:'+str(fila_filtro)    

#mensajes de alerta
if num_coincidencias < num_comp_filtro:
    print "atencion: algunas filas no se encontraron !!!!!!!!!!!!!!!!!!!!!"

f1.close()
f2.close()
f3.close()
f4.close()

编辑：
我现在知道我的问题不充分。你知道吗

我一直在尝试一个简单的算法在一个大的文本文件中查找字符串，它必须逐行查找字符串，但是如果我使用记事本或windows简单文本编辑器，它会立即找到字符串。你知道吗

哪种算法使用这个程序？你知道吗

是因为他们使用c++语言还是因为使用原始的windows dll？或者是因为python是一种解释语言？你知道吗

这就是我真正想知道的

Answer 1

您的算法是O(N^2)，因为它迭代了file1中的行，并为每一行迭代file2中的行以找到匹配项。你知道吗

如果您将搜索操作（在帖子中：“查找file1中的行是否在file2中”）加速到O(log(N))，您的总体复杂性将是O(N*log(N))。你知道吗

我建议把这篇文章作为一个起点：Most efficient way for a lookup/search in a huge list (python)

另一种方法是在行匹配之前对文件进行排序。在两个排序的文件中查找匹配项将是O(N)。但是一个好的排序算法是O(N*log(N))本身，所以快速搜索可以节省同样多的钱。你知道吗