OrderedDict.peekitem()
Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away. My proposal is to add a peekitem() method to OrderedDict. This method would have the same signature and would return the same thing as popitem(), it just wouldn't modify the data structure. -Kale P.S. There is already a way to peek at the last item an OrderedDict, but it hides the intent of the code and you wouldn't think of it if you weren't familiar with python: next(reversed(ordered_dict))
On Jul 6, 2015 4:49 PM, "Kale Kundert" <kale@thekunderts.net> wrote:
Today I was trying to use collections.OrderedDict to manage a LIFO queue,
and I
was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
My proposal is to add a peekitem() method to OrderedDict. This method would have the same signature and would return the same thing as popitem(), it just wouldn't modify the data structure.
-Kale
P.S. There is already a way to peek at the last item an OrderedDict, but it hides the intent of the code and you wouldn't think of it if you weren't familiar with python: next(reversed(ordered_dict))
What about just making OrderedDict.values support indexing?
On Jul 6, 2015, at 07:56, Todd <toddrjen@gmail.com> wrote:
On Jul 6, 2015 4:49 PM, "Kale Kundert" <kale@thekunderts.net> wrote:
Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
My proposal is to add a peekitem() method to OrderedDict. This method would have the same signature and would return the same thing as popitem(), it just wouldn't modify the data structure.
-Kale
P.S. There is already a way to peek at the last item an OrderedDict, but it hides the intent of the code and you wouldn't think of it if you weren't familiar with python: next(reversed(ordered_dict))
What about just making OrderedDict.values support indexing?
Then you can't use integers as keys. Also, would a novice really expect d[0] to return an item (key, value pair) rather than a value? I think this pretty much has to be a nonstandard function, not an ambiguous reuse of subscripting. Or, maybe better, OrderedDict could have extended keys/values/items views that return something that's tuple-like as well as set-like (because indexing doesn't have any meaning on the standard views to conflict with, and nobody would expect mutability, and it would be obvious whether you're getting keys, values, or items).
Hello, On Mon, 06 Jul 2015 07:39:58 -0700 Kale Kundert <kale@thekunderts.net> wrote:
Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
What's wrong with using list, collections.Deque, heapq to manage a LIFO queue? -- Best regards, Paul mailto:pmiscml@gmail.com
On 06/07/2015 16:38, Paul Sokolovsky wrote:
Hello,
On Mon, 06 Jul 2015 07:39:58 -0700 Kale Kundert <kale@thekunderts.net> wrote:
Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
What's wrong with using list, collections.Deque, heapq to manage a LIFO queue?
Or queue.LifoQueue or even multiprocessing.Queue depending on the precise requirements? -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing? On Monday, July 6, 2015 at 10:49:44 AM UTC-4, Kale Kundert wrote:
Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
My proposal is to add a peekitem() method to OrderedDict. This method would have the same signature and would return the same thing as popitem(), it just wouldn't modify the data structure.
-Kale
P.S. There is already a way to peek at the last item an OrderedDict, but it hides the intent of the code and you wouldn't think of it if you weren't familiar with python: next(reversed(ordered_dict))
_______________________________________________ Python-ideas mailing list Python...@python.org <javascript:> https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
On Mon, Jul 6, 2015 at 2:30 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing?
OrderedDict doesn't currently do the same thing. But you could use a SortedDict to implement an OrderedDict and have that feature. The use case: ``` In [2]: o = OrderedDict([(1, 2), (2, 3), (3, 4)]) In [3]: o.index[0] Out[3]: 1 In [4]: o.index[-1] Out[4]: 3 ``` A little benchmarking put it at half the speed of collections.OrderedDict. Here's the recipe: ``` from itertools import count from collections import MutableMapping from sortedcontainers import SortedDict class OrderedDictIndex(object): def __init__(self, nums): self._nums = nums def __len__(self): return len(self._nums) def __getitem__(self, index): num = self._nums.iloc[index] return self._nums[num] class OrderedDict(MutableMapping): def __init__(self, *args, **kwargs): self._dict = {} self._keys = {} self._nums = SortedDict() self._count = count() self.index = OrderedDictIndex(self._nums) self.update(*args, **kwargs) def __getitem__(self, key): return self._dict[key] def __setitem__(self, key, value): if key not in self._dict: num = next(self._count) self._keys[key] = num self._nums[num] = key self._dict[key] = value def __delitem__(self, key): del self._dict[key] num = self._keys.pop(key) del self._nums[num] def __len__(self): return len(self._dict) def __iter__(self): return self._nums.itervalues() ```
On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing?
Don't forget that, as the docs describe, an "OrderedDict is a dict that remembers the order that keys were first inserted". While obviously there's an implicit sequence for that order, the focus is still on dict-ness with the sequence exposed through the normal mapping approach (iteration). If you want to get sequence semantics then first unpack the order into a sequence type like list or tuple. Or use some other type than OrderedDict. Note that OrderedDict's view types are essentially just dict's view types with custom iteration. Adding indexing to the views would complicate things and certainly would not be O(1) like you would expect indexing to be. -eric
You can do indexing, insertion, and removal all in logarithmic time (which is basically constant) by using a B-tree as the underlying data structure. (See e.g. the blist package.) On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <ericsnowcurrently@gmail.com> wrote:
On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict ( http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing?
Don't forget that, as the docs describe, an "OrderedDict is a dict that remembers the order that keys were first inserted". While obviously there's an implicit sequence for that order, the focus is still on dict-ness with the sequence exposed through the normal mapping approach (iteration). If you want to get sequence semantics then first unpack the order into a sequence type like list or tuple. Or use some other type than OrderedDict.
Note that OrderedDict's view types are essentially just dict's view types with custom iteration. Adding indexing to the views would complicate things and certainly would not be O(1) like you would expect indexing to be.
-eric
On Jul 6, 2015, at 15:04, Neil Girdhar <mistersheik@gmail.com> wrote:
You can do indexing, insertion, and removal all in logarithmic time (which is basically constant)
If you're dealing with dicts of, say, millions of items, then it's "basically constant" with a multiplier of 6-20x worse than the current implementation, and only as long as you never need to scale larger (which is a pretty major concern if you're writing a general-purpose library or something). That's not the same thing as actually constant. There's a reason all the scripting languages have hash-based containers, and that the systems languages that started off with only tree-based containers later added hash-based containers as well. Personally, I think it would be great if Python had tree-based sorted containers alongside the existing hash-based arbitrary-ordered ones. Then it would be trivial to add a tree-based insertion-order container to replace the hash-based insertion-order container when it's more appropriate to a specific use (e.g., when you need to efficiently random-access-index it). But, unless you're doing government work or something else that has no access to PyPI, that's already true today, so there's not much to wish for.
by using a B-tree as the underlying data structure. (See e.g. the blist package.)
On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <ericsnowcurrently@gmail.com> wrote: On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing?
Don't forget that, as the docs describe, an "OrderedDict is a dict that remembers the order that keys were first inserted". While obviously there's an implicit sequence for that order, the focus is still on dict-ness with the sequence exposed through the normal mapping approach (iteration). If you want to get sequence semantics then first unpack the order into a sequence type like list or tuple. Or use some other type than OrderedDict.
Note that OrderedDict's view types are essentially just dict's view types with custom iteration. Adding indexing to the views would complicate things and certainly would not be O(1) like you would expect indexing to be.
-eric
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
This thread is not about hash tables. This thread is about indexing into an ordered dictionary when you need an ordered dictionary. Someone pointed out that people expect indexing to be constant time. I agree that no one expects indexing to be linear time. My point was that logarithmic-time indexing is reasonable and possible. On Tue, Jul 7, 2015 at 12:15 AM, Andrew Barnert <abarnert@yahoo.com> wrote:
On Jul 6, 2015, at 15:04, Neil Girdhar <mistersheik@gmail.com> wrote:
You can do indexing, insertion, and removal all in logarithmic time (which is basically constant)
If you're dealing with dicts of, say, millions of items, then it's "basically constant" with a multiplier of 6-20x worse than the current implementation, and only as long as you never need to scale larger (which is a pretty major concern if you're writing a general-purpose library or something). That's not the same thing as actually constant. There's a reason all the scripting languages have hash-based containers, and that the systems languages that started off with only tree-based containers later added hash-based containers as well.
Personally, I think it would be great if Python had tree-based sorted containers alongside the existing hash-based arbitrary-ordered ones. Then it would be trivial to add a tree-based insertion-order container to replace the hash-based insertion-order container when it's more appropriate to a specific use (e.g., when you need to efficiently random-access-index it). But, unless you're doing government work or something else that has no access to PyPI, that's already true today, so there's not much to wish for.
by using a B-tree as the underlying data structure. (See e.g. the blist package.)
On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <ericsnowcurrently@gmail.com> wrote:
On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict ( http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing?
Don't forget that, as the docs describe, an "OrderedDict is a dict that remembers the order that keys were first inserted". While obviously there's an implicit sequence for that order, the focus is still on dict-ness with the sequence exposed through the normal mapping approach (iteration). If you want to get sequence semantics then first unpack the order into a sequence type like list or tuple. Or use some other type than OrderedDict.
Note that OrderedDict's view types are essentially just dict's view types with custom iteration. Adding indexing to the views would complicate things and certainly would not be O(1) like you would expect indexing to be.
-eric
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
I didn't even mean for this thread to be about arbitrarily indexing into an OrderedDict. I meant for it to be about accessing the first and last items in an OrderedDict. Given that a method already exists to access and remove these items, I find it hard to understand why there isn't a method to simply access them. This should be a constant-time operation if OrderedDict employs a doubly-linked list under the hood. -Kale On 07/06/2015 09:23 PM, Neil Girdhar wrote:
This thread is not about hash tables. This thread is about indexing into an ordered dictionary when you need an ordered dictionary. Someone pointed out that people expect indexing to be constant time. I agree that no one expects indexing to be linear time. My point was that logarithmic-time indexing is reasonable and possible.
What's wrong with "next(iter(o))" and "next(reversed(o))"? On Tue, Jul 7, 2015 at 2:56 AM, Kale Kundert <kale@thekunderts.net> wrote:
I didn't even mean for this thread to be about arbitrarily indexing into an OrderedDict. I meant for it to be about accessing the first and last items in an OrderedDict. Given that a method already exists to access and remove these items, I find it hard to understand why there isn't a method to simply access them. This should be a constant-time operation if OrderedDict employs a doubly-linked list under the hood.
-Kale
On 07/06/2015 09:23 PM, Neil Girdhar wrote:
This thread is not about hash tables. This thread is about indexing into an ordered dictionary when you need an ordered dictionary. Someone pointed out that people expect indexing to be constant time. I agree that no one expects indexing to be linear time. My point was that logarithmic-time indexing is reasonable and possible.
Three things: 1. Someone who is not all that familiar with python would never think to do either of those things. I've been using python for years and it didn't occur to me that I could peek at the ends of an OrderedDict like that until I saw someone on stack overflow suggest it. 2. Furthermore, if you don't have a good understanding of iterators in python, you could be excused for thinking that 'next(reversed(o))' creates a temporary list and is O(n) in time and memory. Those expressions read like they're doing a lot more work than they actually are, and that's confusing. 3. Readability counts, and those expressions hide the intent of the programmer. You wouldn't use 'next(iter(o))' to access the first element of a list, because that would be confusing and obfuscated. On 07/06/2015 11:59 PM, Neil Girdhar wrote:
What's wrong with "next(iter(o))" and "next(reversed(o))"?
On Tue, Jul 7, 2015 at 2:56 AM, Kale Kundert <kale@thekunderts.net <mailto:kale@thekunderts.net>> wrote:
I didn't even mean for this thread to be about arbitrarily indexing into an OrderedDict. I meant for it to be about accessing the first and last items in an OrderedDict. Given that a method already exists to access and remove these items, I find it hard to understand why there isn't a method to simply access them. This should be a constant-time operation if OrderedDict employs a doubly-linked list under the hood.
-Kale
On 07/06/2015 09:23 PM, Neil Girdhar wrote: > This thread is not about hash tables. This thread is about indexing into an > ordered dictionary when you need an ordered dictionary. Someone pointed out > that people expect indexing to be constant time. I agree that no one expects > indexing to be linear time. My point was that logarithmic-time indexing is > reasonable and possible.
Good points. I will do my best to address them: 3. The reason I like "next(iter(" and "reversed(iter", which is also probably the reason the discussion drifted into indexing is that right after someone asks for peek, someone else asks for peek_next and so on. If you're unhappy with logarithmic indexing time as you suggested, then the best you can do is linear time with respect to peek depth. That is just iteration. The most readable way to express one step of iteration is to call next on an iterator. The most readable way to produce an iterator from an iterable is with iter or reversed. 1/2. If you don't have a good understanding of Python, I think that that is something that should be remedied by learning about Python? There should ideally be one way of doing things after all. Maybe the documentation could be extended with a mention of how to peek? I don't know. But I disagree with adding peek to OrderedDict for the same reason that I disagree with adding peek to list and to heapq (as "heapq.peek(h)"). Best, Neil On Tue, Jul 7, 2015 at 3:59 AM, Kale Kundert <kale@thekunderts.net> wrote:
Three things:
1. Someone who is not all that familiar with python would never think to do either of those things. I've been using python for years and it didn't occur to me that I could peek at the ends of an OrderedDict like that until I saw someone on stack overflow suggest it.
2. Furthermore, if you don't have a good understanding of iterators in python, you could be excused for thinking that 'next(reversed(o))' creates a temporary list and is O(n) in time and memory. Those expressions read like they're doing a lot more work than they actually are, and that's confusing.
3. Readability counts, and those expressions hide the intent of the programmer. You wouldn't use 'next(iter(o))' to access the first element of a list, because that would be confusing and obfuscated.
What's wrong with "next(iter(o))" and "next(reversed(o))"?
On Tue, Jul 7, 2015 at 2:56 AM, Kale Kundert <kale@thekunderts.net <mailto:kale@thekunderts.net>> wrote:
I didn't even mean for this thread to be about arbitrarily indexing into an OrderedDict. I meant for it to be about accessing the first and last items in an OrderedDict. Given that a method already exists to access and remove these items, I find it hard to understand why there isn't a method to simply access them. This should be a constant-time operation if OrderedDict employs a doubly-linked list under the hood.
-Kale
On 07/06/2015 09:23 PM, Neil Girdhar wrote: > This thread is not about hash tables. This thread is about indexing into an > ordered dictionary when you need an ordered dictionary. Someone
On 07/06/2015 11:59 PM, Neil Girdhar wrote: pointed out
> that people expect indexing to be constant time. I agree that no
one expects
> indexing to be linear time. My point was that logarithmic-time
indexing is
> reasonable and possible.
On Tue, Jul 07, 2015 at 12:59:07AM -0700, Kale Kundert wrote:
On 07/06/2015 11:59 PM, Neil Girdhar wrote:
What's wrong with "next(iter(o))" and "next(reversed(o))"?
Three things:
1. Someone who is not all that familiar with python would never think to do either of those things. I've been using python for years and it didn't occur to me that I could peek at the ends of an OrderedDict like that until I saw someone on stack overflow suggest it.
2. Furthermore, if you don't have a good understanding of iterators in python, you could be excused for thinking that 'next(reversed(o))' creates a temporary list and is O(n) in time and memory. Those expressions read like they're doing a lot more work than they actually are, and that's confusing.
Do we know that OrderedDict.__reversed__ *doesn't* do that? I assume it won't, but I'm not sure it's a guarantee.
3. Readability counts, and those expressions hide the intent of the programmer. You wouldn't use 'next(iter(o))' to access the first element of a list, because that would be confusing and obfuscated.
I agree with all of those objections, especially the third. Which is why the reasonable and simple solution is to write: def first(od): return next(iter(od)) def last(od): return next(reversed(od)) then call first(o), last(o). Add comments, documentation and tests to taste. Or subclass OrderedDict and add first() last() methods. I am unconvinced that peeking at the first and last items of a dict (ordered, sorted or otherwise), let alone O(1) indexed access to items, is a good fit for the OrderedDict API. If I were the OD maintainer, I would want to understand your use-case (why are you using an OD as a queue, instead of a list, deque, or queue?), and possibly hear two or three additional uses, before agreeing to add it to the API. -- Steve
On 07/07/2015 13:34, Steven D'Aprano wrote:
I am unconvinced that peeking at the first and last items of a dict (ordered, sorted or otherwise), let alone O(1) indexed access to items, is a good fit for the OrderedDict API. If I were the OD maintainer, I would want to understand your use-case (why are you using an OD as a queue, instead of a list, deque, or queue?), and possibly hear two or three additional uses, before agreeing to add it to the API.
That's not what the original message said:- <quote> Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. </quote> I've no idea what the use case is for managing a LIFO queue with anything. Only the OP can tell us what he's trying to achieve, so over to you Kale :) -- My fellow Pythonistas, ask not what our language can do for you, ask what you can do for our language. Mark Lawrence
On Tue, 7 Jul 2015 at 13:34 Steven D'Aprano <steve@pearwood.info> wrote:
On Tue, Jul 07, 2015 at 12:59:07AM -0700, Kale Kundert wrote:
3. Readability counts, and those expressions hide the intent of the programmer. You wouldn't use 'next(iter(o))' to access the first element of a list, because that would be confusing and obfuscated.
I agree with all of those objections, especially the third. Which is why the reasonable and simple solution is to write:
def first(od): return next(iter(od))
def last(od): return next(reversed(od))
then call first(o), last(o). Add comments, documentation and tests to taste. Or subclass OrderedDict and add first() last() methods.
If the OrderedDict is empty both of the above will raise StopIteration. This can have unintended consequences if the OrderedDict is called from another iterator/generator etc. So it should probably be: def first(od): try: return next(iter(od)) except StopIteration: raise KeyError
I am unconvinced that peeking at the first and last items of a dict (ordered, sorted or otherwise), let alone O(1) indexed access to items, is a good fit for the OrderedDict API. If I were the OD maintainer, I would want to understand your use-case (why are you using an OD as a queue, instead of a list, deque, or queue?), and possibly hear two or three additional uses, before agreeing to add it to the API.
I once wanted to be able to peek the last item. My usecase was something to do with traversing a graph. Perhaps a depth-first search where I wanted a stack of the vertices I was traversing and an efficient way to check for a vertex in the stack (to avoid traversing cycles). I think the keys were the vertices and the values were iterators over the neighbours of the corresponding vertices. After traversing all neighbours of a vertex I want to pop that vertex off and continue traversing the vertex preceding it on the stack. I can retrieve the vertex from the top of the stack with popitem. However I want the returned vertex to remain in the stack while traversing its other neighbours so I pop it off and then push it back on again akin to: def peekitem(od): key, val = od.popitem() od[key] = val return key, val -- Oscar
On Wed, Jul 8, 2015 at 12:35 AM, Oscar Benjamin <oscar.j.benjamin@gmail.com> wrote:
If the OrderedDict is empty both of the above will raise StopIteration. This can have unintended consequences if the OrderedDict is called from another iterator/generator etc. So it should probably be:
def first(od): try: return next(iter(od)) except StopIteration: raise KeyError
Agreed, though it's worth noting that as of Python 3.5, generators can be made not-vulnerable to this problem (and as of 3.7ish, they automatically will be protected). See PEP 479 for details. But yes, turning that into KeyError is the right thing to do, and is exactly why something like this wants to be a published recipe rather than simply dismissed as "see how easy it is?". Does it belong in a collection like moreitertools? ChrisA
On Wed, Jul 8, 2015 at 12:58 AM, Chris Angelico <rosuav@gmail.com> wrote:
On Wed, Jul 8, 2015 at 12:35 AM, Oscar Benjamin <oscar.j.benjamin@gmail.com> wrote:
If the OrderedDict is empty both of the above will raise StopIteration. This can have unintended consequences if the OrderedDict is called from another iterator/generator etc. So it should probably be:
def first(od): try: return next(iter(od)) except StopIteration: raise KeyError
Agreed, though it's worth noting that as of Python 3.5, generators can be made not-vulnerable to this problem (and as of 3.7ish, they automatically will be protected). See PEP 479 for details. But yes, turning that into KeyError is the right thing to do, and is exactly why something like this wants to be a published recipe rather than simply dismissed as "see how easy it is?".
Does it belong in a collection like moreitertools?
ChrisA
Doh. Next time, Chris, look first, *then* post. https://github.com/erikrose/more-itertools/blob/master/more_itertools/more.p... ChrisA
On 2015-07-07, at 06:23 , Neil Girdhar <mistersheik@gmail.com> wrote:
This thread is not about hash tables. This thread is about indexing into an ordered dictionary when you need an ordered dictionary. Someone pointed out that people expect indexing to be constant time. I agree that no one expects indexing to be linear time. My point was that logarithmic-time indexing is reasonable and possible.
Linear time indexing would be possible by changing the OrderedDict implementation to Raymond Hettinger's compact dictionaries[0] with a delete operation recompacting the entries array rather than just nulling the item (it would make removals on "early" keys of large dictionaries more expensive though, delete would become O(n) with n the number of "living" entries added after the one being removed). [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html
Yeah, but logarithmic time everything should be good enough for nearly all problems. After years of programming competitions, one thing I remember is how hard it is to craft a problem such that a linear solution is accepted, but a linearithmic one is not. On Tue, Jul 7, 2015 at 4:33 AM, Masklinn <masklinn@masklinn.net> wrote:
On 2015-07-07, at 06:23 , Neil Girdhar <mistersheik@gmail.com> wrote:
This thread is not about hash tables. This thread is about indexing into an ordered dictionary when you need an ordered dictionary. Someone pointed out that people expect indexing to be constant time. I agree that no one expects indexing to be linear time. My point was that logarithmic-time indexing is reasonable and possible.
Linear time indexing would be possible by changing the OrderedDict implementation to Raymond Hettinger's compact dictionaries[0] with a delete operation recompacting the entries array rather than just nulling the item (it would make removals on "early" keys of large dictionaries more expensive though, delete would become O(n) with n the number of "living" entries added after the one being removed).
[0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
--
--- You received this message because you are subscribed to a topic in the Google Groups "python-ideas" group. To unsubscribe from this topic, visit https://groups.google.com/d/topic/python-ideas/gDc4Ez6Z4MQ/unsubscribe. To unsubscribe from this group and all its topics, send an email to python-ideas+unsubscribe@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
On Jul 6, 2015, at 14:30, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing.
Only by having a special view, accessed as .index. If it just took indices as subscripts, that would be ambiguous with integer keys.
Can OrderedDict do the same thing?
It's worth noting that most of the various different sorted containers on PyPI support something equivalent, but all with different interfaces. More importantly, they all use logarithmic data structures (binary trees, b-trees, skip lists, the hybrid thing blist uses, ...), which give you O(log N) indexing, and some of them can do even better by giving you O(log N) to find a slice and O(1) within that slice; OrderedDict uses a linked list, so it would be O(N).
On Monday, July 6, 2015 at 10:49:44 AM UTC-4, Kale Kundert wrote: Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
My proposal is to add a peekitem() method to OrderedDict. This method would have the same signature and would return the same thing as popitem(), it just wouldn't modify the data structure.
-Kale
P.S. There is already a way to peek at the last item an OrderedDict, but it hides the intent of the code and you wouldn't think of it if you weren't familiar with python: next(reversed(ordered_dict))
_______________________________________________ Python-ideas mailing list Python...@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
On Tue, Jul 7, 2015 at 12:08 AM, Andrew Barnert <abarnert@yahoo.com> wrote:
On Jul 6, 2015, at 14:30, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict ( http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing.
Only by having a special view, accessed as .index. If it just took indices as subscripts, that would be ambiguous with integer keys.
Can OrderedDict do the same thing?
It's worth noting that most of the various different sorted containers on PyPI support something equivalent, but all with different interfaces.
2015 might not be the right year to add sorted containers to Python. However, it might be a good idea to standardize the interface of a "sorted map" and "sorted set" in a PEP.
More importantly, they all use logarithmic data structures (binary trees, b-trees, skip lists, the hybrid thing blist uses, ...), which give you O(log N) indexing, and some of them can do even better by giving you O(log N) to find a slice and O(1) within that slice; OrderedDict uses a linked list, so it would be O(N).
On Monday, July 6, 2015 at 10:49:44 AM UTC-4, Kale Kundert wrote:
Today I was trying to use collections.OrderedDict to manage a LIFO queue, and I was surprised to realize that OrderedDict doesn't provide a way to look at its first or last item. There is an OrderedDict.popitem() method, which removes and returns either the first or last item, but it's not hard to imagine cases where you would want to see what's on the queue without popping it right away.
My proposal is to add a peekitem() method to OrderedDict. This method would have the same signature and would return the same thing as popitem(), it just wouldn't modify the data structure.
-Kale
P.S. There is already a way to peek at the last item an OrderedDict, but it hides the intent of the code and you wouldn't think of it if you weren't familiar with python: next(reversed(ordered_dict))
_______________________________________________ Python-ideas mailing list Python...@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
_______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
On Jul 6, 2015, at 21:27, Neil Girdhar <mistersheik@gmail.com> wrote:
On Tue, Jul 7, 2015 at 12:08 AM, Andrew Barnert <abarnert@yahoo.com> wrote:
On Jul 6, 2015, at 14:30, Neil Girdhar <mistersheik@gmail.com> wrote:
SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing.
Only by having a special view, accessed as .index. If it just took indices as subscripts, that would be ambiguous with integer keys.
Can OrderedDict do the same thing?
It's worth noting that most of the various different sorted containers on PyPI support something equivalent, but all with different interfaces.
2015 might not be the right year to add sorted containers to Python. However, it might be a good idea to standardize the interface of a "sorted map" and "sorted set" in a PEP.
I suggested that before, but apparently 2013 was not the right time to suggest standardizing the interface without adding an implementation to the stdlib; maybe things are different enough in 2015. Thanks for raising the idea. I'll go back and try to dig up other past proposals and re-survey the different options to see if that seems plausible, and meanwhile I'll stop derailing this thread with it. :)
participants (12)
-
Andrew Barnert -
Chris Angelico -
Eric Snow -
Grant Jenks -
Kale Kundert -
Mark Lawrence -
Masklinn -
Neil Girdhar -
Oscar Benjamin -
Paul Sokolovsky -
Steven D'Aprano -
Todd