Python: maintain key sort order on dictionary

Question

I want to iteratively add elements to a dictionary with an integer key for which I would like to keep a key-ordering. Modern Python (3.7+) keeps an insertion order on dict, but I need a key ordering.

Example use-case:

from collections import defaultdict
import numpy as np

my_dict = defaultdict(list)

for i in range(10):
    idx = i + np.random.randint(10)
    my_dict[idx].append(i)

    # Do something with my_dict
    ...

print(my_dict)

Example output:

>> defaultdict(, {9: [0, 4, 9], 10: [1], 2: [2], 6: [3, 5], 7: [6, 7], 16: [8]})

Desired output:

print(defaultdict(list, sorted(my_dict.items())))
>> defaultdict(, {2: [2], 6: [3, 5], 7: [6, 7], 9: [0, 4, 9], 10: [1], 16: [8]})

Of course, this is a very simple sort, but the index shifts (computed above as i + np.random.randint(10)) can become arbitrarily large and I need a low time-complexity solution. Also note that I am also removing items from my_dict inside the loop (e.g., keys with value lesser or equal to i).

What kind of objects/ data structures does Python provide to achieve this? I've looked at PriorityQueue (heapq), which preserves the ordering I need but only that. I need the get and pop methods from the conventional dictionary + the ordering of e.g., PriorityQueue on the keys without having to expensively sort at every iteration.

Edit: The best current solution that I was able to find is the use of SortedDict from the SortedContainers library. Unfortunately, this solution loses the O(1) time complexity of dict.pop, to O(log N), but the dictionary is kept in key-order with O(log N) instead of O(N log N).

I am still open to hearing alternative solutions that preserves the characteristics of SortedDict, but provides O(1) time complexity for SortedDict.pop. Note that pop is always called on the smallest key, just like a queue (/ dequeue).

user_15475598 · Answer

Here is a function I made to sort the dictionary keys.

def dict_sort(d):
  return({x:d[x] for x in sorted(d)})

Basically, the function iterates through the sorted() version of the keys, and then maps them to a new dictionary (in order) and returns that new dictionary.

Call like this:

a=dict_sort(my_dict)
print(a) #this prints out sorted dictionary

Hope this was a help.

Python: maintain key sort order on dictionary

1 Answers