Comparando listas masivas de diccionarios en python

Question

Nunca pensé que me encontraría con problemas de velocidad con Python, pero lo hice. Estoy tratando de comparar realmente grandes listas de diccionarios entre sí en función de los valores del diccionario. Comparo dos listas, con la primera como tal

biglist1=[{'transaction':'somevalue', 'id':'somevalue', 'date':'somevalue' ...}, {'transactio':'somevalue', 'id':'somevalue', 'date':'somevalue' ...}, ...] 

Con 'somevalue' de pie para una cadena generado por el usuario, int o decimal. Ahora, la segunda lista es bastante similar, excepto que los valores de id siempre están vacíos, ya que aún no se han asignado.

biglist2=[{'transaction':'somevalue', 'id':'', 'date':'somevalue' ...}, {'transactio':'somevalue', 'id':'', 'date':'somevalue' ...}, ...] 

por lo que quiero obtener una lista de los diccionarios en biglist2 que coinciden con los diccionarios en biglist1 para todas las otras teclas excepto ID.

que he estado haciendo

for item in biglist2: 
    for transaction in biglist1: 
     if item['transaction'] == transaction['transaction']: 
      list_transactionnamematches.append(transaction) 

for item in biglist2: 
    for transaction in list_transactionnamematches: 
     if item['date'] == transaction['date']: 
      list_transactionnamematches.append(transaction) 

... y así sucesivamente, no comparando los valores de ID, hasta que consiga una lista final de los partidos. Dado que las listas pueden ser realmente grandes (alrededor de más de 3000 elementos cada una), Python necesita bastante tiempo para recorrerlas.

Supongo que no es así como se debe hacer este tipo de comparación. ¿Algunas ideas?

Answer 1

Indique los campos que desea utilizar para la búsqueda. O (n + m)

matches = [] 
biglist1_indexed = {} 

for item in biglist1: 
    biglist1_indexed[(item["transaction"], item["date"])] = item 

for item in biglist2: 
    if (item["transaction"], item["date"]) in biglist1_indexed: 
     matches.append(item) 

Esto es probablemente miles de veces más rápido que lo que está haciendo ahora.

Answer 2

Lo que se quiere hacer es utilizar estructuras de datos correctos:

1. crear un diccionario de asignaciones de tuplas de otros valores en el primer diccionario para su identificación.

2. Crea dos conjuntos de tuplas de valores en ambos diccionarios. Luego use set operations para obtener el conjunto de tuplas que desee.

3. Utilice el diccionario del punto 1 para asignar identificadores a esas tuplas.

Answer 3

En O (m * n) ...

for item in biglist2: 
    for transaction in biglist1: 
     if (item['transaction'] == transaction['transaction'] && 
      item['date'] == transaction['date'] && 
      item['foo'] == transaction['foo']) : 

      list_transactionnamematches.append(transaction) 

Answer 4

perdona mis sintaxis de Python oxidado, que ha pasado un tiempo, por lo que consideran que esta parcialmente pseudocódigo

import operator 
biglist1.sort(key=(operator.itemgetter(2),operator.itemgetter(0))) 
biglist2.sort(key=(operator.itemgetter(2),operator.itemgetter(0))) 
i1=0; 
i2=0; 
while i1 < len(biglist1) and i2 < len(biglist2): 
    if (biglist1[i1]['date'],biglist1[i1]['transaction']) == (biglist2[i2]['date'],biglist2[i2]['transaction']): 
     biglist3.append(biglist1[i1]) 
     i1++ 
     i2++ 
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) < (biglist2[i2]['date'],biglist2[i2]['transaction']): 
     i1++ 
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) > (biglist2[i2]['date'],biglist2[i2]['transaction']): 
     i2++ 
    else: 
     print "this wont happen if i did the tuple comparison correctly" 

Esto ordena tanto listas en el mismo orden, por (fecha, transacción). Luego camina a través de ellos uno al lado del otro, caminando a través de cada uno buscando coincidencias relativamente adyacentes. Asume que (fecha, transacción) es único, y que no estoy completamente fuera de mi balanceo con respecto a la clasificación y comparación de tuplas.

Answer 5

El enfoque que probablemente tomaría para esto es hacer una clase muy, muy ligera con una variable de instancia y un método. La variable de instancia es un puntero a un diccionario; el método anula el método especial incorporado __hash__(self), devolviendo un valor calculado a partir de todos los valores en el diccionario excepto id.

A partir de ahí la solución parece bastante obvio: Crear dos diccionarios inicialmente vacías: N y M (. Para no-partidos y partidos) bucle sobre cada lista exactamente una vez y para cada uno de estos diccionarios representan una transacción (llamémoslo Tx_dict), cree una instancia de la nueva clase (a Tx_ptr). Luego, prueba un artículo que coincida con este Tx_ptr en N y M: si no hay un artículo correspondiente en N, inserta el actual Tx_ptr en N; si hay un elemento coincidente en N pero no coincide en M, inserte el Tx_ptr actual en M con el Tx_ptr como una clave y una lista que contiene el Tx_ptr como valor; si hay un elemento coincidente en N y en M, añada el Tx_ptr actual al valor asociado con esa clave en M.

Después de haber examinado cada elemento una vez, su diccionario M contendrá punteros a todas las transacciones que coinciden con otras transacciones, todas prolijamente agrupadas en listas para usted.

Editar: ¡Vaya! Obviamente, la acción correcta si hay un juego Tx_ptr en N pero no en M es insertar un par clave-valor en M con la corriente Tx_ptr como la clave y el valor, una lista de la corriente Tx_ptry la Tx_ptr eso ya estaba en N.

Answer 6

Eche un vistazo a Psyco. Es un compilador de Python que puede crear código de máquina optimizado y muy rápido de su fuente.

http://sourceforge.net/projects/psyco/

Si bien esto no es una solución directa a los problemas de eficiencia de su código, aún podría ayudar a acelerar las cosas sin necesidad de escribir ningún código nuevo. Dicho esto, aún recomiendo optimizar tu código tanto como sea posible Y usar Psyco para exprimir la mayor velocidad posible.

Parte de su guía se refiere específicamente a su uso para acelerar la lista, cadena y funciones pesadas de cálculo numérico.

http://psyco.sourceforge.net/psycoguide/node8.html

Answer 7

también soy un novato. Mi código está estructurado de manera muy similar a la suya.

for A in biglist: 
    for B in biglist: 
     if (A.get('somekey') <> B.get('somekey') and #don't match to itself 
      len(set(A.get('list')) - set(B.get('list'))) > 10: 
      [do stuff...] 

Esta toma horas para ejecutar a través de una lista de diccionarios 10000. Cada diccionario contiene muchas cosas, pero podría extraer solo los ids ('somekey') y las listas ('list') y reescribir como un solo diccionario de 10000 pares clave: value.

Pregunta: ¿cuánto más rápido sería eso? Y supongo que esto es más rápido que usar una lista de listas, ¿verdad?