CODEWITHSUNDEEP
pythonpython-3.xtime-complexity
bakumpai
bakumpai

Reputation: 1

Why initialize Set from dict.keys() is faster than using set.add()?

Code

total_exc_time = 0
for _ in range(10):
    start = time.time()
    set_a = set()
    dict_a = dict()
    add = set_a.add
    for index in range(1000000):
        dict_a[index] = index
        add(index)
    total_exc_time += ((time.time() - start) * 1000)

total_exc_time = 0
for _ in range(10):
    start = time.time()
    dict_a = dict()
    for index in range(1000000):
        dict_a[index] = index
    set_a = set(dict_a.keys())
    total_exc_time += ((time.time() - start) * 1000)

Result

332.3066234588623 ms
283.2982540130615 ms

isn't the time complexity for the first code is O(n) and later code is 2 times O(n)?

Upvotes: 0

Views: 74

Answers (1)

anch2150
anch2150

Reputation: 81

They are equivalent. The heavy lifting here to calculate the key hash. In both, it happens twice: add to a dict and then add to set. Other procedures should be light. You can use debugger to show the C calls to verify.

In addition to function call overhead mentioned by Carcigenicate, memory management might also play a role. If the set knows the length, it could possibly avoid copying data over when the predefined space isn't enough.

Upvotes: 1

Related Questions