Trjtdtk

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.