Sub-dictionary from dictionary. Create another dictionary with dict comprehension, or delete keys from a copy of the original dictionary

A little feedback on both answers; neither is accurate IMHO, because of the way they're selecting keys.

They're effectively treating the dictionary like a list and keeping n items if your data is setup that way you likely don't need a dictionary (but instead a sorted list).

With regards to Option 2

I'd wager you're performing a lookup like this:

new_dict = {k:v for k,v in parent_dict.items() if k in selections}

in which case the performance decreases as len(selections) increases; one way to somewhat mitigate this would be to use a set instead of a list for selections; effectively O(m*n) (where m is the size of the parent_dict and n is the number of selections)

since the loop on n won't always require looping on the full n it'd probably be closer to O((n**2-n)/2) where (n**2-2)/2 is the sum of all numbers between 1 and n.

On the other hand, looping for the removal in Option 1 is O(2m-n).

O(m) for copying the dict and O(m-n) for removing the keys

There are non-vanilla (lodash comes to mind) solutions that are highly optimized and will likely be faster, but strictly looking at the time complexity it seems that deleting ought to be faster with realistic key selections.

Which option is best will likely depend on the sizes of m & n

I just had a blond moment, but want to leave my ignorance up there for any other future passerby

You should do this: new_dict = {k: parent_dict[k] for k in selections}

You don't pay the O(m) penalty for copying the dict, adding items to a dict is O(1) and looping over the selections is O(n) so you're sitting pretty at O(2n) ie O(n) -- I don't think anything is going to be faster than that.

Alright, here's code:

import random
import timeit

m = 3_000
n0 = 300
n1 = 600

trials = 10_000

def remove(parent_dict, kept_keys):
    result = parent_dict.copy()
    for key in parent_dict.keys():
        if key not in kept_keys:
            del result[key]
    return result

def add_dict_comprehension(parent_dict, kept_keys):
    return {k:v for k,v in parent_dict.items() if k in kept_keys}

def add_key_comprehension(parent_dict, kept_keys):
    return {k:parent_dict[k] for k in kept_keys}

def add_dict_comprehension_set(parent_dict, kept_keys):
    return {k:v for k,v in parent_dict.items() if k in kept_keys}

def generate_test_data(m, n0, n1):
    parent_dict = {}
    for key in range(m):
        parent_dict[key] = 0

    target_keys = random.sample(range(m), random.randint(n0, n1))

    return parent_dict, target_keys

test_functions = {
    'remove': (remove, lambda x: x),
    'add_dict_comprehension': (add_dict_comprehension, lambda x: x),
    'add_key_comprehension': (add_key_comprehension, lambda x: x),
    'add_dict_comprehension_set': (add_dict_comprehension, lambda keys: set(keys)),
    'remove_set': (remove, lambda keys: set(keys)),
}

results = {k:[] for k in test_functions.keys()}

for _ in range(trials):
    parent_dict, target_keys = generate_test_data(m, n0, n1)


    for k,(func, preprocessor) in test_functions.items():

        # Not timing the preprocessing, assuming this is done on construction
        processed_keys = preprocessor(target_keys)
        
        starttime = timeit.default_timer()
        func(parent_dict, processed_keys)
        results[k].append(timeit.default_timer() - starttime)


def avg(lst):
    return sum(lst)/len(lst)

def stddev(lst):
    mean = avg(lst)
    r2 = sum([(i-mean)**2 for i in lst])
    bias = len(lst) - 1
    return (r2/bias)**.5

result_data = {k: {'avg': avg(v), 'stddev': stddev(v)} for k,v in results.items()}

title_len = max(len(i) for i in result_data.keys())
for (name, data) in sorted(result_data.items(), key = lambda item: item[1]['avg']):
    print(f"{name}: {''.join([' ']*(title_len-len(name)))} Avg. {data['avg']} [Stddev: {data['stddev']}]")

As expected, the key comprehension is the fastest and using sets instead of lists are faster for both Option 1&2) -- sets have an average lookup time of O(1) so you avoid most of the searching costs of an array

add_key_comprehension:       Avg. 8.616499952040612e-05 [Stddev: 4.227672839185718e-05]
add_dict_comprehension_set:  Avg. 0.0001553589993272908 [Stddev: 3.535997011243502e-05]
remove_set:                  Avg. 0.00021654199925251306 [Stddev: 0.00017905888806226246]
add_dict_comprehension:      Avg. 0.013669110001646913 [Stddev: 0.0031769500128693085]
remove:                      Avg. 0.0138856839996879 [Stddev: 0.004191406076651088]

Option 2 looks fast enough - see below

import random
import string
import timeit

letters = string.ascii_lowercase


def _get_word():
    return ''.join(random.choice(letters) for i in range(10))

N = 10000
CHUNK = 400
ITERATIONS = 30
# dummy dict with N entries
data = {_get_word(): _get_word() for _ in range(0, N)}


for _ in range(0,ITERATIONS):
    starttime = timeit.default_timer()

    sub_dicts = []
    temp = {}
    for idx,(k,v) in enumerate(data.items()):
        temp[k] = v
        if idx % CHUNK == 0:
            sub_dicts.append(temp)
            temp = {}
    print("Option 2: The time difference is :", timeit.default_timer() - starttime)

output (delta T in seconds)

Option 2: The time difference is : 0.003928793012164533
Option 2: The time difference is : 0.006472171982750297
Option 2: The time difference is : 0.006867899966891855
Option 2: The time difference is : 0.007105670985765755
Option 2: The time difference is : 0.004680399026256055
Option 2: The time difference is : 0.0034195330226793885
Option 2: The time difference is : 0.0034254349884577096
Option 2: The time difference is : 0.003625455021392554
Option 2: The time difference is : 0.003444572037551552
Option 2: The time difference is : 0.003441892040427774
Option 2: The time difference is : 0.0038558689993806183
Option 2: The time difference is : 0.00340640899958089
Option 2: The time difference is : 0.004021176020614803
Option 2: The time difference is : 0.004761706979479641
Option 2: The time difference is : 0.0039043189608491957
Option 2: The time difference is : 0.0035160399856977165
Option 2: The time difference is : 0.003446961985900998
Option 2: The time difference is : 0.0038189300103113055
Option 2: The time difference is : 0.003589348983950913
Option 2: The time difference is : 0.0033721639774739742
Option 2: The time difference is : 0.0033731560106389225
Option 2: The time difference is : 0.0033843390410766006
Option 2: The time difference is : 0.003322889970149845
Option 2: The time difference is : 0.0034315589582547545
Option 2: The time difference is : 0.003400936024263501
Option 2: The time difference is : 0.0032910890295170248
Option 2: The time difference is : 0.003319227951578796
Option 2: The time difference is : 0.003392132988665253
Option 2: The time difference is : 0.0032848399714566767
Option 2: The time difference is : 0.003325468976981938

Option 2 is faster :

import timeit

# create a dummy dict
dict1 = {}
for key in range(30000):
    dict1[key] = 0


# both option keep the first 4500 key

# option 1 :
starttime = timeit.default_timer()
dict_op1 = dict1.copy()
for key, value in dict1.items():
    if key >= 4500:
        del dict_op1[key]
op1_time = timeit.default_timer() - starttime

# option 2 :
starttime = timeit.default_timer()
dict_op2 = {key: value for key, value in dict1.items() if key < 4500}
op2_time = timeit.default_timer() - starttime

print("option1 time:" + str(op1_time))
print("option2 time:" + str(op2_time))

output :

option1 time:0.0025474
option2 time:0.0009779