Fastest way to pop N items from a large dict

Question

I have a large dict src (up to 1M items) and I would like to take N (typical values would be N=10K-20K) items, store them in a new dict dst and leave only the remaining items in src. It doesn't matter which N items are taken. I'm looking for the fastest way to do it on Python 3.6 or 3.7.

Fastest approach I've found so far:

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]

Is there anything better? Even a marginal gain would be good.

Answer 1

A simple comprehension inside dict will do:

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

Here you have the timing tests

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

Results:

Method 1:  0.007701821999944514
Method 2:  0.004668198998842854

Answer 2

This is a bit faster still:

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

Compared to other versions, using Netwave's testcase:

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

The extra speedup seems to come from avoiding transitions between C and Python functions. From disassembly we can note that the dict instantiation happens on C side, with only 3 function calls from Python. The loop uses DELETE_SUBSCR opcode instead of needing a function call:

>>> 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

Compared with the iterator in 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

which needs a Python to C function call for each item.