classification
Title: rotating an ordereddict
Type: enhancement Stage:
Components: Versions: Python 3.4
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Ramchandra Apte, eric.snow, pitrou, rhettinger, serhiy.storchaka
Priority: low Keywords: patch

Created on 2013-02-01 16:32 by pitrou, last changed 2013-03-23 13:51 by rhettinger. This issue is now closed.

Files
File name Uploaded Description Edit
od_rotate.patch pitrou, 2013-02-24 00:11 review
Messages (15)
msg181086 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-01 16:32
It can be useful to rotate an OrderedDict (for example when managing a circular playlist). I haven't found any efficient way to do so from user code, without poking at the internals.

Actually, I envision three methods:

 OrderedDict.rotate(self, n):

   rotate n steps to the right (similarly to deque.rotate())

 OrderedDict.rotate_at(self, key):

   rotate so that the given key ends up in first position

 OrderedDict.rotate_after(self, key):

   rotate so that the given key ends up in last position

(rotate_at, rotate_after could be merged in a single method with a "last" argument, if deemed more elegant)

Note: another solution to the playlist problem would be to have insert_after() and insert_before() methods.
msg181132 - (view) Author: Ramchandra Apte (Ramchandra Apte) * Date: 2013-02-02 03:49
Will attach patch when I get free (10 hours from now)
msg181140 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-02 07:32
It is trivial.

def rotate(od, n):
    for i in range(n):
        k, v = od.popitem(False)
        od[k] = v

And those functions look too specialized.
msg181142 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-02 07:56
> It is trivial.
> 
> def rotate(od, n):
>     for i in range(n):
>         k, v = od.popitem(False)
>         od[k] = v

That's O(n), with many spurious insertions and deletions.

> And those functions look too specialized.

How so? rotating sounds quite generic to me. deques already allow
rotating.
msg181147 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-02 08:53
> That's O(n), with many spurious insertions and deletions.

Any implementation is O(n).

> deques already allow rotating.

I agree that the rotation makes some sense for such collections as deque or OrderedDict (although it is easy implemented in user code). But there are no rotate_at() and rotate_after() in deque.
msg181148 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-02 09:02
> > That's O(n), with many spurious insertions and deletions.
> 
> Any implementation is O(n).

For rotate() perhaps (but still, it can be more efficient in that it can
just move the list head once instead of repeatedly deleting and
inserting elements). But rotate_at() / rotate_after() can probably be
O(1), unless I'm missing something.

> > deques already allow rotating.
> 
> I agree that the rotation makes some sense for such collections as
> deque or OrderedDict (although it is easy implemented in user code).
> But there are no rotate_at() and rotate_after() in deque.

That's because a deque is not a mapping ;-) In other words, if a deque
was enough I'd be using a deque, not a OrderedDict.
msg181150 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-02 09:11
> But rotate_at() / rotate_after() can probably be O(1), unless I'm missing something.

Hmm, perhaps. But only for current implementation. With more effective deque-like implementation (when linked list items grouped in fixed-size chunks) it will be O(n).
msg181152 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-02 09:22
> > But rotate_at() / rotate_after() can probably be O(1), unless I'm
> missing something.
> 
> Hmm, perhaps. But only for current implementation. With more effective
> deque-like implementation (when linked list items grouped in
> fixed-size chunks) it will be O(n).

Does your deque-like implementation preserve O(1) deletion?
msg181160 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-02 11:12
> Does your deque-like implementation preserve O(1) deletion?

Ah, OrderedDict should provide O(1) deletion for arbitrary key. Then deque-
like implementation should use variable-size chunks and rotate_at() / 
rotate_after() are possible with O(1).
msg182838 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-24 00:11
Attaching proof of concept patch for rotate_at() and rotate_after().
I am now conviced that bare rotate() isn't very useful.
msg182864 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-02-24 09:41
Perhaps for consistency with popitem() and move_to_end() it is worth to merge rotate_at() and rotate_after() in one method (rotate_to()? move_to()?) with a boolean parameter.
msg182866 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-24 10:27
> Perhaps for consistency with popitem() and move_to_end() it is worth
> to merge rotate_at() and rotate_after() in one method (rotate_to()?
> move_to()?) with a boolean parameter.

Yes, perhaps. rotate_to(last=False) sounds ok, but perhaps a native
English speaker can suggest a better name.
msg183165 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-02-27 17:24
My only attraction to adding any of the rotate variants is that they provide functionality that can't be done efficiently by a user without access to the underlying data structure.

However, looking only at the API, the methods seem a bit awkward and a bit at odds with how people think of ordered dicts (rotate is not a method that comes to mind for my mental model).   

When I built the OD code, I looked at many existing implementations (in Python and other languages), and I don't recall seeing rotation in any of them.

In the absence of strong use cases, I prefer to keep the API thin so that OD's remain easy to learn and remember.
msg183173 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2013-02-27 18:56
> In the absence of strong use cases, I prefer to keep the API thin
> so that OD's remain easy to learn and remember.

It could be a separate function or a dedicated subclass if you prefer.
But providing it in the stdlib would avoid 3rd party code having to poke inside the OD internals.
msg185047 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-03-23 13:51
For the time being, I want to keep the OrderedDict API simple and avoid feature creep into rotation logic.
History
Date User Action Args
2013-03-23 13:51:43rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg185047
2013-02-27 18:56:16pitrousetmessages: + msg183173
2013-02-27 17:24:23rhettingersetpriority: normal -> low

messages: + msg183165
2013-02-24 10:27:06pitrousetmessages: + msg182866
2013-02-24 09:41:43serhiy.storchakasetmessages: + msg182864
2013-02-24 00:11:41pitrousetfiles: + od_rotate.patch
keywords: + patch
messages: + msg182838
2013-02-02 17:44:53rhettingersetmessages: - msg181184
2013-02-02 17:38:44rhettingersetmessages: + msg181184
2013-02-02 17:23:58rhettingersetassignee: rhettinger
2013-02-02 11:12:50serhiy.storchakasetmessages: + msg181160
2013-02-02 09:22:42pitrousetmessages: + msg181152
2013-02-02 09:11:19serhiy.storchakasetmessages: + msg181150
2013-02-02 09:02:56pitrousetmessages: + msg181148
2013-02-02 08:53:29serhiy.storchakasetmessages: + msg181147
2013-02-02 07:56:56pitrousetmessages: + msg181142
2013-02-02 07:32:53serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg181140
2013-02-02 03:49:12Ramchandra Aptesetnosy: + Ramchandra Apte
messages: + msg181132
2013-02-01 20:04:14eric.snowsetnosy: + eric.snow
2013-02-01 16:32:03pitroucreate