How to copy list dictionary?

Question

How can I copy a dictionary of lists and what is its complexity? The dictionary I'm trying to copy looks something like this:

myDict = { 'k1': ['a', 'b', 'c'], 'k2': ['d', 'e', 'f'], 'k3': ['g', 'h', 'i'] } 

Answer 1

The easiest way to copy any complex data structure is copy.deepcopy . (If you thought about doing it yourself, see the source to get an idea of ​​what is involved.)

The complexity should obviously be O (NM), where N is the number of dict entries and M is the average number of list entries. But let him work through it:

Let's say you have a dict of key pairs / N values, each value of which is list with an average of M.

If list were simple values, you need to allocate 1 hash table and make 2N + 1 simple copies and possibly N hashes. string immutable, and they are all 1 anyway, and if they were not, Python caches hash values ​​in large strings. So, we have O (N) complete operations.

But list are not simple values. You need to select a new list and copy the elements of M It takes O (M) time. Since there are N, then O (NM).

Thus, the total time is O (N + NM) = O (NM).

And, given that you have NM objects and explicitly want to copy them, you really cannot defeat this.

Of course, it is possible that you could achieve a better order by separating the extraneous parts of what deepcopy does, and porting any hard loops left in Cython or C.

Answer 2

 from copy import deepcopy myCopy = deepcopy(myDict) 

deepcopy always .

Answer 3

You can use the copy() internal dictionary method to copy the dictionary:

Example:

 a = {'s':[1,2,3], 'f':[5,4,2]} b = a.copy() 

if you change a , b does not change.

and the complexity is close to O(1) , because dictionaries use hash tables to store data, access to their data is close to O(1) , then for lists, access to data and memory programs is constant. Therefore, it is close to O(1) .