Encontrar las claves coincidentes en dos grandes diccionarios y hacerlo rápido

Question

Estoy tratando de encontrar las teclas correspondientes en dos diccionarios diferentes. Cada uno tiene unos 600k entradas.

Digamos por ejemplo:

    myRDP = { 'Actinobacter': 'GATCGA...TCA', 'subtilus sp.': 'ATCGATT...ACT' }
    myNames = { 'Actinobacter': '8924342' }

Quiero imprimir el valor de Actinobacter (8.924.342) ya que coincide con un valor myRDP.

El siguiente código funciona, pero es muy lento:

    for key in myRDP:
        for jey in myNames:
            if key == jey:
                print key, myNames[key]

He intentado lo siguiente pero siempre se traduce en una KeyError:

    for key in myRDP:
        print myNames[key]

¿Hay tal vez una función implementada en C para hacer esto? He buscado en Google en todo pero nada parece funcionar.

Gracias.

Answer 1

Utilice conjuntos, porque tienen incorporado un método intersection que debe ser rápido:

myRDP = { 'Actinobacter': 'GATCGA...TCA', 'subtilus sp.': 'ATCGATT...ACT' }
myNames = { 'Actinobacter': '8924342' }

rdpSet = set(myRDP)
namesSet = set(myNames)

for name in rdpSet.intersection(namesSet):
    print name, myNames[name]

# Prints: Actinobacter 8924342

Answer 2

Usted puede hacer esto:

for key in myRDP:
    if key in myNames:
        print key, myNames[key]

Su primer intento fue lento porque hacer una comparación cada tecla en myRDP con cada tecla en myNames. En la jerga algorítmico, si myRDP ha n elementos y myNames tiene m elementos, a continuación, que el algoritmo tomarían O ( n × m ) operaciones. Para 600k elementos cada uno, esto es 360,000,000,000 comparaciones!

Pero probando si un elemento particular es una clave de un diccionario es rápido - de hecho, esta es una de las características definitorias de los diccionarios. En términos algorítmicos, la prueba key in dict es O (1), o constante de tiempo. Así que mi algoritmo toma O (n ) el tiempo, que es uno 600000a del tiempo.

Answer 3

en Python 3 que sólo puede hacer

myNames.keys() & myRDP.keys()

Answer 4

for key in myRDP:
    name = myNames.get(key, None)
    if name:
        print key, name

dict.get devuelve el valor por defecto que le dan (en este caso, None) si no existe la clave.

Answer 5

Se podría empezar por encontrar las claves comunes y luego iterar sobre ellos. operaciones de conjunto debe ser rápida, ya que se implementan en C, por lo menos en las versiones modernas de Python.

common_keys = set(myRDP).intersection(myNames)
for key in common_keys:
    print key, myNames[key]

Answer 6

Utilice el método get lugar:

 for key in myRDP:
    value = myNames.get(key)
    if value != None:
      print key, "=", value

Answer 7

La forma mejor y más fácil sería simplemente realizar operaciones con el conjunto común (Python 3).

a = {"a": 1, "b":2, "c":3, "d":4}
b = {"t1": 1, "b":2, "e":5, "c":3}
res = a.items() & b.items() # {('b', 2), ('c', 3)} For common Key and Value
res = {i[0]:i[1] for i in res}  # In dict format
common_keys = a.keys() & b.keys()  # {'b', 'c'}

Saludos!

Answer 8

Copie ambos diccionarios en un diccionario / matriz. Esto tiene sentido ya que tienes 1: 1 los valores relacionados. A continuación, necesita sólo una búsqueda, sin lazo de comparación, y puede acceder al valor relacionado directamente.

Ejemplo resultante Dictionary / matriz:

[Name][Value1][Value2]

[Actinobacter][GATCGA...TCA][8924342]

[XYZbacter][BCABCA...ABC][43594344]

...

Answer 9

Aquí está mi código para hacer intersecciones, uniones, las diferencias y otras operaciones de conjuntos en los diccionarios:

class DictDiffer(object):
    """
    Calculate the difference between two dictionaries as:
    (1) items added
    (2) items removed
    (3) keys same in both but changed values
    (4) keys same in both and unchanged values
    """
    def __init__(self, current_dict, past_dict):
        self.current_dict, self.past_dict = current_dict, past_dict
        self.set_current, self.set_past = set(current_dict.keys()), set(past_dict.keys())
        self.intersect = self.set_current.intersection(self.set_past)
    def added(self):
        return self.set_current - self.intersect 
    def removed(self):
        return self.set_past - self.intersect 
    def changed(self):
        return set(o for o in self.intersect if self.past_dict[o] != self.current_dict[o])
    def unchanged(self):
        return set(o for o in self.intersect if self.past_dict[o] == self.current_dict[o])

if __name__ == '__main__':
    import unittest
    class TestDictDifferNoChanged(unittest.TestCase):
        def setUp(self):
            self.past = dict((k, 2*k) for k in range(5))
            self.current = dict((k, 2*k) for k in range(3,8))
            self.d = DictDiffer(self.current, self.past)
        def testAdded(self):
            self.assertEqual(self.d.added(), set((5,6,7)))
        def testRemoved(self):      
            self.assertEqual(self.d.removed(), set((0,1,2)))
        def testChanged(self):
            self.assertEqual(self.d.changed(), set())
        def testUnchanged(self):
            self.assertEqual(self.d.unchanged(), set((3,4)))
    class TestDictDifferNoCUnchanged(unittest.TestCase):
        def setUp(self):
            self.past = dict((k, 2*k) for k in range(5))
            self.current = dict((k, 2*k+1) for k in range(3,8))
            self.d = DictDiffer(self.current, self.past)
        def testAdded(self):
            self.assertEqual(self.d.added(), set((5,6,7)))
        def testRemoved(self):      
            self.assertEqual(self.d.removed(), set((0,1,2)))
        def testChanged(self):
            self.assertEqual(self.d.changed(), set((3,4)))
        def testUnchanged(self):
            self.assertEqual(self.d.unchanged(), set())
    unittest.main()