OrderedDict vs defaultdict vs dict

Question

在Python的库中，我们现在有两个Python字典实现，这些子类是 dict 超出本地 dict 类型。

Python的倡导者一直倾向于使用defaultdict而不是尽可能使用 dict.setdefault 。即使文档引用了 This technique is simpler and faster than an equivalent technique using dict.setdefault()： 同样，由于字典不维护顺序，因此在可以选择的情况下，使用OrderedDict 而不是使用 dict 后跟排序项目更受欢迎。

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

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

我相信应该有一种--最好只有一种--明显的方法来做到这一点。，那么哪种是首选方式？

- Abhijit

---

defaultdict 并不一定比普通的 dict 更慢。那里的计时方式有缺陷，因为计时包括了创建对象的时间。除此之外，还有不同类型的性能，其中易于维护就是其中之一。你没有指定任何衡量性能的标准。只需使用 适合工作的正确工具。 - Martijn Pieters

再次强调：请根据您自己的用例进行时间测试。您引用的时间是针对一个小数据集并包括字典对象的创建；因为字典文字（{}）比defaultdict（...）工厂调用（全局查找，堆栈推送，调用）快得多，这会导致在小数据集上结果失衡。认为defaultdict更慢是错误的。 - Martijn Pieters

虽然我同意使用 defaultdict 比调用 dict.setdefault 更加方便，但为什么 OrderedDict 在可能的情况下被认为是比 dict 更优选的呢？我认为我从来没有关心过字典中键的插入顺序，这个特性比仅仅提供新键的默认值更加具体。 - chepner

Answer 1

没有一个单一的答案和唯一的字典是正确的。在许多变量中，这取决于：

1. 数据集的大小；
2. 数据映射集中唯一键的数量与重复键的数量；
3. 默认字典底层工厂的速度；
4. OrderDict 的速度与某些后续排序步骤；
5. Python 版本。

我不想做出概括，但以下是一些普遍性：

1. 声明“这种技术比使用 dict.setdefault() 相当技术更简单和更快”是错误的。它取决于数据；
2. 对于小数据集，setdefault 更快、更简单；
3. 对于具有更同质键集（即添加元素后 dict 有多短）的大型数据集，defaultdict 更快；
4. 对于更异构键集，setdefault 有优势；
5. Python 3 和 Python 2 的结果不同；
6. OrderedDict 在除依赖于顺序且难以重构或排序的算法之外的所有情况下都较慢；
7. Python 3 对于大多数 dict 操作通常更快；
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)

- dawg

---

“defaultdict” 对于更同质的键集速度更快。这里的“同质”是指类型的同质性吗？ - tel

“同质性”是指在添加一些可能有重复元素的元素后，有多少个键。如果您执行dict(zip('123','abc'))，则从3次添加中得到3个键-0同质性；如果您执行dict(zip('111','abc'))，则从三次添加中得到一个带有1个键的字典-非常同质化。 - dawg

@dawg 我猜测，如果你在setdefault中使用list()而不是[]，那么在多键版本中差异实际上会消失。如果您无法在.setdefault中使用文字，例如使用set对象，则可能会有所帮助。 - juanpa.arrivillaga

@juanpa.arrivillaga 我已将其添加到基准测试中，是的，它们更接近了一些，但并没有显著改变... - dawg

Answer 2

我认为你的假设 - 只有一种可取的方式 - 是不成立的。我看到至少两种有不同要求的情况：

在 维护密集型 代码中（例如一个不断演进的实用程序类的选项解析器），我总是会选择 更干净的代码，以便其他人和我可以更轻松地实现新功能。性能并不关键，因为只处理小量数据（例如用户设置的字典）。

而在

数据处理任务中实现 性能至上 的算法时，我不介意写出稍微 更繁琐的代码来加速执行。如果算法不太可能发生变化，那么稍微不太易读的代码也不会成为问题。

- ojdo

---

在数据处理任务中实现性能关键算法时，我不介意编写更冗长的代码以获得更快的执行速度。在这种情况下，为什么不使用本地代码编写实现呢？“只有一种可取的方式”……这不是我的假设，而是Tim Peters的指导方针。 - Abhijit

对于给定的、完全指定的用例（以及完全知道的边界条件），可能有可能只选定一种首选方式。但我认为这种情况很少见。大多数时候，必须进行某些权衡（性能、可读性、通用性等），并且首选方式基本上是选择最少感知到不利因素的选项的主观选择。 - ojdo

有些只是投资回报率问题。用Cython编写或使用PyPy编写的复杂性比股票Python更高，而编译C库则更加复杂。您可以决定部分前进（更快的本地Python解决方案）的权衡是值得的，而更进一步（本地库）的权衡则不值得。 - Corley Brigman