Búsqueda de una cadena en un archivo de texto grande: creación de perfiles de varios métodos en python

Question

Esta pregunta se ha hecho muchas veces. Después de pasar algún tiempo leyendo las respuestas, he hecho un poco de perfiles rápida para probar los diferentes métodos mencionados anteriormente ...

• Tengo un archivo 600 MB con 6 millones líneas de cuerdas (Categoría caminos del proyecto DMOZ).
• La entrada en cada línea es única.
• Quiero carga el archivo vez & seguir buscando de partidos en los datos

Los tres métodos que he intentado debajo de la lista el tiempo necesario para cargar el archivo, el tiempo de búsqueda para un partido uso & recuerdo negativo en el administrador de tareas

---

s

1) set : 
    (i) data = set(f.read().splitlines()) 
    (ii) result = search_str in data 

tiempo de carga a ~, ~ 0.0s Tiempo de búsqueda, uso de memoria ~ 1,2 GB

---

2) list : 
    (i) data = f.read().splitlines() 
    (ii) result = search_str in data 

tiempo de carga ~ 6s, el tiempo de búsqueda ~ 0.36s , Uso de memoria ~ 1.2GB

s

---

3) mmap : 
    (i) data = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) 
    (ii) result = data.find(search_str) 

tiempo de carga a ~, ~ 5.4s Tiempo de búsqueda, uso de memoria ~ NA

---

4) Hash lookup (using code from @alienhard below): 

Tiempo de carga ~ 65 años, Tiempo de búsqueda ~ 0.0s, uso de memoria ~ 250MB

0s 0s

---

5) File search (using code from @EOL below): 
    with open('input.txt') as f: 
     print search_str in f #search_str ends with the ('\n' or '\r\n') as in the file 

tiempo de carga a ~, ~ 3.2s Tiempo de búsqueda, Uso de memoria ~ NA

---

6) sqlite (with primary index on url): 

tiempo de carga ~, Buscar tiempo ~ 0.0s, uso de memoria ~ NA

---

Por mi caso de uso, parece ir con el conjunto es la mejor opción, siempre y cuando tengo suficiente memoria disponible. Tenía la esperanza de obtener algunos comentarios sobre estas preguntas:

1. Una alternativa mejor por ejemplo, sqlite?
2. Formas de mejorar el tiempo de búsqueda utilizando mmap. Tengo una configuración de 64 bits. [editar] p. Ej. filtros de floración
3. A medida que el tamaño del archivo crece a un par de GB, ¿hay alguna manera de seguir usando el "conjunto", p. dividirlo en lotes ..

[Editar 1] P.S. Necesito buscar frecuentemente, agregar/eliminar valores y no puedo usar una tabla hash sola porque necesito recuperar los valores modificados más adelante.

¡Cualquier comentario/sugerencia es bienvenida!

[editar 2] Actualizar con los resultados de los métodos sugeridos en las respuestas [editar 3] UPDATE con resultados sqlite

solución: Sobre la base de toda la retroalimentación de perfiles &, creo que voy a ir con SQLite. La segunda alternativa es el método 4. Una desventaja de sqlite es que el tamaño de la base de datos es más del doble del archivo csv original con direcciones URL. Esto se debe al índice principal en la url

Answer 1

Variante 1 es grande si necesita iniciar muchas búsquedas secuenciales. Dado que set es internamente una tabla hash, es bastante buena en la búsqueda. Sin embargo, lleva tiempo construir y solo funciona bien si sus datos se ajustan a la memoria RAM.

La variante 3 es buena para archivos muy grandes, porque tiene un montón de espacio de direcciones para asignarlos y el sistema operativo almacena suficientes datos en la memoria caché. Usted hace un escaneo completo; puede volverse bastante lento una vez que los datos se detienen para que quepan en la RAM.

SQLite es definitivamente una buena idea si necesita varias búsquedas en fila y no puede ajustar los datos en la memoria RAM. Cargue sus cadenas en una tabla, construya un índice, y SQLite construya un buen árbol en b para usted. El árbol puede caber en la RAM incluso si los datos no lo hacen (es un poco como lo que @alienhard propuso), e incluso si no lo hace, la cantidad si la E/S necesaria es dramáticamente más baja. Por supuesto, debe crear una base de datos SQLite basada en disco. Dudo que SQLite basado en la memoria venza significativamente a la Variante 1.

Answer 2

¿qué tal una solución de indexación de texto?

usaría Lucene en el mundo Java, pero hay un motor de Python llamada Whoosh

https://bitbucket.org/mchaput/whoosh/wiki/Home

Answer 3

Custom Search tabla hash con cuerdas externalizados

Para obtener el tiempo de acceso rápido y un menor consumo de memoria puede hacer lo siguiente:

• para cada línea calcule un hash de cadena y agréguelo a una tabla hash, por ejemplo, index[hash] = position (do no almacene la cadena). Si hay una colisión, guarde todas las posiciones de archivo para esa clave en una lista.
• para buscar una cadena, calcular su hash y buscarlo en la tabla. Si se encuentra la clave, lea la cadena al position del archivo para verificar que realmente tiene una coincidencia. Si hay varias posiciones, marque cada una hasta encontrar una coincidencia o ninguna.

Edición 1: reemplazado número_línea por la posición (como se señaló por un comentarista, uno necesita obviamente la posición real y se alinea números)

Edit 2: proporcionar código para una aplicación con una tabla hash personalizada , lo que demuestra que este enfoque es más eficiente de la memoria que los otros enfoques mencionados:

from collections import namedtuple 
Node = namedtuple('Node', ['pos', 'next']) 

def build_table(f, size): 
    table = [ None ] * size 
    while True: 
     pos = f.tell() 
     line = f.readline() 
     if not line: break 
     i = hash(line) % size 
     if table[i] is None: 
      table[i] = pos 
     else: 
      table[i] = Node(pos, table[i]) 
    return table 

def search(string, table, f): 
    i = hash(string) % len(table) 
    entry = table[i] 
    while entry is not None: 
     pos = entry.pos if isinstance(entry, Node) else entry 
     f.seek(pos) 
     if f.readline() == string: 
      return True 
     entry = entry.next if isinstance(entry, Node) else None 
    return False 

SIZE = 2**24 
with open('data.txt', 'r') as f: 
    table = build_table(f, SIZE) 
    print search('Some test string\n', table, f) 

el hash de una línea sólo se utiliza para indexar en la tabla (si usamos un diccionario normal, los valores hash también serían almacenado como llaves). La posición del archivo de la línea se almacena en el índice dado. Las colisiones se resuelven con el encadenamiento, es decir, creamos una lista vinculada. Sin embargo, la primera entrada nunca se envuelve en un nodo (esta optimización hace que el código sea un poco más complicado pero ahorra bastante espacio).

Para un archivo con 6 millones de líneas elegí un tamaño de tabla hash de 2^24. Con mis datos de prueba obtuve 933132 colisiones. (Una tabla hash de la mitad del tamaño era comparable en consumo de memoria, pero resultó en más colisiones. Desde más colisiones significa más acceso a los archivos para las búsquedas, yo prefiero usar una mesa grande.)

Hash table: 128MB (sys.getsizeof([None]*(2**24))) 
Nodes:  64MB (sys.getsizeof(Node(None, None)) * 933132) 
Pos ints: 138MB (6000000 * 24) 
----------------- 
TOTAL:  330MB (real memory usage of python process was ~350MB) 

Answer 4

Sin crear un archivo de índice, su búsqueda será lenta, y esta no es una tarea tan simple. Así que es mejor utilizar el software ya desarrollado. La mejor forma será usar Sphinx Search Engine.

Answer 5

También puede probar

with open('input.txt') as f: 
    # search_str is matched against each line in turn; returns on the first match: 
    print search_str in f 

con search_str terminando con la secuencia de nueva línea adecuada ('\n' o '\r\n'). Esto debería usar poca memoria, ya que el archivo se lee progresivamente. También debería ser bastante rápido, ya que solo se lee una parte del archivo.

Answer 6

Supongo que muchas de las rutas comienzan de la misma manera en DMOZ. Debe usar un trie data structure y almacenar los caracteres individuales en los nodos.

Las pruebas tienen O (m) tiempo de búsqueda (donde m es la longitud de la clave) también ahorran mucho espacio, cuando se guardan diccionarios de gran tamaño o datos tipo árbol.

También podría almacenar partes de ruta en los nodos para reducir el número de nodos; esto se llama Patricia Trie. Pero eso hace que la búsqueda sea más lenta por el tiempo promedio de comparación de la longitud de la cadena. Vea la pregunta Trie (Prefix Tree) in Python para obtener más información sobre implementaciones.

Hay un par de implementaciones en Python Package Index, pero no son muy buenas. He escrito uno en Ruby y en Common Lisp, que es especialmente adecuado para esta tarea. Si lo preguntas bien, podría publicarlo como código abierto ... :-)