[issue17100] rotating an ordereddict
Raymond Hettinger added the comment: For the time being, I want to keep the OrderedDict API simple and avoid feature creep into rotation logic. -- resolution: - rejected status: open - closed ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Raymond Hettinger added the comment: 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. -- priority: normal - low ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Antoine Pitrou added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Serhiy Storchaka added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Antoine Pitrou added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Antoine Pitrou added the comment: Attaching proof of concept patch for rotate_at() and rotate_after(). I am now conviced that bare rotate() isn't very useful. -- keywords: +patch Added file: http://bugs.python.org/file29213/od_rotate.patch ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Serhiy Storchaka added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Antoine Pitrou added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Serhiy Storchaka added the comment: 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). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Antoine Pitrou added the comment: 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? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Serhiy Storchaka added the comment: 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). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Changes by Raymond Hettinger raymond.hettin...@gmail.com: -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Raymond Hettinger added the comment:
Please don't rush to make patches. It isn't even clear that this is a good
idea.
AFAICT, none of the many extant implementation of ordered dictionaries in any
language currently implement a rotate operation.
FWIW, the iter() and move_to_end() methods are likely your best bet for
implementing a rotate function using the current API and without doing any
ordered dictionary key lookups:
from collections import OrderedDict
from itertools import islice
def rotate(d, n):
# quick demo
if n 0:
for k in list(islice(d, n)):
d.move_to_end(k)
elif n 0:
for k in list(islice(reversed(d), -n)):
d.move_to_end(k, 0)
d = collections.OrderedDict.fromkeys('abcdefghijk')
list(d)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
rotate(d, 3)
list(d)
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'a', 'b', 'c']
rotate(d, -3)
list(d)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue17100
___
___
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Changes by Raymond Hettinger raymond.hettin...@gmail.com: -- Removed message: http://bugs.python.org/msg181184 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
New submission from Antoine Pitrou: 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. -- messages: 181086 nosy: pitrou, rhettinger priority: normal severity: normal status: open title: rotating an ordereddict type: enhancement versions: Python 3.4 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Changes by Eric Snow ericsnowcurren...@gmail.com: -- nosy: +eric.snow ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Ramchandra Apte added the comment: Will attach patch when I get free (10 hours from now) -- nosy: +ramchandra.apte ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Serhiy Storchaka added the comment: 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. -- nosy: +serhiy.storchaka ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue17100] rotating an ordereddict
Antoine Pitrou added the comment: 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. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17100 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
