Нахождение соответствия ключам в двух больших словарях и выполнении его быстро
Я использую "индексные точки между элементами" метод размышления об этом сам, но один способ описать это, который иногда помогает другим получить его, является этим:
mylist[X:Y]
X индекс первого элемента, который Вы хотите.
Y является индексом первого элемента, который Вы не делаете , хотят.
7 ответов
Используйте наборы, потому что они имеют встроенный метод пересечения , который должен быть быстрым:
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
for key in myRDP:
name = myNames.get(key, None)
if name:
print key, name
dict.get возвращает заданное вами значение по умолчанию (в данном случае Нет ), если ключ не существует.
Вы можете сделать это:
for key in myRDP:
if key in myNames:
print key, myNames[key]
Ваша первая попытка была медленной, потому что вы сравнивали каждый ключ в myRDP с каждым ключом в myNames. На алгоритмическом жаргоне, если myRDP имеет n элементов, а myNames имеет m элементов, то этот алгоритм будет принимать O ( n × m ) операции. Для каждого 600 000 элементов это 360 000 000 000 сравнений!
Но проверка того, является ли конкретный элемент ключом словаря, выполняется быстро - на самом деле, это одна из определяющих характеристик словарей. С алгоритмической точки зрения ключ в тесте dict - O (1) или постоянное время. Таким образом, мой алгоритм будет использовать время O ( n ), что составляет одну 600 000-ю времени.
Вы можете начать с поиска общих ключей, а затем перебирать их. Операции набора должны быть быстрыми, потому что они реализованы на C, по крайней мере, в современных версиях Python.
common_keys = set(myRDP).intersection(myNames)
for key in common_keys:
print key, myNames[key]
Вместо этого используйте метод get :
for key in myRDP:
value = myNames.get(key)
if value != None:
print key, "=", value
Скопируйте оба словаря в один словарь / массив. Это имеет смысл, поскольку у вас есть связанные значения 1: 1. Тогда вам понадобится только один поиск, без цикла сравнения, и вы можете напрямую обращаться к соответствующему значению.
Пример результирующего словаря / массива:
[Name][Value1][Value2]
[Actinobacter][GATCGA...TCA][8924342]
[XYZbacter][BCABCA...ABC][43594344]
...
Вот мой код для выполнения пересечений, объединений, различий и других операций над словарями:
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()