从大词典中弹出N个项目的最快方法

Question

我有一个大字典src（最多1M个项目），我想取N个（典型值为N = 10K-20K）项目，将它们存储在一个新的字典中dst，仅将其余项目保留在中src。拿走N个项目都没关系。我正在寻找在Python 3.6或3.7上最快的方法。

到目前为止，我发现的最快方法是：

src = {i: i ** 3 for i in range(1000000)}

# Taking items 1 by 1 (~0.0059s)
dst = {}
while len(dst) < 20000:
    item = src.popitem()
    dst[item[0]] = item[1]

有更好的吗？即使是边际收益也将是好的。

Answer 1

一个简单的内部理解dict会做：

dict(src.popitem() for _ in range(20000))

这里有计时测试

setup = """
src = {i: i ** 3 for i in range(1000000)}

def method_1(d):
  dst = {}
  while len(dst) < 20000:
      item = d.popitem()
      dst[item[0]] = item[1]
  return dst

def method_2(d):
  return dict(d.popitem() for _ in range(20000))
"""
import timeit
print("Method 1: ", timeit.timeit('method_1(src)', setup=setup, number=1))

print("Method 2: ", timeit.timeit('method_2(src)', setup=setup, number=1))

结果：

Method 1:  0.007701821999944514
Method 2:  0.004668198998842854

Answer 2

这还是有点快：

from itertools import islice
def method_4(d):
    result = dict(islice(d.items(), 20000))
    for k in result: del d[k]
    return result

与其他版本相比，使用Netwave的测试用例：

Method 1:  0.004459443036466837  # original
Method 2:  0.0034434819826856256 # Netwave
Method 3:  0.002602717955596745  # chepner
Method 4:  0.001974945073015988  # this answer

额外的加速似乎来自避免C和Python函数之间的转换。从反汇编中，我们可以注意到dict实例化发生在C端，只有3个Python调用函数。循环使用DELETE_SUBSCR操作码而不需要函数调用：

>>> dis.dis(method_4)
  2           0 LOAD_GLOBAL              0 (dict)
              2 LOAD_GLOBAL              1 (islice)
              4 LOAD_FAST                0 (d)
              6 LOAD_ATTR                2 (items)
              8 CALL_FUNCTION            0
             10 LOAD_CONST               1 (20000)
             12 CALL_FUNCTION            2
             14 CALL_FUNCTION            1
             16 STORE_FAST               1 (result)

  3          18 SETUP_LOOP              18 (to 38)
             20 LOAD_FAST                1 (result)
             22 GET_ITER
        >>   24 FOR_ITER                10 (to 36)
             26 STORE_FAST               2 (k)
             28 LOAD_FAST                0 (d)
             30 LOAD_FAST                2 (k)
             32 DELETE_SUBSCR
             34 JUMP_ABSOLUTE           24
        >>   36 POP_BLOCK

  4     >>   38 LOAD_FAST                1 (result)
             40 RETURN_VALUE

与迭代器相比method_2：

>>> dis.dis(d.popitem() for _ in range(20000))
  1           0 LOAD_FAST                0 (.0)
        >>    2 FOR_ITER                14 (to 18)
              4 STORE_FAST               1 (_)
              6 LOAD_GLOBAL              0 (d)
              8 LOAD_ATTR                1 (popitem)
             10 CALL_FUNCTION            0
             12 YIELD_VALUE
             14 POP_TOP
             16 JUMP_ABSOLUTE            2
        >>   18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

每个项目都需要一个Python到C函数的调用。