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

Question

最近我发现 "the Python way" 处理列表、dict、集合等。为此我修改了我的函数以计算第一个 N 个素数，我们称它为'Pure Dict' 版本：

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)

该函数的工作原理如下：

在字典中维护一个素数列表和这些相同素数的整数倍列表
这些倍数应该大于或等于某个整数i
如果一个数不在现有素数的整数倍列表中，那么它一定是一个素数并被添加到素数列表中
从 2（最小素数）开始增加 i，直到 x
return 素数列表

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

如果有人好心让我知道这是否可以写得更清楚，请发表评论，因为我很想阅读它。

现在的问题是：这个函数的第一个版本不太干净，更像 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 编译器时，第一个版本绝对是最快的：

python3:

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？

编辑：

为了消除我是否应该使用列表而不是 dict 的困惑，我提交了这个函数的另一个版本，我称之为 'Clean version'。这个版本不直接访问列表的第 N 个元素，而是以我认为最 Python 主义的方式遍历列表（顺便说一句，这个版本与相同代码的 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

是的，如果您关心性能，'First Version' 是最佳选择。您可以使用 cProfile 查看发生了什么。

作为参考，在 pypy 2.5.0 上，运行 python -m cProfile -s cumulative x.py 和 'First Version' 给我：

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().

上

现在，有一个简单的解决方法：将 .items() 和 .values() 替换为它们各自的迭代器版本 .iteritems() 和 .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 秒。

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

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

Idiomatic way to process lists and dicts

python

dictionary

pypy

list

python-3.4