Python比2个嵌套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变得非常大（比如数百万），我觉得肯定有比2for循环更快的东西。在

代码所做的是获取一个字典列表，并对每个字典的值运行一个奇特的模糊匹配函数。所以这并不像把所有的字典和其他的字典比较那么简单。我想在每个字典上运行一个函数，也许2个for循环是正确的方法吗？任何建议都会有帮助的！在

Answer 1

您可以使用^{}，它本质上是同一个双循环，但它的迭代速度更快，因为它是用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'])

哪个打印：

^{pr2}$

---

但是，如果您的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'])

显然，如果您更改匹配函数，您将需要更改键函数，以便它为匹配的任何元素返回相同的值，并为不匹配的任何元素返回不同的值。这取决于这样一个事实：这样的键函数存在，而对于任意匹配函数，情况并非总是如此。在