Sorry to pipe in so late, but this is actually the default behaviour of
my C implementation (which I call KIO (Key Insertion Order), there is an
option to change this to KVIO (Key (or) Value Insertion Order), which
moves the pair to the end.
Anthon
Armin Ronacher wrote:
Steven D'Aprano steve at
It is possible to get both ordered dict and sorted dict semantics in
the same type if you replace (key, value) pairs for dictionary entries
with (key,value,order) triples. The third component is a value that
indicates the place of the entry relative to the other entries. To get
an ordered dict,
Armin Ronacher armin.ronacher at active-4.com writes:
There are far more responses for that topic than I imagined so I would love
to write a PEP about that topic, incorporating the ideas/questions and
suggestions discussed here.
There is now a PEP for the ordered dict:
- PEP:
Armin Ronacher wrote:
Armin Ronacher armin.ronacher at active-4.com writes:
There are far more responses for that topic than I imagined so I would love
to write a PEP about that topic, incorporating the ideas/questions and
suggestions discussed here.
There is now a PEP for the ordered dict:
[EMAIL PROTECTED] writes:
It is possible to get both ordered dict and sorted dict semantics in
the same type if you replace (key, value) pairs for dictionary entries
with (key,value,order) triples.
Roundup uses something like this concept for its value choice menus.
I don't actually think
Raymond Hettinger python at rcn.com writes:
For an insertion order dictionary, there was also a question about
how to handle duplicate keys.
Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items()
return?
[(k1,v3), (k2,v2)]
[(k2,v2), (k1,v3)]
All the ordered dict
In data 15 giugno 2008 alle ore 07:43:32, Raymond Hettinger [EMAIL PROTECTED]
ha scritto:
For an insertion order dictionary, there was also a question about
how to handle duplicate keys.
Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items()
return?
[(k1,v3), (k2,v2)]
On Jun 14, 4:39 pm, Armin Ronacher [EMAIL PROTECTED]
wrote:
- in XML/HTML processing it's often desired to keep the attributes of
an tag ordered during processing. So that input ordering is the
same as the output ordering.
Munging XML is a niche.
- Form data transmitted via
From: Cesare Di Mauro [EMAIL PROTECTED]
The same problem happens with dictionary updates:
d = {}
d[k1] = v1
d[k2] = v2
d[k1] = v3
The last instruction just replaces the existing entry, so I'm +0 for the first
result.
There's a difference. With dicts, the third insertion *replaces* the
I compared multiple ordered dicts now (including Babel, Django and the
C-implementation I mentioned earlier) and implemented a python version
of the ordered dict as reference implementation:
http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py
I find the slicing API surprising. IMO, if
Armin Ronacher wrote:
That's true, but by now there are countless of ordered dict
implementations with a mostly-compatible interface and applications and
libraries are using them already.
Even worse, most of them are slow, i.e. show a wrong algorithmic
complexity ...
I have an example
Raymond Hettinger wrote:
I don't favor one over the other. Am just pointing-out that the
proposal is a little more complex than simply wishing for an ordered
verion of a dictionary and expecting that that wish is self-defining in
a way the matches everyone's intuition, use cases, and
[EMAIL PROTECTED] wrote:
-1 for ordered dict
+1 for sorted dict
Build the ordered dict, then sort it in-place afterwards, just like a
list (alternatively, build a normal dict then feed sorted(orig.items())
to the ordered dict constructor).
The point of an ordered dict is that unlike a
On Sun, 15 Jun 2008 02:59:51 pm David Wolever wrote:
And, as far as questions about the definition of an ordered
dictionary, is there any good reason not to simply treat the dict as
a list? Something like (with the obvious bits left out):
Yes.
(1) If you implement the ordered dict as a
On Sun, 2008-06-15 at 00:12 -0700, Raymond Hettinger wrote:
From: Cesare Di Mauro [EMAIL PROTECTED]
The same problem happens with dictionary updates:
d = {}
d[k1] = v1
d[k2] = v2
d[k1] = v3
The last instruction just replaces the existing entry, so I'm +0 for the
first result.
... like your implementation. It is not too hard to get the delitem
O(log n) compared to your O(n), see here:
http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py
So many people are implementing this kind of data type but do not really
care about making as fast as it could be
On Sun, 15 Jun 2008 06:42:32 pm laurent wrote:
An other way to think of such a structure would be as a list, for
which each item would also have an associated key.
I think someone mentioned the link with a list during this thread,
but here I am not referring to implementation, but the feature
* Guido van Rossum wrote:
On Sat, Jun 14, 2008 at 4:57 PM, André Malo [EMAIL PROTECTED] wrote:
* Armin Ronacher wrote:
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes
of an tag ordered during processing. So that
Steven D'Aprano steve at pearwood.info writes:
Conceptually, I would expect the following behaviour:
od = odict()
od[1] = 'spam' # insert a new key
od[2] = 'parrot' # insert a new key
od[1] = 'ham' # modify existing key
od.items()
[(1, 'ham'), (2, 'parrot')]
That behavior is
Hi,
Alexander Schremmer 2008a at usenet.alexanderweb.de writes:
Even worse, most of them are slow, i.e. show a wrong algorithmic
complexity ...
I already said that in the initial post.
I have an example implementation here that incorporates the ideas
from ordereddict, Django's OrderedDict
There are far more responses for that topic than I imagined so I would love
to write a PEP about that topic, incorporating the ideas/questions and
suggestions discussed here.
Regards,
Armin
___
Python-Dev mailing list
Python-Dev@python.org
Martin v. Löwis martin at v.loewis.de writes:
I compared multiple ordered dicts now (including Babel, Django and the
C-implementation I mentioned earlier) and implemented a python version
of the ordered dict as reference implementation:
From: Armin Ronacher [EMAIL PROTECTED]
There are far more responses for that topic than I imagined so I would love
to write a PEP about that topic, incorporating the ideas/questions and
suggestions discussed here.
Instead of going straight to a PEP, I recommend opening a new wiki page
on the
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
On Jun 15, 2008, at 1:43 AM, Raymond Hettinger wrote:
For an insertion order dictionary, there was also a question about
how to handle duplicate keys.
Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the
odict.items() return?
[(k1,v3),
Armin Ronacher wrote:
- in XML/HTML processing it's often desired to keep the attributes of
an tag ordered during processing. So that input ordering is the
same as the output ordering.
- [...]
XML libraries such as etree could add support for it when creating
elements
dbpokorny at gmail.com dbpokorny at gmail.com writes:
If you don't like the fact that your web application framework loses
the order of its key:value pairs relative to the page, then you should
bring it up with the developers.
Who will then point up that to retain that order while providing
At 02:19 PM 6/15/2008 +, Antoine Pitrou wrote:
Ordered dicts, dicts that remember the chronological order of their
insertion, don't sound generally useful.
They are generally useful in any case where you want to handle key-value
pairs while not confusing a human operator by messing up the
Phillip J. Eby pje at telecommunity.com writes:
As for the other uses for ordered dictionaries, I find it simplest to
just use a list of key,value pairs, and only transform it to a
dictionary or dictionary-like structure as needed, using tools like
the cgi module, the email package, or
At 02:34 PM 6/15/2008 +, Antoine Pitrou wrote:
Phillip J. Eby pje at telecommunity.com writes:
As for the other uses for ordered dictionaries, I find it simplest to
just use a list of key,value pairs, and only transform it to a
dictionary or dictionary-like structure as needed, using
On Sun, Jun 15, 2008 at 6:01 AM, Barry Warsaw [EMAIL PROTECTED] wrote:
On Jun 15, 2008, at 1:43 AM, Raymond Hettinger wrote:
The second one is a bit weird because a key loses its place whenever
the value is updated.
Heh, neither of these would work for the email package's own flavor of
2008/6/15 Raymond Hettinger [EMAIL PROTECTED]:
From: Armin Ronacher [EMAIL PROTECTED]
There are far more responses for that topic than I imagined so I would
love
to write a PEP about that topic, incorporating the ideas/questions and
suggestions discussed here.
Instead of going straight to
On Sun, Jun 15, 2008 at 1:03 AM, Nick Coghlan [EMAIL PROTECTED] wrote:
Raymond Hettinger wrote:
I don't favor one over the other. Am just pointing-out that the proposal
is a little more complex than simply wishing for an ordered verion of a
dictionary and expecting that that wish is
On Jun 14, 2008, at 8:26 PM, Guido van Rossum wrote:
No, but an ordered dict happens to be a *very* common thing to need,
for a variety of reasons. So I'm +0.5 on adding this to the
collections module. However someone needs to contribute working code.
Here's an LRU cache that I've used a few
On Jun 15, 2008, at 12:20 PM, zooko wrote:
So, it would be easy to change those two behaviors in order to use
this implementation. There are actually three implementations in
that file: one that is asymptotically O(1) for all operations
(using a double-linked list woven into the values of
On Sun, 15 Jun 2008 07:39:05 pm Armin Ronacher wrote:
Steven D'Aprano steve at pearwood.info writes:
Conceptually, I would expect the following behaviour:
od = odict()
od[1] = 'spam' # insert a new key
od[2] = 'parrot' # insert a new key
od[1] = 'ham' # modify existing key
Talin wrote:
In some cases, the term is used to mean a
dictionary that remembers the order of insertions, and in other cases it
is used to mean a sorted dict,
I would be more in favor of the idea if we could come up with a less
ambiguous naming scheme.
Perhaps indexed list or maybe keyed
But my point is that we we need to focus on finding real use cases and
exploring how best to solve them. Otherwise we might as well throw in
my OrderedSet[1] as-is, despite that it's got no comments and no
ratings. Even I don't seem to use it.
I'm mostly lurking on these threads, so as to
Armin Ronacher wrote:
Hi,
I noticed lately that quite a few projects are implementing their own
subclasses of `dict` that retain the order of the key/value pairs.
However half of the implementations I came across are not implementing
the whole dict interface which leads to weird bugs, also the
* Armin Ronacher wrote:
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes of
an tag ordered during processing. So that input ordering is the
same as the output ordering.
- Form data transmitted via HTTP is
Hi,
Armin Ronacher armin.ronacher at active-4.com writes:
To fight that problem I want to proposed a new class in collections
called odict which is a dict that keeps the items sorted, similar to
a PHP array.
I'm also +1 on this. I've used the implementation you mentioned in a compiler
On Sat, Jun 14, 2008 at 4:57 PM, André Malo [EMAIL PROTECTED] wrote:
* Armin Ronacher wrote:
Some reasons why ordered dicts are a useful feature:
- in XML/HTML processing it's often desired to keep the attributes of
an tag ordered during processing. So that input ordering is the
Michael Foord wrote:
Armin Ronacher wrote:
Hi,
I noticed lately that quite a few projects are implementing their own
subclasses of `dict` that retain the order of the key/value pairs.
However half of the implementations I came across are not implementing
the whole dict interface which leads to
On Sat, Jun 14, 2008 at 11:39 PM, Armin Ronacher
[EMAIL PROTECTED] wrote:
Some reasons why ordered dicts are a useful feature:
And for metaclasses or for LRU caches or for removing duplicates in a
list while maintaining order. I think that the name ordereddict would
be more readable though, and
2008/6/14 Talin [EMAIL PROTECTED]:
There's been a lot of controversy/confusion about ordered dicts. One of the
sources of confusion is that people mean different things when they use the
term ordered dict: In some cases, the term is used to mean a dictionary
that remembers the order of
Talin wrote:
Michael Foord wrote:
Armin Ronacher wrote:
Hi,
I noticed lately that quite a few projects are implementing their own
subclasses of `dict` that retain the order of the key/value pairs.
However half of the implementations I came across are not implementing
the whole dict interface
Guido van Rossum guido at python.org writes:
On Sat, Jun 14, 2008 at 4:57 PM, André Malo nd at perlig.de wrote:
I find this collection of cases pretty weak as an argument for implementing
that in the stdlib. A lot of special purpose types would fit into such
reasoning, but do you want to
BJörn Lindqvist bjourne at gmail.com writes:
I think that the name ordereddict would be more readable though, and
match the existing defaultdict class in the collections module.
While I agree that ordered makes more sense, it's pretty stupid to type
with two 'd's right after another.
Regards,
From: Talin [EMAIL PROTECTED]
There's been a lot of controversy/confusion about ordered dicts.
I think that is why all earlier proposals all died.
One of
the sources of confusion is that people mean different things when they
use the term ordered dict: In some cases, the term is used to
Hasan Diwan hasan.diwan at gmail.com writes:
2008/6/14 Talin talin at acm.org:
There's been a lot of controversy/confusion about ordered dicts. One of the
sources of confusion is that people mean different things when they use the
term ordered dict: In some cases, the term is used to
On 14-Jun-08, at 8:39 PM, Armin Ronacher wrote:
...
I noticed lately that quite a few projects are implementing their own
subclasses of `dict` that retain the order of the key/value pairs.
...
I'm +1 on this one too, as there are at least a couple of times in
recent memory when I would have
50 matches
Mail list logo