预排序改进itertools.组合表演？

Question

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

在Python3.4中，我尝试了三种方法来执行此操作。在

首先，将数据伪造为一个字符串列表，有或没有GO-term：

# -*- 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项的结果如下。在

现在，执行基准测试：

^{pr2}$

带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. 为什么围棋术语对第一种和第二种方法的影响大于第三种方法？在

我的第一个猜测是sorting+组合产生的数据比较要少得多，而另外两个方法对每对字符串执行比较，但是，由于排序听起来像是一个繁重的操作，我不能完全确定这一点。在

Answer 1

我非常肯定，您所观察到的性能差异的重要原因是检查if (i < j)49995000次与排序10000个元素的列表相比，而不是假设的排序与不排序的iterable。在

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表示组合，而{}表示产品。在

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 ；

Answer 2

1. 真的不奇怪，看看combinations如何只创建i<j为真的组合，而{a2}创建所有组合，包括{}不正确的组合-if (i < j) else (j,i)在{}中是多余的。省略此签入test1将大大减少执行时间，如下所示。在

用cd4{1}检查：

shuffle done
49995000
49995000
49995000
31.66194307899991
49995000
49995000
49995000
37.66488860800018
49995000
49995000
49995000
22.706632076000005

没有i<j签入test1：

^{pr2}$