Znajdowanie pasujących kluczy w dwóch dużych słownikach i robienie tego szybko

Question

Próbuję znaleźć odpowiednie klucze w dwóch różnych słownikach. Każdy ma około 600 000 wpisów.

Powiedz na przykład:

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

chcę wydrukować wartości dla Actinobacter (8924342), ponieważ odpowiada wartości w myRDP.

Poniższy kod działa, ale jest bardzo powolny:

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

Próbowałem następujących ale zawsze skutkuje rzucony wyjątek KeyError:

for key in myRDP: 
     print myNames[key] 

tam jest chyba funkcja wdrożone w C za to? Przeszukałem go, ale nic nie działa.

Dzięki.

Answer 1

używać zestawów, ponieważ mają wbudowany intersection metody, które powinny być szybki:

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

Można to zrobić:

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

Twoja pierwsza próba była powolna, ponieważ zostały porównując każdy klucza w myRDP z każdy kluczowego w myNames. W żargonie algorytmicznego jeśli myRDP ma n elementów i myNames ma m elementów, to algorytm się O (n x m) operacji. Dla każdego z elementów 600 tysięcy, to jest 360 000 000 000 porównań!

Ale sprawdzenie, czy dany element jest kluczem do słownika, jest szybkie - w rzeczywistości jest to jedna z cech charakterystycznych słowników. W kategoriach algorytmicznych testem key in dict jest O (1) lub stały czas. Mój algorytm zajmie więc O (n) czas, który jest jednym 600 000-tym razem.

Answer 3

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

dict.get zwraca wartość domyślną ją podać (w tym przypadku, None) jeżeli klucz nie istnieje.

Answer 4

pomocą metody get Zamiast:

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

Answer 5

Kopiuj obu słowników w jeden słownik/tablicy. Ma to sens, ponieważ masz powiązane wartości 1: 1. Następnie potrzebujesz tylko jednego wyszukiwania, bez pętli porównania i możesz uzyskać bezpośredni dostęp do powiązanej wartości.

Przykład Wynikające słownik/Array:

[Name][Value1][Value2] 

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

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

...

Answer 6

Można zacząć od znalezienia wspólnych kluczy, a następnie powtórzyć je.Operacje ustawiania powinny być szybkie, ponieważ są zaimplementowane w C, przynajmniej we współczesnych wersjach Pythona.

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

Answer 7

Oto mój kod robi skrzyżowań, związki, różnice i inne operacje ustawiony na słownikach:

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() 

Answer 8

w Pythonie 3 można po prostu zrobić

myNames.keys() & myRDP.keys()