python - 处理列表和字典的惯用方式

Question

最近我发现了处理列表、字典、集合等的“Python 方式”。为此，我修改了我的函数以计算第一个 N 个素数，让我们调用它是“纯字典”版本:

def findprimeuptoG(x):
    n_primes = {}

    for i in range(2, x):

        if i not in n_primes.values():
            n_primes[i]=i

        for k, v in n_primes.items():
            if i > v:
                n_primes[k] += k

    return sorted(n_primes)

这个函数的工作原理如下:

1. 在字典中维护素数列表和这些相同素数的整数倍列表

2. 这些倍数应该大于或等于某个整数 i

3. 如果一个数不在现有素数的整数倍列表中，那么它一定是一个素数并被添加到素数列表中

4. 从 2(最小素数)开始增加 i，直到 x

5. 返回素数列表

我已经使用列表、集合多次重写了这个函数，但这个版本似乎是最地道的版本。它很短，易于阅读。

如果有人愿意让我知道是否可以将其写得更清楚，请发表评论，因为我很乐意阅读它。

现在的问题是:这个函数的第一个版本不是那么干净，更像 C:

def findprimeupto(x):
    primes = []
    n_primes = []

    for i in range(2, x):

        if i not in n_primes:
            primes.append(i)
            n_primes.append(i)

        for j in range(len(primes)):
            if i > n_primes[j]:
                n_primes[j] += primes[j]

    return primes

但是当我用 pypy 编译器运行它时，第一个版本绝对是最快的:

python 3:

Primes up to: 100000

Algo: Clean version       , primes: 9592, time: 102.74523687362671

Algo: Dict, Set           , primes: 9592, time: 58.230621337890625

Algo: **FirstVersion**        , primes: 9592, time: 59.945680379867554

Algo: List of List[1]        , primes: 9592, time: 71.41077852249146

Algo: List of MutableNum  , primes: 9592, time: 292.3777365684509

Algo: **Pure Dict**           , primes: 9592, time: 56.381882667541504

pypy(版本 2.3.1):

Primes up to: 100000

Algo: Clean version       , primes: 9592, time: 29.3849189281

Algo: Dict, Set           , primes: 9592, time: 85.8557658195

Algo: **FirstVersion**        , primes: 9592, time: 1.11557507515

Algo: List of List        , primes: 9592, time: 42.2394959927

Algo: List of MutableNum  , primes: 9592, time: 38.764893055

Algo: **Pure Dict**           , primes: 9592, time: 110.416568995

我知道“Pure Dict”版本的性能提升是因为我没有在循环中使用迭代器，但“FirstVersion”的加速仍然是惊人的。

由于我们的大部分代码可能最终会在产品中编译，我们是否应该以更像 C 的方式而不是惯用的 Python 编写代码？

编辑:

为了消除我是否应该使用列表而不是字典的困惑，我提交了这个函数的另一个版本，我称之为“干净版本”。这个版本不直接访问列表的第 N 个元素，而是以我认为最 Pythonistic 的方式遍历列表(顺便说一句，这个版本与相同代码的 lisp 版本最相似:)

def findprimeuptoB(x):
    primes = []
    n_primes = []

    for i in range(2, x):

        if not (i in n_primes):
            primes.append(i)
            n_primes.append(i)

        new_n_primes = []

        for prime, n_prime in zip(primes, n_primes):
            if i > n_prime:
                new_n_primes.append(prime + n_prime)
            else:
                new_n_primes.append(n_prime)

        n_primes = new_n_primes

    return primes

Answer 1

是的，如果您关心性能，“第一版”是最佳选择。您可以使用 cProfile 查看发生了什么。

作为引用，在 pypy 2.5.0 上，使用“第一版”运行 python -m cProfile -s cumulative x.py 给我:

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000    0.727    0.727 x.py:1(<module>)
     1    0.724    0.724    0.727    0.727 x.py:29(findprimeupto)
 99999    0.002    0.000    0.002    0.000 {len}
 99999    0.001    0.000    0.001    0.000 {range}
 19184    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

OTOH，使用“Pure Dict”，我得到:

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000   16.864   16.864 x.py:1(<module>)
     1    1.441    1.441   16.864   16.864 x.py:1(findprimeuptoG)
 99998   12.376    0.000   12.376    0.000 {method 'items' of 'dict' objects}
 99998    3.047    0.000    3.047    0.000 {method 'values' of 'dict' objects}
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     1    0.000    0.000    0.000    0.000 {len}
     1    0.000    0.000    0.000    0.000 {range}

这表明大部分时间都浪费在了创建临时列表 n_primes.items() 和 n_primes.values() 上。

现在，有一个简单的解决方法:用它们各自的迭代器版本 .iteritems() 替换 .items() 和 .values() 和 .itervalues()。然而，结果仍然比列表版本慢得多，因为字典的结构比列表更复杂，低级字典操作因此比等效的列表操作慢得多:

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000    3.155    3.155 x.py:1(<module>)
     1    3.147    3.147    3.155    3.155 x.py:15(findprimeuptoH)
 99998    0.006    0.000    0.006    0.000 {method 'itervalues' of 'dict' objects}
 99998    0.002    0.000    0.002    0.000 {method 'iteritems' of 'dict' objects}
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
     1    0.000    0.000    0.000    0.000 {len}
     1    0.000    0.000    0.000    0.000 {range}

最后，'Clean Version' 显然相当糟糕，因为它在每次迭代时都会创建一个新的 n_primes 列表。事实上，我将它计时为 21.795 秒。

结论:创建新容器(列表、字典等)非常缓慢，请尽可能避免使用它。此外，字典比列表慢。在这个问题中，你实际上不需要字典，所以你应该使用列表。