Dtjytyk

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.

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.

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

I found this approach slightly faster (-10% speed) using dictionary comprehension that consumes a loop using range that yields & unpacks the keys & values

dst = {key:value for key,value in (src.popitem() for _ in range(20000))}

on my machine:

your code: 0.00899505615234375

my code:   0.007996797561645508

so about 12% faster, not bad but not as good as not unpacking like Netwave simpler answer

This approach can be useful if you want to transform the keys or values in the process.