# Sorting ordered dicts

**URL:** <https://discuss.python.org/t/sorting-ordered-dicts/25336>\
**Category:** Ideas\
**Created:** [March 31, 2023, 2:16pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336 "2023-03-31T14:16:57Z")\
**Posts on this page:** 15\
**Page:** 2

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 2, 2023, 5:09pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/21 "2023-04-02T17:09:32Z")

</div>

> [@Rosuav](#):
>
> You’d be amazed how efficient timsort is at tweaking mostly-sorted data. Given that a dictionary remembers insertion order, you could fairly easily re-sort and return to dict form, and then it’s mostly sorted for next time.

Yes, that’s actually what I’m advocating for.

> [@methane](#):
>
> What you call “in-place” is not true “in-place”.

Oh, so `id(d)` before and after sort would return different memory addresses ? Other variables (or attributes) holding the dict would still hold the unsorted version ?  
I think not.

> [@methane](#):
>
> Then, `dict(sorted(dic.items(), key=itemgetter(1)))`.

Still wrong… this is the dict copied and ordered by value. Nothing to do with the original use case : having a dict initially sorted (in-place is better), then edited, then iterating the updated values following the former ordering.

> [@methane](#):
>
> Linked list is slow and memory inefficient. Dict is faster and more efficient because it is array-based.
> 
> If can not believe me, try implementing `OrderedDict.sort()`.

Slow compared to what ? It would still be faster than any alternative listed here, by omitting unnecessary operations - with the additional advantages of being in-place as far as the public API can see, which is a small feature in itself.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 2, 2023, 5:33pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/22 "2023-04-02T17:33:16Z")

</div>

> [@Gouvernathor](#):
>
> Oh, so `id(d)` before and after sort would return different memory addresses ? Other variables (or attributes) holding the dict would still hold the unsorted version ?  
> I think not.

Even though `id(d)` is not changed, sort is executed temporal array, and whole linked list will be reconstructed. Generally speaking, “in-place sort algorithm” doesn’t need temporal list + full reconstruction.

And that’s why your “in-place sort” would be much slower than simple “out-place” dict sort.

> [@Gouvernathor](#):
>
> Still wrong… this is the dict copied and ordered by value. Nothing to do with the original use case : having a dict initially sorted (in-place is better), then edited, then iterating the updated values following the former ordering.

I can not understand your use case. I stop discussing about it.

> [@Gouvernathor](#):
>
> Slow compared to what ?

Compared to:

```py
items = sorted(d.items(), key=itemgetter(0))
d.clear()
d.update(items) # This is what you call "in-place"!

```

> [@Gouvernathor](#):
>
> It would still be faster than any alternative listed here, by omitting unnecessary operations - with the additional advantages of being in-place as far as the public API can see, which is a small feature in itself.

Try implementing it yourself. Then you would understand how many operations are needed to reconstruct linked list in OrderedDict.  
Both of Python implementation and C implementation are good. They are different from each other, but both need significant overhead for just reorder the linked list.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 2, 2023, 7:52pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/23 "2023-04-02T19:52:52Z")

</div>

So, I did some tests, which are too long to copypaste here, so [here it is](https://gist.github.com/Gouvernathor/e44028a6ecda35f052d6845e500064d2) (a gist with 5 different implems I’ll detail here).

- Option A is `self.update(sorted(self.items(), key=itemgetter(0)))`, which some here said it would be the quickest. Its drawback is, it doesn’t support the `key=` parameter.
- Option B is sorting the keys using sorted() (which all the following options will do as well), then mapping them with their values, then passing that through update().
- Option C is @storchaka’s : calling move\_to\_end on each key in sorted order.
- Option D is the same, but without calling move\_to\_end, and instead executing a copypasted version of its code without the unnecessary if (since we always move to the last end).
- Option E is a simplification of the previous one, avoiding unnecessary writes and rewrites of pointers in the double-linked list.

Here is my timing code:

```py
import timeit
import random
import collecs # my other file is collecs.py

def time(d=None, /):
    if d is None:
        d = collecs.OrderedDict((random.randrange(1000), object()) for _k in range(100))
    sd = d.copy()
    print(tuple(d))
    sd.sort_C()
    print(tuple(sd))

    rv = {}
    for let in "CDE":
        rv[let] = timeit.Timer(f"dc.sort_{let}()", setup="dc = d.copy()", globals=dict(d=d)).autorange()
        dc = d.copy()
        getattr(dc, f"sort_{let}")()
        if dc != sd:
            print(f"sort_{let} failed")
            print(tuple(dc))
    return rv

```

I know, it only tests one type of key and one size of dict, but it’s a very basic version.  
Also, you have to edit your `collections/ __init__.py` to make it use the pure-python version instead of overriding it with the C version, otherwise implems D and E don’t work. Anyway.  
~~As I tested it on 3.9, it turns out options A and B don’t work : update() doesn’t update the order of the elements. I’ll try again on later versions of python when I find the time (pun intended).~~ It turns out I forgot the .clear was required before .update. Anyway.  
The results are as follows :  
`A:(5000, 0.2827916), B:(5000, 0.2619572), C:(10000, 0.2920622), D:(10000, 0.21275239), E:(20000, 0.3542883)]`

So, contrary to your predictions, it seems that creating a new dict is the worst way, and that my idea of optimizing Serhiy’s idea is the best performance-wise. And I’m not sure how in-place you would consider it, @methane, but as far as the public API goes it certainly is.

---

<div class="post-metadata">

**Author:** ![NeilGirdhar](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/neilgirdhar/32/5776_2.png) [@NeilGirdhar](https://discuss.python.org/u/NeilGirdhar)\
**Post date:** [April 2, 2023, 10:59pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/25 "2023-04-02T22:59:57Z")

</div>

> [@Gouvernathor](#):
>
> Option A is `self.update(sorted(self.items(), key=itemgetter(0)))`, w

Or just add a list, and that’s basically option A without the entire `self.update` call.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 3, 2023, 3:08am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/27 "2023-04-03T03:08:58Z")

</div>

I posted this as a [proof-of-concept PR](https://github.com/python/cpython/pull/103203), so the tests would run : none failed (but at the same time none call the method, so…) (and actually it seems there may not be _any_ test on the OrderedDict class ??).

There are some objections from @rhettinger on Github, I’ll answer them here.

> This is a permanent API change just to optimize the idiom `OrderedDict(sorted(od.items()))` or `for k in sorted(od): od.move_to_end(k)`.

Yes, more like the second one in that it’s in-place.

> AFAICT people rarely use those idioms and when they do it is never speed critical; otherwise, they would be using a regular dict which already has much better performance than `collections.OrderedDict`.

I think there’s a chicken-and-egg situation here : people don’t use it _because_ there’s no optimized way to do it - and also, in my opinion, because the for-move\_to\_end idiom itself is not obvious. Having an easily linkable OrderedDict.sort could change that a lot.

> Also, `collections.OrderedDict` is close to being a dead part of the collections module. Mostly It is only useful for being backwards compatible to versions before Python 3.6 and for creating LRU cache variants.
> 
> Lastly, it isn’t desirable to have API to diverge further from the regular dict.

I’ll merge those into one, because I don’t see why it wouldn’t be desirable to add things to OrderedDict _per se_, other than for keeping it “dead”.

Yes, the OrderedDict is mostly dead as it stands. Not as much as the UserX classes, since it does have the move\_to\_end method and the popitem(last=False) feature, but I agree it’s still quite comatose. I’m proposing we change that, and maybe not even in a big way. Why would changing its deadness be a bad thing at all ?  
I understand the fear of adding a new feature which will have to be maintained, but not the link between that and the deadness of the class.

In a way I think this is indirectly asking why this should be done on OrderedDict rather than the builtin dict : primarily sorting is related to ordering, so it fits more the purpose of OrderedDict to have its ordering being changed, than the simple dict.  
Furthermore, according to the thread I linked in the OP, there are performance and implementation issues with implementing a dict.sort method. On the opposite, this implementation is - as far as my benchmarks went - the quickest available, period, seemingly even better than creating a new dict by sorting the items. My intuition (for now) is that taking aventage of the doubly-linked list, while being a waste of memory, lets us gain time as compared to the builtin dict. The lock-during-sort feature isn’t a problem in any of the proposed implementations, as was the fear for a dict.sort method.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 3, 2023, 4:11am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/28 "2023-04-03T04:11:47Z")

</div>

Please share your benchmark in complete, runnable form using gist or github repository.  
I can not believe benchmark result no one can reproducible.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 3, 2023, 4:16am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/29 "2023-04-03T04:16:27Z")

</div>

> [@Gouvernathor](#):
>
> So, contrary to your predictions, it seems that creating a new dict is the worst way, and that my idea of optimizing Serhiy’s idea is the best performance-wise. And I’m not sure how in-place you would consider it, @methane, but as far as the public API goes it certainly is.

Wait, are you sorting OrderedDict??  
My prediction is sorting dict is much faster than sorting OrderedDict.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 3, 2023, 10:14am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/30 "2023-04-03T10:14:22Z")

</div>

Please make an effort to stay relevant to the topic, everybody here talks about OrderedDict, it’s even in the name of the thread. We were talking about doubly-linked lists, that was always the case of OrderedDict and never of dict, so why did you think we weren’t talking about sorting OrderedDict ??

My benchmark _is_ in a gist, and the code to test it I copypasted in a message above. Just look up.  
It won’t work until you edit your `collections/ __init__.py` file to make it not use the C-boosted implementation though.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 3, 2023, 11:58am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/31 "2023-04-03T11:58:03Z")

</div>

Do you mean you need to use OrderedDict even if sorting dict is much (say 10x) faster than sorting OrderedDict?  
Why you can not use dict?

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 4, 2023, 11:34am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/32 "2023-04-04T11:34:18Z")

</div>

Because as I said in the OP, another thread is dedicated to sorting dict and it poses other issues - implementation issues apparently - so this is about taking the other approach, OrderedDict.  
Also, I only have a python implementation for what I want to do, even though if it were accepted it would eventually get a C version. So benchmarking my implem against C-based dict is comparing apples and oranges : of course it will be faster to compare execution of a C code with a Python code, but it gives no insight whatsoever as to the performance of a C version of my implem, on OrderedDict, versus your (plural your) ideas using the native dict.

Even conceptually it’s not trivial : sorting a native dict requires entering n keys into the mapping after pulling them out, whereas sorting an OrderedDict only requires setting 2\*n links. It’s not obvious to me that the one would be faster than the other.  
That’s the intuition I shared earlier : I suspect the OrderedDict structure, while heavier in memory, allows us to gain time as compared to dict in this sorting use-case.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 4, 2023, 3:34pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/33 "2023-04-04T15:34:17Z")

</div>

> [@Gouvernathor](#):
>
> Because as I said in the OP, another thread is dedicated to sorting dict and it poses other issues - implementation issues apparently - so this is about taking the other approach, OrderedDict.

I think it is a bad motivation.

Since OrderedDict uses 2x memory and slow to create than dict, adding `sort` method only to `OrderedDict` makes sense to me only if:

a. Only `OrderedDict` have strong use cases, or  
b. `OrderedDict.sort()` will be much efficient than `dict.sort()`.

You didn’t explain why OrderedDict is important for your use case.

(b) is the only reason to add sort method only to OrderedDict to me.  
That is why I compared dict.sort() and OrderedDict.sort() performance. It is very relevant to this topic.

> [@Gouvernathor](#):
>
> Even conceptually it’s not trivial : sorting a native dict requires entering n keys into the mapping after pulling them out, whereas sorting an OrderedDict only requires setting 2\*n links. It’s not obvious to me that the one would be faster than the other.  
> That’s the intuition I shared earlier : I suspect the OrderedDict structure, while heavier in memory, allows us to gain time as compared to dict in this sorting use-case.

OrderedDict.sort() requires n times lookup + setting 2\*n links. Dict.sort() requires n insertion.  
I don’t know which is faster, but I would not expect OrderedDict.sort() to be more than twice as fast as dict.sort(). Both are O(n \* log n) anyway.

---

<div class="post-metadata">

**Author:** ![Gouvernathor](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/gouvernathor/32/7957_2.png) [@Gouvernathor](https://discuss.python.org/u/Gouvernathor)\
**Post date:** [April 4, 2023, 6:14pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/34 "2023-04-04T18:14:24Z")

</div>

> [@methane](#):
>
> a. Only `OrderedDict` have strong use cases

> [@methane](#):
>
> You didn’t explain why OrderedDict is important for your use case.

Not for that, I was sort-of expecting the reverse, that the new feature had the potential to attract people into using OrderedDict - not that it’s a goal in itself either. That, and sorting being related to ordering and ordering to OrderedDict which makes the feature “fit” more with OrderedDict as a concept. So, no for your (a).

As for performance benchmarks, I’ll say again : you can’t compare C and Python. If we want a relevant benchmark, my OrderedDict.sort needs to be ported to C language. But I don’t think I’m able to write that, and I’m certainly incapable of compiling it.

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 5, 2023, 7:23am UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/35 "2023-04-05T07:23:12Z")

</div>

> [@Gouvernathor](#):
>
> As for performance benchmarks, I’ll say again : you can’t compare C and Python.

Of course. I just wanted you to realize that `OrderedDict.sort()` needs to do more than just update the double linked list.

---

<div class="post-metadata">

**Author:** ![Stefan2](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stefan2/32/18492_2.png) [@Stefan2](https://discuss.python.org/u/Stefan2)\
**Post date:** [April 5, 2023, 1:30pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/36 "2023-04-05T13:30:34Z")

</div>

What else does it need to do? Doesn’t `move_to_end` also only update the double linked list?

---

<div class="post-metadata">

**Author:** ![methane](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/methane/32/43_2.png) [@methane](https://discuss.python.org/u/methane)\
**Post date:** [April 5, 2023, 1:50pm UTC](https://discuss.python.org/t/sorting-ordered-dicts/25336/37 "2023-04-05T13:50:28Z")

</div>

C implementation of move\_to\_end does:

1. Lookup key. (dict lookup)
2. Find list node from key index
3. Move the node to the end.

Since list node position is tightly coupled with internal index of the key, OrderedDict.sort() need to do this n times.

[Previous page](https://discuss.python.org/t/sorting-ordered-dicts/25336.md?page=1)