通过csv快速查找字符串

Question

我正在编写一个小编以比较python 2.7上的两个csv文件。

我用csv模块和喜欢做的事情：

为行文件1：
“看，如果行文件1在文件2”

的前卫作品不错，但很慢，因为如果一个字符串在两个文件中都必须逐行检查。从第一行到最后一行可能是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中找到匹配。

如果加快搜索操作（在您的文章：“看，如果行的文件1在文件2”）到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))，所以快速搜索可以节省更多。