CODEWITHSUNDEEP
pythonalgorithmdata-structurestime-complexitybig-o
Muhammad Safwan
Muhammad Safwan

Reputation: 1024

Reduce time complexity of pairwise dictionary construction

Let say I have dict

slots = {
    "a": {"a": "Data for A"},
    "b": {"b": "Data for B"},
    "c": {"c": "Data for c"},
}

and a list

numbers = [1, 2, 3]

Now what i want that for each nested dict duplicate it the length times of list and add each object of list with some key

like this:

output = [
    {"a": "Data for A", "number": 1},
    {"a": "Data for A", "number": 2},
    {"a": "Data for A", "number": 3},
    {"b": "Data for B", "number": 1},
    {"b": "Data for B", "number": 2},
    {"b": "Data for B", "number": 3},
    {"c": "Data for c", "number": 1},
    {"c": "Data for c", "number": 2},
    {"c": "Data for c", "number": 3},
]

I have achieved the desired output by using following code:

output = []
for key in slots:
    for number in numbers:
        data = slots[key].copy()
        data["number"] = number
        output.append(data)

but the issue here is the time complexity which is in this case is O(n^2) I want it to reduce to O(n) or O(n log n) I did too much brainstorming and searching but could not find the appropriate solution. One thing I found is

https://dev.to/leandronsp/how-to-reduce-the-time-complexity-of-nested-loops-1lkd#:~:text=Putting%20all%20together,from%20the%20previously%20created%20%22index%22

but don't know how to use it in my case. May be another dict to maintain indexes but i couldn't figure it out how I can do it.

Any help will be appreciated, Thank you!

Upvotes: 0

Views: 84

Answers (1)

BrokenBenchmark
BrokenBenchmark

Reputation: 19252

What you're describing isn't possible. You can't do better than O(n * m).

(where n is the length of the dictionary list, and m is the length of the numbers list.)

You need O(n * m) memory just to be able to store the result, and we need to iterate over each pair of elements from each list to generate its corresponding dictionary in the final result. Iterating over each pair alone takes O(n * m) time, so that gives a lower bound for how fast the algorithm can run.

You might want to look into itertools.product() -- it may be faster for your use case. But since you're asking about time complexity, the only (correct) answer that can be given is that what you're describing isn't possible.

Upvotes: 0

Related Questions