Python - что-то быстрее, чем 2 вложенных для петель

Question

def fancymatching(fname1, fname2): 
#This function will do much smarter and fancy kinds of compares 
    if (fname1 == fname2): 
     return 1 
    else: 
     return 0 

personlist = [ 
{ 
'pid':'1', 
'fname':'john', 
'mname':'a', 
'lname':'smyth', 
},{ 
'pid':'2', 
'fname':'john', 
'mnane':'a', 
'lname':'smith', 
},{ 
'pid':'3', 
'fname':'bob', 
'mname':'b', 
'lname':'nope', 
} 
] 

for person1 in personlist: 
    for person2 in personlist: 
     if person1['pid'] >= person2['pid']: 
      #don't check yourself, or ones that have been 
     continue 
     if fancymatching(person1['fname'], person2['fname']): 
      print (person1['pid'] + " matched " + person2['pid']) 

Я пытаюсь улучшить идею вышеуказанного кода. Он работает, но если personlist становится очень большим (скажем, миллионы), я чувствую, что для циклов должно быть что-то быстрее, чем 2.

Что делает код, это перечислить список словарей и запустить функцию fancy fuzzzy matching, соответствующую значениям каждого словаря по отношению друг к другу. Так что это не так просто, как просто сравнение всех словарей с другими. Я бы хотел, чтобы запустить функцию в каждом словаре, возможно, 2 для циклов - это правильный способ сделать это? Любые предложения будут полезны!

Answer 1

Вы можете использовать itertools.combinations, который по существу такой же двойной цикл, но он перебирает быстрее, потому что это написано в C (что только снижает постоянный коэффициент, вы до сих пор поведение O(n**2) во время выполнения), и вам не нужны if person1['pid'] >= person2['pid']: continue больше (который уже встроен в функцию combinations).

from itertools import combinations 

for person1, person2 in combinations(personlist, 2): 
    print(person1['fname'], person2['fname']) 

который печатает:

('john', 'john') 
('john', 'bob') 
('john', 'bob') 

---

Однако если ваш fancymatching позволяет ему то вы могли бы также групповые (O(n) выполнения) ваши ценности. Например, в вашем случае вы соответствуете только идентичным 'fname' -значениям.

>>> matches = {} 
>>> for person in personlist: 
...  matches.setdefault(person['fname'], []).append(person) 
>>> matches 
{'bob': [{'fname': 'bob', 'lname': 'nope', 'mname': 'b', 'pid': '3'}], 
'john': [{'fname': 'john', 'lname': 'smyth', 'mname': 'a', 'pid': '1'}, 
      {'fname': 'john', 'lname': 'smith', 'mnane': 'a', 'pid': '2'}]} 

Но это возможно, только если ваш fancymatching допускает такую ​​группировку. Это верно для вашего случая, но если это сложнее, этого может и не быть.

Answer 2

Добавление ответа MSeifert в, если соответствие зависит от fname1 == fname2, то вы можете сортировать и затем группы список: а именно:

from itertools import combinations, groupby 

keyfunc = lambda x: x['fname'] 
data = sorted(personlist, key= keyfunc) 
for key, group in groupby(data, key): 
    #every element in group will now match 
    for person1, person2 in combinations(group, 2): 
     print(person1['fname'], person2['fname']) 

Очевидно, что если вы измените функцию соответствия вам нужно будет изменить ваш чтобы он возвращал одно и то же значение для любых элементов, которые соответствуют и возвращают другое значение для любых элементов, которые этого не делают. Это полагается на то, что такая ключевая функция существует, что не всегда будет иметь место для произвольной функции сопоставления.