优化盈亏平衡点:在集合上多次迭代或首先转换为列表？

Question

这是我一直想知道的事情.我将提出Python的问题,但我也欢迎解决Java和C++标准库的问题.

假设您有一个名为"my_list"的Python列表,并且您希望迭代其独特元素.有两种自然方法:

#iterate over set
for x in set(my_list):
    do_something(x)

要么

#list to set to list
for x in list(set(my_list)):
    do_something(x)

紧张是在列表上迭代比在集合上迭代更快,但是将集合转换为列表需要时间.我的猜测是,这个问题的答案取决于许多因素,例如:

• 我们需要迭代多少次？
• 原始清单有多大？
• 我们应该在原始列表中重复多少次？

所以我想我正在寻找形式的经验法则"如果列表有x个元素,每个元素重复不超过y次,你只需要迭代z次,那么你应该遍历集合;否则你应该把它转换成一个清单."

Answer 1

我正在寻找经验法则......

经验法则

这是编写最佳Python的最佳经验法则:使用尽可能少的中间步骤,避免实现不必要的数据结构.

适用于这个问题:集合是可迭代的.不要将它们转换为另一个数据结构,只是为了迭代它们.信任Python以了解迭代集合的最快方法.如果将它们转换为列表更快,Python就会这样做.

关于优化:

不要通过增加程序的复杂性来尝试过早优化.如果您的程序耗时太长,请对其进行分析,然后优化瓶颈.如果您正在使用Python,那么您可能更关心开发时间而不是程序运行所需的时间.

示范

在Python 2.7中:

import collections
import timeit
blackhole = collections.deque(maxlen=0).extend
s = set(xrange(10000))

我们看到更大n,更简单更好:

>>> timeit.timeit(lambda: blackhole(s))
108.87403416633606
>>> timeit.timeit(lambda: blackhole(list(s)))
189.0135440826416

对于较小n的同样的关系:

>>> s = set(xrange(10))
>>> timeit.timeit(lambda: blackhole(s))
0.2969839572906494
>>> timeit.timeit(lambda: blackhole(list(s)))
0.630713939666748

是的,列表比集合迭代更快(在您自己的Python解释器上尝试):

l = list(s)
timeit.repeat(lambda: blackhole(l))

但这并不意味着您应该将集合转换为仅用于迭代的列表.

盈亏平衡分析

好的,所以你已经分析了你的代码,发现你正在迭代一组(我认为这个集是静态的,否则我们正在做的是非常有问题的).我希望您熟悉set方法,而不是复制该功能.(我也认为你应该考虑将frozensets与元组链接起来,因为使用一个列表(可变)来替换一个规范集(也是可变的)似乎可能容易出错.)所以有了这个警告,让我们做一个分析.

可能是通过对复杂性进行投资并从更多代码行中承担更大的错误风险,您可以获得良好的回报.这一分析将证明这一点的盈亏平衡点.我不知道你需要为更大的风险和开发时间付出更多的表现,但这会告诉你在什么时候你可以开始支付那些:

import collections
import timeit
import pandas as pd

BLACKHOLE = collections.deque(maxlen=0).extend

SET = set(range(1000000))

def iterate(n, iterable):
    for _ in range(n):
        BLACKHOLE(iterable)

def list_iterate(n, iterable):
    l = list(iterable)
    for _ in range(n):
        BLACKHOLE(l)

columns = ('ConvertList', 'n', 'seconds')

def main():
    results = {c: [] for c in columns}

    for n in range(21):
        for fn in (iterate, list_iterate):
            time = min(timeit.repeat((lambda: fn(n, SET)), number=10))
            results['ConvertList'].append(fn.__name__)
            results['n'].append(n)
            results['seconds'].append(time)

    df = pd.DataFrame(results)
    df2 = df.pivot('n', 'ConvertList')
    df2.plot()
    import pylab
    pylab.show()

看起来你的盈亏平衡点是5次完整的迭代.平均为5或更少,这样做是不可能的.只有5个或更多才开始补偿额外的开发时间,复杂性(增加维护成本)以及更多代码行的风险.

我认为你必须做很多事情,值得为你的项目增加复杂性和代码行.

这些结果是使用Anaconda的Python 2.7从Ubuntu 14.04终端创建的.您可能会因不同的实现和版本而获得不同的结果.

关注

我关心的是集合是可变的,列表是可变的.一个集合将阻止您在迭代它时修改它,但是从该集合创建的列表将不会:

>>> s = set('abc')
>>> for e in s:
...     s.add(e + e.upper())
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: Set changed size during iteration

如果在迭代衍生列表时修改集合,则不会出现错误,告诉您这样做.

>>> for e in list(s):
...     s.add(e + e.upper())

这就是为什么我还建议使用frozensets和元组代替.它将内置防范语义错误的数据更改.

>>> s = frozenset('abc')
>>> t_s = tuple(s)
>>> for e in t_s:
...     s.add(e + e.upper())
... 
Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
AttributeError: 'frozenset' object has no attribute 'add'

最后,您必须相信自己才能使算法正确.我经常告诉我,当我向新用户提醒这些事情时,我给了他很好的建议.他们知道这是一个很好的建议,因为他们最初没有听,并发现它造成了不必要的复杂性,并发症和由此产生的问题.但是,如果你没有做对,那么你也只能责怪自己的逻辑正确性.最大限度地减少可能出错的事情是一种通常值得性能权衡的好处.而且,如果在处理这个项目时性能(而不是正确性或开发速度)是主要关注点,那么你就不会使用Python.