Python - 比嵌套for循环更快的东西

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更快的东西.

代码正在做的是获取字典列表并对每个字典的值与每个其他字典运行奇特的模糊匹配函数.所以它并不像将所有词典与其他词典进行比较那么简单.我想要一种在每个字典上运行一个函数的方法,也许2个for循环是正确的方法吗？任何的意见都将会有帮助!

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允许这样的分组才有可能.哪种情况适用于您的情况,但如果它更复杂则可能不是.