50

在 python 的库中，我们现在有两个 Python 实现的字典，它们dict是本机类型之上的子dict类。

Python 的拥护者一直倾向于尽可能defaultdict多地使用dict.setdefault。甚至医生也引用了This technique is simpler and faster than an equivalent technique using dict.setdefault():

以类似的方式，由于字典不保持顺序，因此在可能的替代用法中，优先使用OrderedDictover using ，然后对项目进行排序。dict

在上述两种情况下，代码肯定更干净，但代价是性能损失。

在回答和评论一个问题python unique list based on item时，我偶然发现了dict使用defaultdictand时对本机的性能损失OrderedDict。似乎数据的大小对于dict解决方案相对于其他解决方案的性能优势也不是不重要的。

我相信There should be one-- and preferably only one --obvious way to do it.，那么首选的方式是什么？

4

2 回答 2

68

没有一个单一的答案，也没有一个真实且唯一的听写。在众多变量中，它取决于：

  1. 数据集的大小；
  2. 唯一键的数量与数据映射集中重复键的数量；
  3. defaultdict 底层工厂的速度；
  4. OrderDict 的速度与稍后的订购步骤；
  5. Python 版本。

我不愿一概而论，但这里有一些概括：

  1. 这种说法This technique is simpler and faster than an equivalent technique using dict.setdefault()是完全错误的。这取决于数据；
  2. setdefault使用小数据集更快更简单；
  3. defaultdict对于具有更多同质键集的更大数据集（即，添加元素后字典有多短）更快；
  4. setdefault具有更多异构密钥集的优势；
  5. 这些结果对于 Python 3 和 Python 2 是不同的；
  6. OrderedDict在所有情况下都较慢，除了依赖于顺序的算法并且顺序不容易重构或排序；
  7. dict对于大多数操作，Python 3 通常更快；
  8. Python 3.6 的 dict 现在按插入顺序排序（降低 的有用性OrderedDict）。

唯一的事实：这取决于！这三种技术都很有用。

这是一些要显示的时序代码：

from __future__ import print_function
from collections import defaultdict
from collections import OrderedDict

try:
    t=unichr(100)
except NameError:
    unichr=chr

def f1(li):
    '''defaultdict'''
    d = defaultdict(list)
    for k, v in li:
        d[k].append(v)
    return d.items()

def f2(li):
    '''setdefault'''
    d={}
    for k, v in li:
        d.setdefault(k, []).append(v)
    return d.items()

def f3(li):
    '''OrderedDict'''
    d=OrderedDict()
    for k, v in li:
        d.setdefault(k, []).append(v)
    return d.items()      


if __name__ == '__main__':
    import timeit
    import sys
    print(sys.version)
    few=[('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
    fmt='{:>12}: {:10.2f} micro sec/call ({:,} elements, {:,} keys)'
    for tag, m, n in [('small',5,10000), ('medium',20,1000), ('bigger',1000,100), ('large',5000,10)]:
        for f in [f1,f2,f3]:
            s = few*m
            res=timeit.timeit("{}(s)".format(f.__name__), setup="from __main__ import {}, s".format(f.__name__), number=n)
            st=fmt.format(f.__doc__, res/n*1000000, len(s), len(f(s)))
            print(st)
            s = [(unichr(i%0x10000),i) for i in range(1,len(s)+1)]
            res=timeit.timeit("{}(s)".format(f.__name__), setup="from __main__ import {}, s".format(f.__name__), number=n)
            st=fmt.format(f.__doc__, res/n*1000000, len(s), len(f(s)))
            print(st)            
        print()

Python 2.7 结果：

2.7.5 (default, Aug 25 2013, 00:04:04) 
[GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.0.68)]
 defaultdict:      10.20 micro sec/call (25 elements, 3 keys)
 defaultdict:      21.08 micro sec/call (25 elements, 25 keys)
  setdefault:      13.41 micro sec/call (25 elements, 3 keys)
  setdefault:      18.24 micro sec/call (25 elements, 25 keys)
 OrderedDict:      49.47 micro sec/call (25 elements, 3 keys)
 OrderedDict:     102.16 micro sec/call (25 elements, 25 keys)

 defaultdict:      28.28 micro sec/call (100 elements, 3 keys)
 defaultdict:      79.78 micro sec/call (100 elements, 100 keys)
  setdefault:      45.68 micro sec/call (100 elements, 3 keys)
  setdefault:      68.66 micro sec/call (100 elements, 100 keys)
 OrderedDict:     117.78 micro sec/call (100 elements, 3 keys)
 OrderedDict:     343.17 micro sec/call (100 elements, 100 keys)

 defaultdict:    1123.60 micro sec/call (5,000 elements, 3 keys)
 defaultdict:    4250.44 micro sec/call (5,000 elements, 5,000 keys)
  setdefault:    2089.86 micro sec/call (5,000 elements, 3 keys)
  setdefault:    3803.03 micro sec/call (5,000 elements, 5,000 keys)
 OrderedDict:    4399.16 micro sec/call (5,000 elements, 3 keys)
 OrderedDict:   16279.14 micro sec/call (5,000 elements, 5,000 keys)

 defaultdict:    5609.39 micro sec/call (25,000 elements, 3 keys)
 defaultdict:   25351.60 micro sec/call (25,000 elements, 25,000 keys)
  setdefault:   10267.00 micro sec/call (25,000 elements, 3 keys)
  setdefault:   24091.51 micro sec/call (25,000 elements, 25,000 keys)
 OrderedDict:   22091.98 micro sec/call (25,000 elements, 3 keys)
 OrderedDict:   94028.00 micro sec/call (25,000 elements, 25,000 keys)

Python 3.3 结果：

3.3.2 (default, May 21 2013, 11:50:47) 
[GCC 4.2.1 Compatible Apple Clang 4.1 ((tags/Apple/clang-421.11.66))]
 defaultdict:       8.58 micro sec/call (25 elements, 3 keys)
 defaultdict:      21.18 micro sec/call (25 elements, 25 keys)
  setdefault:      10.42 micro sec/call (25 elements, 3 keys)
  setdefault:      14.58 micro sec/call (25 elements, 25 keys)
 OrderedDict:      45.43 micro sec/call (25 elements, 3 keys)
 OrderedDict:      92.69 micro sec/call (25 elements, 25 keys)

 defaultdict:      20.47 micro sec/call (100 elements, 3 keys)
 defaultdict:      77.48 micro sec/call (100 elements, 100 keys)
  setdefault:      34.22 micro sec/call (100 elements, 3 keys)
  setdefault:      54.86 micro sec/call (100 elements, 100 keys)
 OrderedDict:     107.37 micro sec/call (100 elements, 3 keys)
 OrderedDict:     318.98 micro sec/call (100 elements, 100 keys)

 defaultdict:     714.70 micro sec/call (5,000 elements, 3 keys)
 defaultdict:    3892.92 micro sec/call (5,000 elements, 5,000 keys)
  setdefault:    1502.91 micro sec/call (5,000 elements, 3 keys)
  setdefault:    2888.08 micro sec/call (5,000 elements, 5,000 keys)
 OrderedDict:    3912.95 micro sec/call (5,000 elements, 3 keys)
 OrderedDict:   14863.02 micro sec/call (5,000 elements, 5,000 keys)

 defaultdict:    3649.02 micro sec/call (25,000 elements, 3 keys)
 defaultdict:   22313.17 micro sec/call (25,000 elements, 25,000 keys)
  setdefault:    7447.28 micro sec/call (25,000 elements, 3 keys)
  setdefault:   18426.88 micro sec/call (25,000 elements, 25,000 keys)
 OrderedDict:   19202.17 micro sec/call (25,000 elements, 3 keys)
 OrderedDict:   85946.45 micro sec/call (25,000 elements, 25,000 keys)
于 2013-10-28T19:05:32.817 回答
10

我觉得你的假设 -只有一种更可取的方式- 不成立。我看到至少有两种不同要求的案例：

在维护密集型代码（例如，不断发展的实用程序类的选项解析器）中，我总是会使用更简洁的代码，以便我和其他人可以更轻松地实现新功能。性能并不重要，因为只处理少量（例如用户设置的字典）。

而在

在数据处理任务中实现性能关键算法，我不介意编写更详细的代码以更快地执行。如果算法不太可能改变，那么可读性差的代码就不会成为问题。

于 2013-10-28T08:26:04.513 回答