python - 预排序提高了 itertools.combinations 的性能？

Question

我目前正在处理大数据，工作的一个重要步骤是获取数千个字符串的所有排序组合。

在 python 3.4 中，我尝试了三种方法来执行此操作。

首先，将数据伪造为字符串列表，有或没有 GO 术语:

# -*- coding: utf-8 -*-
import random as rd

# With GO term
# data = ["GO:" + str(i) for i in range(0, 10000)]
# Xor, without GO term
data = [str(i) for i in range(0, 10000)]

rd.shuffle(data)
print("shuffle done")

GO 术语只是添加到所有数据字符串开头的常量字符串。有和没有 GO 项的结果如下。

现在，执行基准测试:

from itertools import combinations, product

def test1(): # use condition
    g = ((i,j) if (i < j) else (j,i) for i, j in combinations(data, 2))
    print(len([(i, j) for i, j in g]))


def test2(): # use filter
    g = ((i, j) for i,j in product(data, data) if (i < j))
    print(len([(i, j) for i, j in g]))


def test3(): # sort before combine
    g = ((i,j) for i, j in combinations(sorted(data), 2))
    print(len([(i, j) for i, j in g]))


import timeit

print(timeit.timeit(stmt=test1, number=3))
print(timeit.timeit(stmt=test2, number=3))
print(timeit.timeit(stmt=test3, number=3))

使用 GO 术语的输出:

49995000
49995000
49995000
23.490827083587646
49995000
49995000
49995000
31.04393219947815
49995000
49995000
49995000
16.878661155700684

没有 GO 术语的输出:

49995000
49995000
49995000
22.99237084388733
49995000
49995000
49995000
29.025460958480835
49995000
49995000
49995000
16.596422910690308

每次调用打印的 49995000 向我们证明所有方法都产生相同数量的数据。现在的问题:

1. 为什么第一种方法比第二种方法快？使用过滤器是我用来过滤数据的主要方式。到目前为止，我认为过滤器形式已经过大量优化。
2. 为什么第三种方法似乎更好？排序复杂度为 O(N*log(N))，在大型列表中似乎代价高昂？
3. 为什么 GO 术语对第一种和第二种方法的影响大于对第三种方法的影响？

我的第一个猜测是排序+组合产生的数据比较要少得多，而其他两种方法对每对字符串进行比较，但是，由于排序听起来像是一项繁重的操作，我对此并不完全确定.

Answer 1

我很确定造成您所观察到的性能差异的重要因素是检查 if (i < j)。 49995000 次 vs 对 10000 个元素的列表进行排序，而不是假定的已排序 vs 未排序的可迭代对象。

combinations在这两种情况下应该做相同数量的工作，因为它们产生相同数量的元素并且不对元素进行排序并按字典顺序返回它们。

要正确测试排序是否有所不同:

1. 对同一组数据执行相同的条件检查，但已排序和未排序:

   sorted_data = sorted(data)
   
   def test1():
       g = ((i,j) if (i < j) else (j,i) for i, j in combinations(sorted_data, 2))
       return len([(i, j) for i, j in g])
   
   def test2():
       g = ((i,j) if (i < j) else (j,i) for i, j in combinations(data, 2))
       return len([(i, j) for i, j in g])
   
   %timeit test1()
   1 loops, best of 3: 23.5 s per loop
   
   %timeit test2()
   1 loops, best of 3: 24.6 s per loop
   

2. 在没有条件的情况下执行测试:

   def test3():
       g = ((i,j) for i, j in combinations(sorted_data, 2))
       return len([(i, j) for i, j in g])
   
   def test4():
       g = ((i,j) for i, j in combinations(data, 2))
       return len([(i, j) for i, j in g])
   
   %timeit test3()
   1 loops, best of 3: 20.7 s per loop
   
   %timeit test4()
   1 loops, best of 3: 21.3 s per loop
   

Why is the first method so quick, compared to the second ? Use of filter is the main way i use for filtering data. Until now, i assume that the filter form was heavily optimized.

使用组合会产生较少的条件检查元素。 10000C2 = 49995000对于组合与 10000**2 = 100000000用于产品。

Why the GO term impact more the first and the second method than the third one ?

第一种和第二种方法受比较49995000次和100000000次附加字符的影响。第三个仅受对 10000 个项目进行排序所需的比较的影响。

---

经过一些摆弄后，似乎排序可能会有所不同，但不会像使用条件一样大。不知道是什么原因造成的。

from itertools import combinations
import random as rd

data = ["{0:04d}".format(i) for i in range(0, 10000)] # Normalize str length
rd.shuffle(data)

sorted_data = sorted(data)
reversed_sorted_data = sorted_data[::-1]

def test1():
    g = list((i,j) if (i < j) else (j,i) for i, j in combinations(data, 2))
    print('unsorted with conditional: ', len(g))

%timeit test1()
# unsorted with conditional:  49995000
# unsorted with conditional:  49995000
# unsorted with conditional:  49995000
# unsorted with conditional:  49995000
# 1 loops, best of 3: 20.7 s per loop

def test2():
    g = list((i,j) if (i < j) else (j,i) for i, j in combinations(sorted_data, 2))
    print('sorted with conditional: ', len(g))

%timeit test2()
# sorted with conditional:  49995000
# sorted with conditional:  49995000
# sorted with conditional:  49995000
# sorted with conditional:  49995000
# 1 loops, best of 3: 19.6 s per loop

def test3():
    g = list((i,j) for i, j in combinations(data, 2))
    print('unsorted without conditional: ', len(g))
    
%timeit test3()
# unsorted without conditional:  49995000
# unsorted without conditional:  49995000
# unsorted without conditional:  49995000
# unsorted without conditional:  49995000
# 1 loops, best of 3: 15.7 s per loop

def test4():
    g = list((i,j) for i, j in combinations(sorted_data, 2))
    print('sorted without conditional: ', len(g))

%timeit test4()
# sorted without conditional:  49995000
# sorted without conditional:  49995000
# sorted without conditional:  49995000
# sorted without conditional:  49995000
# 1 loops, best of 3: 15.3 s per loop

def test5():
    g = list((i,j) for i, j in combinations(reversed_sorted_data, 2))
    print('reverse sorted without conditional: ', len(g))
    
%timeit test5()
# reverse sorted without conditional:  49995000
# reverse sorted without conditional:  49995000
# reverse sorted without conditional:  49995000
# reverse sorted without conditional:  49995000
# 1 loops, best of 3: 15 s per loop