CODEWITHSUNDEEP
pythonpython-3.xperformancedictionaryoptimization
Ivailo Karamanolev
Ivailo Karamanolev

Reputation: 823

Fastest way to pop N items from a large dict

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.

Upvotes: 20

Views: 1878

Answers (3)

Netwave
Netwave

Reputation: 42756

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

Upvotes: 19

jpa
jpa

Reputation: 12176

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.

Upvotes: 12

Jean-Fran&#231;ois Fabre
Jean-Fran&#231;ois Fabre

Reputation: 140276

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.

Upvotes: 3

Related Questions