通過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))，所以快速搜索可以節省更多。