How can i copy a dictionary of lists and what is its complexity? The dictionary I'm tryint to copy is something like this:
myDict = { 'k1': ['a', 'b', 'c'],
'k2': ['d', 'e', 'f'],
'k3': ['g', 'h', 'i'] }
The simplest way to copy any complex data structure is copy.deepcopy. (If you were thinking about doing it yourself, see the source to get an idea of what's involved.)
The complexity should obviously be O(NM), where N is the number of dict entries and M the average number of list entries. But let's work through it:
Let's say you have a dict of N key/value pairs, each value being a list with an average of M elements.
If the lists were simple values, you'd need to allocate 1 hash table, and do 2N+1 simple copies and possibly N hashes. The strings are immutable, and they're all length 1 anyway, and if they weren't, Python caches hash values in large strings. So, we've got O(N) total operations.
But the lists are not simple values. You need to allocate a new list and copy M elements. That takes O(M) time. Since there are N of them, that's O(NM).
So, the total time is O(N + NM) = O(NM).
And, given that you have NM objects and explicitly want to copy all of them, there's really no way you could beat that.
Of course it's conceivable that you could get an order of magnitude improvement by stripping down the extraneous parts of what deepcopy does and porting any tight loops left over into Cython or C.