This is probably a FAQ, but I dare to ask it nevertheless since I
haven't found a satisfying answer yet: Why isn't there an "ordered
dictionary" class at least in the standard list? Time and again I am
missing that feature. Maybe there is something wrong with my programming
style, but I rather think it is generally useful.
I fully agree with the following posting where somebody complains why so
very basic and useful things are not part of the standard library: http://groups.google.com/group/comp....52d2f771a49857
Are there plans to get it into the standard lib sometime?
-- Christoph
Nov 22 '05
210  10534 
Fuzzyman schrieb: Of course ours is ordered *and* orderable ! You can explicitly alter
the sequence attribute to change the ordering.
What I actually wanted to say is that there may be a confusion between a
"sorted dictionary" (one where the keys are automatically sorted) and an
"ordered dictionary" (where the keys are not automatically ordered, but
have a certain order that is preserved). Those who suggested that the
"sorted" function would be helpful probably thought of a "sorted
dictionary" rather than an "ordered dictionary."
-- Christoph
Bengt Richter wrote: After finally reading that the odict.py in PyPI by Larosa/Foord was what was desired,
but slower in use than what Fredrik posted, I decided to see if I could speed up odict.py.
I now have a version that I think may be generally faster.
Hm, I wouldn't formulate it that way that I want the odict of
Larosa/Foord, but I want "the one" "obvious" odict for which
Larosa/Foord have already made one implementatin ;-)
Others are here:
http://aspn.activestate.com/ASPN/Coo.../Recipe/438823
http://aspn.activestate.com/ASPN/Coo.../Recipe/107747
http://pleac.sourceforge.net/pleac_p...es.html#AEN250
It is all essentially the same idea I think (though after having a
closer look I see implementation shortcomings in all of them).
I now have a version that I think may be generally faster.
Great. I also wanted to do that. Also, I would like to add some
functionality to Larosa/Foord's odict, like creating or updating an
odict from an ordinary dict (keys taken over from the ordinary dict will
be either in random order or automatically sorted). An ordered
dictionary should also have methods for sorting (like PHP's ksort()).
This way, you could initialize an ordered dict from an ordinary dict,
sort it, and from then on never care to call keys().sorted() or
something when iterating over the dictionary. Probably there are other
methods from lists that could be taken over to ordered dicts.
-- Christoph
>>def __init__(self, init_val = ()): dict.__init__(s elf, init_val)
self.sequence = [x[0] for x in init_val]
Fuzzyman wrote:
But that doesn't allow you to create an ordered dict from another
ordered dict.
Right; I did not want to present a full implementation, just the
relevant part. Of course, a real implementation should also allow to
build an ordered dict from another ordered dict or an ordinary dict. (In
the latter case, maybe the keys should be automatically sorted.) But one
or two case disctinctions would not make things mentionable slower.
-- Christoph
On Tue, 2005-11-22 at 13:37, Christoph Zwerschke wrote: Would the default semantics below really be that suprising?
"An ordered dictionary remembers the order in which keys are first seen
[...] Overwriting an entry replaces
its value, but does not affect its position in the key order. Removing
an entry (using 'del') _does_ remove it from the key order. Accordingly,
if the entry is later recreated, it will then occur last in the key
order. [...]"
I can't help but I still find it unambiguous and intuitive enough to
consider it "the one" standard implementation for ordered dictionaries.
I don't think it's intuitive if you can't describe it without
contradicting yourself. If the order of the keys really were the order
in which they were first seen by the dictionary, deleting and recreating
a key should maintain its original position.
-Carsten
Bengt Richter wrote: On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke <ci**@online.de > wrote:
Fredrik Lundh wrote: if you restructure the list somewhat
d = (
('pid', ('Employee ID', 'int')),
('name', ('Employee name', 'varchar')),
('sal', ('Salary', 'float'))
)
you can still loop over the list
...
but you can easily generate an index when you need it:
index = dict(d)
That's exactly the kind of things I find myself doing too often and what
I was talking about: You are using *two* pretty redundant data
structures, a dictionary and a list/tuple to describe the same thing.
Ok, you can use a trick to automatically create the dictionary from the
tuple, but still it feels somewhat "unnatural" for me. A "ordered
dictionary" would be the more "natural" data structure here.
But, as has been mentioned**n, this is only one example of an ordering one
could make default for an "ordered" dictionary. Suppose you say it should
be ordered by insertion order, so
d = OrderedDict(); d[1]='one'; d[2]='two' =>> list(d) => [1, 2]
ok, now we do d[1]='ein' and what is the order? list(d) => [2, 1] ??
Or do replacements not count as "insertions "?
"Insertion-order" is not a good term. For a dictionary {key:value} pair
creation, updating and deletion are possible modifying operations. I
don't see how deletion influences the order so creation and updating
remains. Therefore you have to select beween a creation_order and an
update_order. This can be reduced to one additional keyword e.g.
"creation_order " that is assigned a boolean value which is true by
default.
The devil is always going
to be in the details. Maybe you want a model that works more like a list
of key:value pairs with just optimized access to a pair by key name as
well as position in the list. Or maybe you want to permit append and
NOT prevent [('a',1), ('a':2)] and maybe d['a'] => [1, 2] ???
As far as I understand the requirement an odict provides the same
interface as a dict. The only difference is a certain order of the keys
that is induced by operations on a dict and cannot be established by
properties of the keys ( or values ) itself.
Note that is isn't hard to snap a few pieces together to make an ordered
dict to your own specs. But IMO it belongs in pyPI or such, not in the system
library. At least until it gets a lot of mileage -- and MMV ;-)
It's also not very hard to write a hex2ascii converter. That's the
reason why 20 incompatible versions of it ( coded in C ) exists in my
department ;)
Kay
PS. Here is some attempt of my own to implement an odict, following the
discussion here.
The implementation highlights just the model and is incomplete:
class odict(dict):
def __init__(self, create_order = True):
dict.__init__(s elf)
self.create_ord er = create_order
self.__cnt = 0
def __setitem__(sel f, key, value):
val = dict.get(self,k ey)
if val and self.create_ord er:
dict.__setitem_ _(self, key, (val[0], value))
else:
self.__cnt+=1
dict.__setitem_ _(self, key, (self.__cnt, value))
def __getitem__(sel f, key):
return dict.__getitem_ _(self, key)[1]
def values(self):
return list(zip(*sorte d(dict.values(s elf)))[1])
def keys(self):
ks = [(dict.get(self, k)[0],k) for k in dict.keys(self)]
return list(zip(*sorte d(ks))[1])
od = odict()
od["a"] = 0
od["b"] = 8
od.keys()
["a", "b"]
od = odict(create_or der = False)
od["a"] = 1
od["b"] = 2
od["a"] = 3
od.keys()
["b", "a"]
One implementation detail that I think needs further consideration is in
which way to expose the keys and to mix in list methods for ordered
dictionaries.
In http://aspn.activestate.com/ASPN/Coo.../Recipe/107747
the keys are exposed via the keys() method which is bad. It should be a
copy only, like for ordinary dicts (one comment also mentions that).
In Foord/Larosa's odict, the keys are exposed as a public member which
also seems to be a bad idea ("If you alter the sequence list so that it
no longer reflects the contents of the dictionary, you have broken your
OrderedDict").
I think it would be probably the best to hide the keys list from the
public, but to provide list methods for reordering them (sorting,
slicing etc.).
For instance:
d1 = OrderedDict( (1, 11), (2, 12), 3, 13) )
d1[1:] ==> OrderedDict( (2, 12), 3, 13) )
d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
d1.reverse() ==> OrderedDict( (3, 13), (2, 12), 1, 11) )
d1.insert(1, (4, 14))
==> OrderedDict( (1, 11), (4, 14), (2, 12), 3, 13) )
etc.
But no other way to directly manipulate the keys should be provided.
-- Christoph
Magnus Lycka schrieb: I still believe that the concept of an "ordered dictionary" ("behave
like dict, only keep the order of the keys") is intuitive and doesn't
give you so much scope for ambiguity.
Sure. Others think so too. The problem is that if you and these other
people actually write down exactly how this unambigous ordered dict
should behave, you'll end up with a dozen different sets of semantics,
which can be divided in at least three main groups.
That's the point where I dare to disagree. As I have pointed out in
another posting in this thread, all other implementations have the same
semantics for the basic behavior. I cannot see three different groups.
Again, what's so surprising as the "natural" semantics described here: http://mail.python.org/pipermail/pyt...ch/052041.html
-- Christoph
On Tue, 2005-11-22 at 14:37, Christoph Zwerschke wrote: In Foord/Larosa's odict, the keys are exposed as a public member which
also seems to be a bad idea ("If you alter the sequence list so that it
no longer reflects the contents of the dictionary, you have broken your
OrderedDict").
That could easily be fixed by making the sequence a "managed property"
whose setter raises a ValueError if you try to set it to something
that's not a permutation of what it was.
d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
What do you think you're doing here?
-Carsten
Carsten Haese schrieb: I don't think it's intuitive if you can't describe it without
contradicting yourself. If the order of the keys really were the order
in which they were first seen by the dictionary, deleting and recreating
a key should maintain its original position.
Admitted that description was not perfect (anyway it was not mine ;-)).
If a key is deleted, it is deleted. I don't think it is intuitive to
expect that the dict "remembers" a deleted item. If it is added again,
it is like it is seen for the first time and thus appended.
I don't think your argument viliates what I said in my last post.
-- Chris
>>I still believe that the concept of an "ordered dictionary" ("behave like dict, only keep the order of the keys") is intuitive and doesn't
give you so much scope for ambiguity. But probably I need to work on an
implementatio n to become more clear about possible hidden subtleties.
Bengt Richter schrieb:
Does that mean that the Larosa/Foord odict.py implementation in PyPI
does not do what you want?
Basically, it is what I had in mind. But I'm now seeing some things that
could be improved/supplemented, e.g.
- performance improvements
- the internal keys list should be hidden
- list methods should be mixed in instead
-- Christoph This thread has been closed and replies have been disabled. Please start a new discussion. |
