获得范围对的最快方法（n）？

Question

假设您想要处理 0 到 n-1 的所有数字对，例如n = 4这六对：

\n

[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]\n

\n

创建这些对的三种方法：

\n

list(combinations(range(n), 2))\n\n[(i, j) for i, j in combinations(range(n), 2)]\n\n[(i, j) for i in range(n) for j in range(i+1, n)]\n

\n

基准测试结果n = 1000：

\n

44.1 ms \xc2\xb1 0.2 ms  f_combinations_pure\n57.7 ms \xc2\xb1 0.3 ms  f_combinations\n66.6 ms \xc2\xb1 0.1 ms  f_ranges\n

\n

请注意，我对仅存储对并不真正感兴趣(i, j)。这只是i和的一个最小示例用法j，以便我们可以比较不同的方法而无需太多开销。实际上，您想要使用和做一些事情，例如获取子字符串（评论启发了这个问题）。所以ij[my_string[i:j] for ...]list(combinations(...))在这里并不算数，我展示它只是为了清楚地表明这一点（尽管我仍然喜欢看到它有多快）。

\n

问题1：为什么f_ranges比 慢f_combinations？它总共for i in只运行一次，因此与运行次数n相比，它是微不足道的。并且只分配一个数字，而构建并分配一对数字，因此后者应该更慢。为什么速度更快for j inn*(n-1)/2for j in range(...)for i, j in combinations(...)？

\n

问题 2：您能想到的最快方法是什么？为了公平比较，它应该是一个列表理解[(i, j) for ...]生成相同对列表的列表理解。

\n

（因为我自己包含了一个答案（这是鼓励），所以我在那里包含了基准代码。）

\n

Answer 1

关于问题1：为什么range比combinations？

\n

虽然for j in range(...)确实具有仅分配一个数字的优点，但它也有缺点是一遍又一遍地创建它们。在Python中，数字是对象，它们的创建（和删除）需要一点时间。

\n

combinations(...)另一方面，首先创建并仅存储数字对象一次，然后成对地重复使用它们。您可能会想“等等，它可以重用数字，但它会将这些对生成为tuple对象，因此每次迭代也会创建一个对象！” 。嗯...它有一个优化。tuple它实际上一遍又一遍地重复使用同一个对象，并用不同的数字填充它。“什么？不可能！元组是不可变的！” 嗯...表面上它们是不可变的，是的。但是，如果combinations迭代器发现没有其他对其结果元组的引用，那么它会“作弊”并无论如何修改它。在 C 代码级别，它可以做到这一点。如果没有其他东西与它相关，那么也没有什么坏处。请注意，for i, j in ...解压元组并且不保留对其的引用。如果您改为使用for pair in ...，则pair是对其的引用，并且不会应用优化，并且实际上result每次都会创建一个新元组。如果您有兴趣，请参阅combinations_next的源代码。

\n

关于问题2：最快的方法是什么？

\n

我发现了四种更快的方法：

\n

44.1 ms \xc2\xb1 0.2 ms  f_combinations_pure\n51.7 ms \xc2\xb1 0.1 ms  f_list\n52.7 ms \xc2\xb1 0.2 ms  f_tee\n53.6 ms \xc2\xb1 0.1 ms  f_copy_iterator\n54.6 ms \xc2\xb1 0.1 ms  f_tuples\n57.7 ms \xc2\xb1 0.3 ms  f_combinations\n66.6 ms \xc2\xb1 0.1 ms  f_ranges\n

\n

所有四种更快的方法都避免了导致解决range方案变慢的原因：它们不是创建（和删除） \xce\x98(n\xc2\xb2)int对象，而是一遍又一遍地重复使用相同的对象。

\n

f_tuples将它们放入元组并迭代切片：

\n

def f_tuples(n):\n    nums = tuple(range(n))\n    return [(i, j)\n            for i in nums\n            for j in nums[i+1:]]\n

\n

f_list将它们放入列表中，然后在每个j循环之前删除第一个数字：

\n

def f_list(n):\n    js = list(range(n))\n    return [(i, j)\n            for i in range(n)\n            if [js.pop(0)]\n            for j in js]\n

\n

f_copy_iterator将它们放入一个元组中，然后使用迭代器 fori和该迭代器的副本for j（这是从 后一个位置开始的迭代器i）：

\n

def f_copy_iterator(n):\n    nums = iter(tuple(range(n)))\n    return [(i, j)\n            for i in nums\n            for j in copy(nums)]\n

\n

f_tee使用itertools.tee获得与 类似的效果copy。它JS是值的主要迭代器j，在每个j循环之前，它会丢弃第一个值，然后JS获取剩余值的第二个迭代器：

\n

def f_tee(n):\n    return [(i, j)\n            for JS in [iter(range(n))]\n            for i in range(n)\n            for _, (JS, js) in [(next(JS), tee(JS))]\n            for j in js]\n

\n

额外问题：像那些更快的方法那样进行优化是否值得？

\n

嗯，可能不是。也许你最好只使用for i, j in combinations(...). 更快的方法并不快得多，而且有些更复杂。另外，实际上，您实际上会使用i和做一些事情j（例如获取子字符串），因此相对较小的速度优势变得相对较小。

\n

但我希望你至少觉得这很有趣，也许有一天你会学到一些有用的新东西。

\n

完整的基准代码

\n

在线尝试一下！

\n

def f_combinations_pure(n):\n    return list(combinations(range(n), 2))\n\n\ndef f_combinations(n):\n    return [(i, j) for i, j in combinations(range(n), 2)]\n\n\ndef f_ranges(n):\n    return [(i, j) for i in range(n) for j in range(i+1, n)]\n\n\ndef f_tuples(n):\n    nums = tuple(range(n))\n    return [(i, j) for i in nums for j in nums[i+1:]]\n\n\ndef f_list(n):\n    js = list(range(n))\n    return [(i, j) for i in range(n) if [js.pop(0)] for j in js]\n\n\ndef f_copy_iterator(n):\n    nums = iter(tuple(range(n)))\n    return [(i, j) for i in nums for j in copy(nums)]\n\n\ndef f_tee(n):\n    return [(i, j)\n            for JS in [iter(range(n))]\n            for i in range(n)\n            for _, (JS, js) in [(next(JS), tee(JS))]\n            for j in js]\n\n\nfs = [\n    f_combinations_pure,\n    f_combinations,\n    f_ranges,\n    f_tuples,\n    f_list,\n    f_copy_iterator,\n    f_tee\n]\n\nfrom timeit import default_timer as time\nfrom itertools import combinations, tee\nfrom statistics import mean, stdev\nfrom random import shuffle\nfrom copy import copy\n\n# Correctness\nexpect = fs[0](1000)\nfor f in fs:\n    result = f(1000)\n    assert result == expect\n\n# Prepare for timing\ntimes = {f: [] for f in fs}\ndef stats(f):\n    ts = [t * 1e3 for t in sorted(times[f])[:5]]\n    return f\'{mean(ts):4.1f} ms \xc2\xb1 {stdev(ts):3.1f} ms \'\n\n# Timing\nfor i in range(25):\n    shuffle(fs)\n    for f in fs:\n        start = time()\n        result = f(1000)\n        end = time()\n        times[f].append(end - start)\n        del result\n\n# Results\nfor f in sorted(fs, key=stats):\n    print(stats(f), f.__name__)\n

\n