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  9876 
Bengt Richter wrote: I'm mostly friendly ;-)
I'm pretty sure you are :-)
-- Chris
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__(self, 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__(self)
self.create_order = create_order
self.__cnt = 0
def __setitem__(self, key, value):
val = dict.get(self,key)
if val and self.create_order:
dict.__setitem__(self, key, (val[0], value))
else:
self.__cnt+=1
dict.__setitem__(self, key, (self.__cnt, value))
def __getitem__(self, key):
return dict.__getitem__(self, key)[1]
def values(self):
return list(zip(*sorted(dict.values(self)))[1])
def keys(self):
ks = [(dict.get(self,k)[0],k) for k in dict.keys(self)]
return list(zip(*sorted(ks))[1])
od = odict()
od["a"] = 0
od["b"] = 8
od.keys()
["a", "b"]
od = odict(create_order = 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
implementation 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
Carsten Haese wrote: 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.
Ok, a managed attribute would be an option. You would allow people to do
what they want with the sequence, and then fix the dictionary
accordingly (if items were deleted from the sequence, they are deleted
from the dictionary, it items were added which are not in the directory,
a ValueError is raised etc.).
But probably it is still better to hide the sequence and instead of
letting people do list operations like sort() on the odict.sequence, let
them do these operations on odict directly. d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
What do you think you're doing here?
Sorry, what I meant was
d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Ordered dictionaries could allow slicing and concatenation.
-- Christoph
> d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Oops, sorry, that was nonsense again. I meant
d1[0:1] + d1[1:2] ==> OrderedDict( (1, 11), (3, 13) ) Ordered dictionaries could allow slicing and concatenation.
Some operations such as concatenation need of course special
considerations, since the keys must stay unique. A concatenation of
ordered dicts with overlapping keys should probably give an IndexError.
-- Christoph
On Tue, 22 Nov 2005 21:24:29 +0100, Christoph Zwerschke <ci**@online.de> wrote: Carsten Haese wrote:
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.
Ok, a managed attribute would be an option. You would allow people to do
what they want with the sequence, and then fix the dictionary
accordingly (if items were deleted from the sequence, they are deleted
from the dictionary, it items were added which are not in the directory,
a ValueError is raised etc.).
But probably it is still better to hide the sequence and instead of
letting people do list operations like sort() on the odict.sequence, let
them do these operations on odict directly.
d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
What do you think you're doing here?
Sorry, what I meant was
d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Ordered dictionaries could allow slicing and concatenation.
Those are zero-length slices in normal notation. ITYM [0:1] and [2:3]?
Note that you'd have to define addition as possible replacement,
if all the keys happened to match. Or pure concat if none matched,
and variations mixing both ways.
But with the current version you can already write that as
OrderedDict(d1.items()[0:1]+d2.items()[2:3])
you just want the sugar? d1+d2 would be like using [:] in the above line
Not a biggie to do.
Regards,
Bengt Richter
On Tue, 22 Nov 2005 20:15:18 +0100, Christoph Zwerschke <ci**@online.de> wrote: def __init__(self, init_val = ()):
dict.__init__(self, 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.
Since the OrderedDict constructor takes a sequence of tuples as a legitimate
argument, you can always create an ordered dict from an unordered by getting
unordered_dict.items() and sorting or ordering them any way you want and calling
the OrderedDict constructor. Ditto for ordered dicts, since they give your their
ordered items with the items() method as a start. I guess one could pass a
key=fun keyword arg to the OrderedDict constuctor to imply a pre-construction sort.
Regards,
Bengt Richter
On 22 Nov 2005 11:18:19 -0800, "Kay Schluehr" <ka**********@gmx.net> wrote: Bengt Richter wrote: On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke <ci**@online.de> wrote: 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 ;)
Bicycle shed effect, I guess ;-)
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:
This is essentially the tack I took in modifying odict.py, except I
added optional caching of sorted items, and other minor differences.
class odict(dict):
def __init__(self, create_order = True):
dict.__init__(self)
self.create_order = create_order
self.__cnt = 0
def __setitem__(self, key, value):
val = dict.get(self,key)
if val and self.create_order:
dict.__setitem__(self, key, (val[0], value))
else:
self.__cnt+=1
dict.__setitem__(self, key, (self.__cnt, value))
def __getitem__(self, key):
return dict.__getitem__(self, key)[1]
def values(self):
return list(zip(*sorted(dict.values(self)))[1])
maybe more directly
return [v for i,v in sorted(dict.values(self))]
def keys(self):
ks = [(dict.get(self,k)[0],k) for k in dict.keys(self)]
return list(zip(*sorted(ks))[1])
or (untested)
def keys(self):
return [k for k,v in sorted(dict.items(self), key=operator.itemgetter(1))]
def items(self):
return [(k,v[1]) for k,v in sorted(dict.items(self), key=operator.itemgetter(1))] od = odict()
od["a"] = 0
od["b"] = 8
od.keys()["a", "b"]
od = odict(create_order = False)
od["a"] = 1
od["b"] = 2
od["a"] = 3
od.keys()
["b", "a"]
Regards,
Bengt Richter
Bengt Richter wrote: On 22 Nov 2005 03:07:47 -0800, "bo****@gmail.com" <bo****@gmail.com> wrote:
Bengt Richter wrote: Ok, so if not in the standard library, what is the problem? Can't find what
you want with google and PyPI etc.? Or haven't really settled on what your
_requirements_ are? That seems to be the primary problem people who complain
with "why no sprollificator mode?" questions. They don't know what they really
mean when it comes down to a DYFR (Define Your Felicitous Requirements) challenge.
So DYFR ;-)Beat me. I am not the one asking the question.
Sorry, I thought you wanted an ordered dict too.
I want/need(well I am told I don't need) to loop over a dict in certain
order but I don't want or need a standard one as I don't think there is
ONE implementation of it. My original post was a response to the
question "why do one want ordered dict", in the tone of "there is no
way one wants it".
>> > parsing or not parsing is not the point, and parsing/converting is
>> > still "create a new view" of an existing data structure.
>>
So you'd like the mechanics to be automated and hidden? Then you need to
DYFR for using the black box you want. Methods, semantics.
Lose you. don't know what you want to say.
I like solving problems. I just get frustrated when people don't focus on getting
the problem defined, which IME is 2/3 of the way to a solution. I don't mind,
in fact enjoy, rambling musings, but if someone seems actually to want a solution
for something, I like to try to realize it concretely.
I tried to define the problem, and how I solve it(if it helps to convey
the message), but was told you don't have the problem in the first
place.
On Tue, 22 Nov 2005, Carsten Haese wrote: 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.
I'm not a managed property expert (although there's a lovely studio in
Bayswater you might be interested in), but how does this stop you doing:
my_odict.sequence[0] = Shrubbery()
Which would break the odict good and hard.
tom
--
When I see a man on a bicycle I have hope for the human race. --
H. G. Wells
On Tue, 22 Nov 2005 20:37:40 +0100, Christoph Zwerschke <ci**@online.de> wrote: 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.
from odictb import OrderedDict
d1 = OrderedDict([(1, 11), (2, 12), (3, 13)])
d1
{1: 11, 2: 12, 3: 13} d1[1:]
{2: 12, 3: 13} d1[0:1] + d1[2:3]
{1: 11, 3: 13} d1.reverse()
d1
{3: 13, 2: 12, 1: 11} d1.insert(1, (4,14))
d1
{3: 13, 4: 14, 2: 12, 1: 11} d1.items()
[(3, 13), (4, 14), (2, 12), (1, 11)] d1.keys()
[3, 4, 2, 1] d1.values()
[13, 14, 12, 11] d1[1:2]
{4: 14} d1[-1:]
{1: 11}
Que mas?
Regards,
Bengt Richter
On Tue, 22 Nov 2005, Christoph Zwerschke wrote: 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 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.).
I'm not too keen on this - there is conceptually a list here, even if it's
one with unusual constraints, so there should be a list i can manipulate
in code, and which should of course be bound by those constraints.
I think the way to do it is to have a sequence property (which could be a
managed attribute to prevent outright clobberation) which walks like a
list, quacks like a list, but is in fact a mission-specific list subtype
whose mutator methods zealously enforce the invariants guaranteeing the
odict's integrity.
I haven't actually tried to write such a beast, so i don't know if this is
either of possible and straightforward.
tom
--
When I see a man on a bicycle I have hope for the human race. --
H. G. Wells
On Tue, 22 Nov 2005, Christoph Zwerschke wrote: 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."
Exactly.
Python could also do with a sorted dict, like binary tree or something,
but that's another story.
tom
--
When I see a man on a bicycle I have hope for the human race. --
H. G. Wells
Christoph Zwerschke <ci**@online.de> wrote:
... * C++ has a Map template in the STL which is ordered (a "Sorted
Associative Container").
Ordered *by comparisons on keys*, NOT by order of insertion -- an
utterly and completely different idea.
So ordered dictionaries don't seem to be such an exotic idea.
Ordered *by order of key insertion*: Java, PHP
Ordered *by other criteria*: LISP, C++
Unordered: Python, Perl, Ruby, Smalltalk, Awk, Tcl
by classification of the languages you've listed.
I can't help but I still find it unambiguous and intuitive enough to
consider it "the one" standard implementation for ordered dictionaries.
Then you should be very careful not to call C++'s implementation
"ordered", because that makes it VERY HARD to argue that "the one"
thingy;-).
Nevertheless, since sorting by keys (or any function of the keys and
values, including one depending on an external table, which was claimed
to be otherwise in other parts of this thread) is so trivial, while
recovering insertion order is impossible without some auxiliary data
structure ``on the side'', I agree that a dictionary subclass that's
ordered based on insertion timing would have more added value than one
where the 'ordering' is based on any function of keys and values.
Alex
On Tue, 22 Nov 2005 22:06:12 +0100, Christoph Zwerschke <ci**@online.de> wrote: d1[0:0] + d1[2:2] ==> OrderedDict( (1, 11), (3, 13) )
Oops, sorry, that was nonsense again. I meant
d1[0:1] + d1[1:2] ==> OrderedDict( (1, 11), (3, 13) )
Ordered dictionaries could allow slicing and concatenation.
Some operations such as concatenation need of course special
considerations, since the keys must stay unique. A concatenation of
ordered dicts with overlapping keys should probably give an IndexError.
If you define the semantics like feeding overlapping keys in a tuple
sequence to dict, then later duplicate keys just replace prior ones
by same rules as d[k]=v1; d[k]=v2. I think that makes sense in this
context, and can be defined unambigously.
Regards,
Bengt Richter
Tom Anderson <tw**@urchin.earth.li> wrote:
... 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."
Exactly.
Python could also do with a sorted dict, like binary tree or something,
but that's another story.
However, since Christoph himself just misclassified C++'s std::map as
"ordered" (it would be "sorted" in this new terminology he's now
introducing), it seems obvious that the terminological confusion is
rife. Many requests and offers in the past for "ordered dictionaries"
(e.g. on this group) were also "sorted", NOT "ordered", in this new
terminology.
Maybe it would therefore be clearer to have the name of the new
container reflect this, with a specific mention of *insertion* order...
rather than just call it "ordered" and risk probable confusion.
Alex
Alex Martelli wrote: However, since Christoph himself just misclassified C++'s std::map as
"ordered" (it would be "sorted" in this new terminology he's now
introducing), it seems obvious that the terminological confusion is
rife. Many requests and offers in the past for "ordered dictionaries"
(e.g. on this group) were also "sorted", NOT "ordered", in this new
terminology.
Maybe it would therefore be clearer to have the name of the new
container reflect this, with a specific mention of *insertion* order...
rather than just call it "ordered" and risk probable confusion.
Um,
what would be the definition of "sorted" and "ordered", before we can
go on ?
On 22 Nov 2005 19:15:42 -0800, "bo****@gmail.com" <bo****@gmail.com> wrote:
Alex Martelli wrote: However, since Christoph himself just misclassified C++'s std::map as
"ordered" (it would be "sorted" in this new terminology he's now
introducing), it seems obvious that the terminological confusion is
rife. Many requests and offers in the past for "ordered dictionaries"
(e.g. on this group) were also "sorted", NOT "ordered", in this new
terminology.
Maybe it would therefore be clearer to have the name of the new
container reflect this, with a specific mention of *insertion* order...
rather than just call it "ordered" and risk probable confusion.
Um,
what would be the definition of "sorted" and "ordered", before we can
go on ?
For me the implication of "sorted" is that there is a sorting algorithm
that can be used to create an ordering from a prior state of order,
whereas "ordered" could be the result of arbitrary permutation, e.g.,
manual shuffling, etc. Of course either way, a result can be said
to have a particular defined order, but "sorted" gets ordered
by sorting, and "ordered" _may_ get its order by any means.
Regards,
Bengt Richter
Bengt Richter wrote: For me the implication of "sorted" is that there is a sorting algorithm
that can be used to create an ordering from a prior state of order,
whereas "ordered" could be the result of arbitrary permutation, e.g.,
manual shuffling, etc. Of course either way, a result can be said
to have a particular defined order, but "sorted" gets ordered
by sorting, and "ordered" _may_ get its order by any means.
But Alex seems to think that based on another external table should be
classified as "sorted" whereas I would consider it as "manual
shuffling", thus "ordered".
I may be wrong it interpreting him though, which is why I want to
clarify. > Alex Martelli <al***@mail.comcast.net> writes: > Ordered
*by order of key insertion*: Java, PHP > Ordered *by other
criteria*: LISP, C++ Java supports both ordered by key insertion
(LinkedHashMap) as well as ordered by key comparison (TreeMap).
Ganesan
--
Ganesan Rajagopal (rganesan at debian.org) | GPG Key:
1024D/5D8C12EA Web: http://employees.org/~rganesan | http://rganesan.blogspot.com bo****@gmail.com <bo****@gmail.com> wrote: Bengt Richter wrote: For me the implication of "sorted" is that there is a sorting algorithm
that can be used to create an ordering from a prior state of order,
whereas "ordered" could be the result of arbitrary permutation, e.g.,
manual shuffling, etc. Of course either way, a result can be said
to have a particular defined order, but "sorted" gets ordered
by sorting, and "ordered" _may_ get its order by any means.
But Alex seems to think that based on another external table should be
classified as "sorted" whereas I would consider it as "manual
shuffling", thus "ordered".
I may be wrong it interpreting him though, which is why I want to
clarify.
What you can obtain (or anyway easily simulate in terms of effects on a
loop) through an explicit call to the 'sorted' built-in, possibly with a
suitable 'key=' parameter, I would call "sorted" -- exactly because, as
Bengt put it, there IS a sorting algorithm which, etc, etc (if there
wasn't, you couldn't implement it through the 'sorted' built-in!).
So, any ordering that can be reconstructed from the key,value data held
in a dict (looking up some combinations of those in an external table is
nothing special in these terms) falls under this category. But, a dict
does not record anything about what was set or changed or deleted when;
any ordering which requires access to such information thus deserves to
be placed in a totally separate category.
Alex
Alex Martelli wrote: What you can obtain (or anyway easily simulate in terms of effects on a
loop) through an explicit call to the 'sorted' built-in, possibly with a
suitable 'key=' parameter, I would call "sorted" -- exactly because, as
Bengt put it, there IS a sorting algorithm which, etc, etc (if there
wasn't, you couldn't implement it through the 'sorted' built-in!).
So, any ordering that can be reconstructed from the key,value data held
in a dict (looking up some combinations of those in an external table is
nothing special in these terms) falls under this category. But, a dict
does not record anything about what was set or changed or deleted when;
any ordering which requires access to such information thus deserves to
be placed in a totally separate category.
But I can also record these changes in a seperate table which then
becomes a "sorted" case ? bo****@gmail.com <bo****@gmail.com> wrote:
... But I can also record these changes in a seperate table which then
becomes a "sorted" case ?
somedict['x']='y', per se, does no magic callback to let you record
anything when type(somedict) is dict. You can wrap or subclass to your
heart's content to record insertion/deletion/update history, but that
ever-changing "seperate [[sic]] table" is entirely coupled to
'somedict', not therefore "separate" at all, and should properly be kept
as an instance variable of your wrapper or subclass.
That's a pretty obvious difference from cases in which the auxiliary
table used to define the ordering is REALLY *separate* -- independent of
the insertion/etc history of the dictionaries it may be used on.
Alex
Alex Martelli wrote: bo****@gmail.com <bo****@gmail.com> wrote:
... But I can also record these changes in a seperate table which then
becomes a "sorted" case ?
somedict['x']='y', per se, does no magic callback to let you record
anything when type(somedict) is dict. You can wrap or subclass to your
heart's content to record insertion/deletion/update history, but that
ever-changing "seperate [[sic]] table" is entirely coupled to
'somedict', not therefore "separate" at all, and should properly be kept
as an instance variable of your wrapper or subclass.
That's a pretty obvious difference from cases in which the auxiliary
table used to define the ordering is REALLY *separate* -- independent of
the insertion/etc history of the dictionaries it may be used on.
So, it depends.
Christoph Zwerschke wrote: 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?
We're always encouraging new posters to use "good" subject lines.
Several hundred posts after your original question I think everyone can
agree that this was a *very* good subject line :-)
Perhaps now the answer top your question is more obvious: there is by no
means universal agreement on what an "ordered dictionary" should do.
Given the ease with which Python allows you to implement your chosen
functionality it would be presumptuous of the core developers to favour
any one of the several reasonable alternatives that might be chosen.
regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/
Steve Holden wrote: Perhaps now the answer top your question is more obvious: there is by no
means universal agreement on what an "ordered dictionary" should do.
Given the ease with which Python allows you to implement your chosen
functionality it would be presumptuous of the core developers to favour
any one of the several reasonable alternatives that might be chosen.
It seems to be though as "ordered dictionary" are slowly to be confined
to only "ordered on order of change to the dictionary".
Christoph Zwerschke wrote: 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
implementation 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
Implementation changes to follow, based on suggestions in this thread.
For *optimal* performance it needs to be implemented in C of course.
:-)
As F points out, a list of tuples may give you a data structure that
can be accessed quicker (although some operations will be slower). An
ordered dictionary will be a lot easier to use and make your code more
readable though.
- the internal keys list should be hidden
I disagree. It is exposed so that you can manually change the order
(e.g. to create a "sorted" dict, rather than one ordered by key
insertion).
What do you *gain* by hiding it ?
- list methods should be mixed in instead
Hmm... I did consider this. Which list methods would you consider
appropriate ?
The difficulty is that integers are valid keys for a dictionary.
Perhaps a subclass that uses integers as indexes instead...
You can always perform list operations on the ``sequence`` attribute of
course.
All the best,
Fuzzyman
http://www.voidspace.org.uk/python/index.shtml
-- Christoph
Bengt Richter wrote: On 22 Nov 2005 02:16:22 -0800, "Fuzzyman" <fu******@gmail.com> wrote:
Kay Schluehr wrote: Christoph Zwerschke wrote:
> That would be also biased (in favour of Python) by the fact that
> probably very little people would look for and use the package in the
> cheese shop if they were looking for ordered dicts.
Does anyone actually use this site? While the Vaults offered a nice
place and a nice interface the Cheese Shop has the appeal of a code
slum.
Hmmm.. it's *the* repository for Python code. I expect quite a few
people use it...
:-)
I hadn't realized how much stuff was there. I generally google for stuff,
but I will be looking directly now.
BTW, I made a mod[1] to your odict that I think/hope is going to be generally faster.
It requires 2.4 though. It passes the same doctest, so its probably close to the same.
It stores the ordering info differently, but is also a dict subclass.
odict maintains compatibility with Python 2.2 - so it's not a change
we'd put back into the module I don't think.
Changes that keep compatibility are very welcoemd though.
Do you happen to have a timing test that exercises various aspects, so I can try it
before I embarrass myself? Otherwise I guess I'll write something.
The only tests we have are the ones in the module.
If you create some timing tests we'd be interested in having access to
them though. They would be a useful addition.
All the best,
Fuzzyman
http://www.voidspace.org.uk/python/index.shtml
Would the would-be users chime in with some idea of what kinds of operations are
most important timing-wise? Which would get the most use? How dynamic would ordering typically be?
[1] fairly pervasive little mods actually
[ 9:15] C:\pywk\clp>diff odict.py odictb.py |wc
146 458 4948
[ 9:15] C:\pywk\clp>wc odict*.py
467 1228 12483 odict.py
511 1500 14728 odictb.py
978 2728 27211 Totals
Regards,
Bengt Richter
While we're on the subject, it would be useful to be able to paste in a
changelog as well as a description.
Currently when updating versions you have to include the changelog in
the description - or not at all...
All the best,
Fuzzyman http://www.voidspace.org.uk/python/index.shtml
Christoph Zwerschke wrote: 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").
So don't do it. ;-)
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) )
So what do you want returned when you ask for d1[1] ? The member keyed
by 1, or the item in position 1 ?
You can access the members using list operations on the sequence
attribute.
E.g. d1[d1.sequence[index]]
This could probably be made more convenient.
d1[0] + d1[2] ==> OrderedDict( (1, 11), (3, 13) )
d1.reverse() ==> OrderedDict( (3, 13), (2, 12), 1, 11) )
Interesting idea.
d1.insert(1, (4, 14))
==> OrderedDict( (1, 11), (4, 14), (2, 12), 3, 13) )
Also an interesting idea.
etc.
But no other way to directly manipulate the keys should be provided.
Why - don't trust yourself with it ?
All the best,
Fuzzyman
http://www.voidspace.org.uk/python/index.shtml
-- Christoph
There is already an update method of course. :-)
Slicing an ordered dictionary is interesting - but how many people are
actually going to use it ? (What's your use case)
You can already slice the sequence atribute and iterate over that.
All the best,
Fuzzyman http://www.voidspace.org.uk/python/index.shtml bo****@gmail.com wrote: Steve Holden wrote: Perhaps now the answer top your question is more obvious: there is by no
means universal agreement on what an "ordered dictionary" should do.
Given the ease with which Python allows you to implement your chosen
functionality it would be presumptuous of the core developers to favour
any one of the several reasonable alternatives that might be chosen.
It seems to be though as "ordered dictionary" are slowly to be confined
to only "ordered on order of change to the dictionary".
While I'm only +0 for a standard odict I'm wondering that discussing
this topic leads to the auctoritative conclusion that it is unsolvable,
we have to accept infinite diversity etc. where people like me seeing a
classification immediately ( mathematical education? ) . Of course this
matter is trivial but we already know about monster-threads revolving
around decorator syntax ( including hurt souls and semi-scientific
papers ) and abandoning the print statement in Python 3.0.
Christoph Zwerschke wrote: Ok, I just did a little research an compared support for ordered dicts
in some other languages:
Just to add to your list:
In Javascript Object properties (often used as an associative array) are
defined as unordered although as IE seems to always store them in the order
of original insertion it wouldn't surprise me if there are a lot of
websites depending on that behaviour.
Javascript Array indexes are also stored as properties and are therefore
also unordered.
On 23 Nov 2005 01:24:46 -0800, "Kay Schluehr" <ka**********@gmx.net> wrote:
bo****@gmail.com wrote: Steve Holden wrote: > Perhaps now the answer top your question is more obvious: there is by no
> means universal agreement on what an "ordered dictionary" should do.
> Given the ease with which Python allows you to implement your chosen
> functionality it would be presumptuous of the core developers to favour
> any one of the several reasonable alternatives that might be chosen.
>
It seems to be though as "ordered dictionary" are slowly to be confined
to only "ordered on order of change to the dictionary".
While I'm only +0 for a standard odict I'm wondering that discussing
this topic leads to the auctoritative conclusion that it is unsolvable,
we have to accept infinite diversity etc. where people like me seeing a
classification immediately ( mathematical education? ) . Of course this
matter is trivial but we already know about monster-threads revolving
around decorator syntax ( including hurt souls and semi-scientific
papers ) and abandoning the print statement in Python 3.0.
I think the concept has converged to a replace-or-append-by-key ordering
of key:value items with methods approximately like a dict. We're now
into usability aspects such as syntactic sugar vs essential primitives,
and default behaviour vs selectable modes, ISTM.
E.g., it might be nice to have a mode that assumes d[key] is d.items()[k][1] when
key is an integer, and otherwise uses dict lookup, for cases where the use
case is just string dict keys.
But feature creep is sure a threat to clean design.
Regards,
Bengt Richter
"Fuzzyman" <fu******@gmail.com> wrote in
news:11*********************@o13g2000cwo.googlegro ups.com:
Christoph Zwerschke wrote: - the internal keys list should be hidden
I disagree. It is exposed so that you can manually change the
order (e.g. to create a "sorted" dict, rather than one ordered
by key insertion).
What do you *gain* by hiding it ?
The internal list should be 'hidden' in the sense that it itself
would not be modifiable, though it should be routine to obtain a
copy of it at any time. That copy could then be arranged as needed.
Any rearrangement of the original list's order destroys the reason
for having an entry- or change-ordered dict in the first place.
--
rzed
Ganesan Rajagopal wrote: >> bonono@gmail com <bo****@gmail.com> writes: > what would be
the definition of "sorted" and "ordered", before we can > go on ? Sorted
would be ordered by key comparison. Iterating over such a container will
give you the keys in sorted order. Java calls this a SortedMap. See
http://java.sun.com/j2se/1.4.2/docs/...SortedMap.html C++ STL
map container is also a Sorted Associative container. See
http://www.sgi.com/tech/stl/Map.html Ganesan
In Python it's simple to keep a list sorted using bisect.insort.
import bisect
l=[]
bisect.insort(l,4)
bisect.insort(l,3)
bisect.insort(l,5)
bisect.insort(l,1)
bisect.insort(l,6)
bisect.insort(l,2)
l
[1, 2, 3, 4, 5, 6]
Assuming a list with n tuples, where the first m elements in each
tuple is the key, we can also fetch elements through keys (interval
matches as well as exact matches) with O(log n) performance.
I guess those who thinks this isn't enough should push for placing
something like Zope's BTree classes in the standard library.
Fredrik already showed how simple and cheap it was to make a dict out
of a list. I think this is a superior solution to odicts as suggested,
but by all means, if people want odicts, make sure that there is a
good implementation available, use it, show that it's useful to
others, and maybe, some time in the future, it will be considered
for inclusion in the standard library.
On Tue, 2005-11-22 at 20:44, Tom Anderson wrote: On Tue, 22 Nov 2005, Carsten Haese wrote:
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.
I'm not a managed property expert (although there's a lovely studio in
Bayswater you might be interested in), but how does this stop you doing:
my_odict.sequence[0] = Shrubbery()
It would only break if the getter returns the internal list directly.
The getter should return a copy instead, which is what the keys() method
already does anyway. This would ensure that the only way to alter the
sequence is by replacing it in its entirety.
-Carsten.
Rick Wotnaz wrote: "Fuzzyman" <fu******@gmail.com> wrote in
news:11*********************@o13g2000cwo.googlegro ups.com:
Christoph Zwerschke wrote: - the internal keys list should be hidden
I disagree. It is exposed so that you can manually change the
order (e.g. to create a "sorted" dict, rather than one ordered
by key insertion).
What do you *gain* by hiding it ?
The internal list should be 'hidden' in the sense that it itself
would not be modifiable, though it should be routine to obtain a
copy of it at any time. That copy could then be arranged as needed.
Any rearrangement of the original list's order destroys the reason
for having an entry- or change-ordered dict in the first place.
That's not the only use case. Other use cases are to have a specific
order, not based on entry time.
Simple example :
d1 = OrderedDict(some_dict.items())
d1.sequence.sort()
d1 is now an ordered dict with the keys in alphabetic order.
If you don't want to modify sequence, don't. If you want a copy do :
seq = d1.sequence[:]
All the best,
Fuzzyman
http://www.voidspace.org.uk/python/index.shtml
--
rzed
Fuzzyman <fu******@gmail.com> wrote: There is already an update method of course. :-)
Slicing an ordered dictionary is interesting - but how many people are
actually going to use it ? (What's your use case)
I detest and abhor almost-sequences which can't be sliced (I consider
that a defect of collections.deque). If the ordered dictionary records
by its sequencing the time order of key insertion, being able to ask for
"the last 5 keys entered" or "the first 3 keys entered" seem to me to be
perfectly natural use cases, and most naturally accomplished by slicing
of course, d[-5:] and d[:3] respectively.
Alex
Fuzzyman <fu******@gmail.com> wrote:
... - the internal keys list should be hidden
I disagree. It is exposed so that you can manually change the order
(e.g. to create a "sorted" dict, rather than one ordered by key
insertion).
What do you *gain* by hiding it ?
Freedom of implementation, of course. E.g., I can perhaps get better
performance by keeping a red-black tree of (insertiontime,key) pairs, so
for example deleting a key is O(log(N)) rather than O(N) as it would
have to be if the sequence had to be kept as a Python list.
What ELSE do you ever gain by enforcing abstraction and information
hiding? Conceptual integrity and implementation freedom...
- list methods should be mixed in instead
Hmm... I did consider this. Which list methods would you consider
appropriate ?
The difficulty is that integers are valid keys for a dictionary.
Perhaps a subclass that uses integers as indexes instead...
What about allowing slicing, taking advantage of the fact that slices
are NOT valid dictionary keys?
Presumably sort and reverse methods are also desired.
You can always perform list operations on the ``sequence`` attribute of
course.
But NOT having to expose .sequence as a real mutable list whose changes
affect ordering has many advantages, as above noticed.
Alex
Steve Holden schrieb: Perhaps now the answer top your question is more obvious: there is by no
means universal agreement on what an "ordered dictionary" should do.
Given the ease with which Python allows you to implement your chosen
functionality it would be presumptuous of the core developers to favour
any one of the several reasonable alternatives that might be chosen.
The discussion showed indeed that there are some points which are not so
straightforward as I believed. But I still don't see the "several
reasonable alternatives". So far all implementations I have seen are
basically pretty similar. Is there any implementation that is basically
different from Foord/Larosa's odict? I still don't see a principal
problem here, just the problem that the existing implementations are not
well enough thought-out and sophisticated enough.
Given the ease with which Python allows you to implement your chosen
functionality it would be presumptuous of the core developers to
favour any one of the several reasonable alternatives that might be
chosen.
You could say the same about the idea of sets in Python, and it is
probably the reason why it took so much time until they became a part of
Python. I wished that had happened earlier, since sets are "the" basic
mathematic structure. I'm now very happy to have sets not only in the
standard lib but even as built-in types and I'm sure there hasn't been
"universal agreement" on how sets should be implemented either. I don't
think it was presumptuous to finally settle down on one implementation.
Of course, ordered dictionaries are no candidates for becoming built-in
data types, and the existing implementations are not sophisticated and
mature enough to go to the standard lib right now. But principally, if
an improved version is developed (maybe on the occasion of this thread)
and will be tested and proven, why should it not go to the standard lib
some day?
BTW, somebody has suggested it could go to "collections" which sounds
like the right place, but the description says the module is intended
for "High-performance container datatypes", and, as has been discussed,
ordered dictionaries are not used for performance or efficiency reasons,
but rather for reasons of convenience. So *if* they ever go to the
standard lib, I'm not sure whether "collections" would be the right
place. Or collections will need a different description - maybe there
are other interesting basic collection types which are chosen for
convenience, not for performance (for instance, ordered sets)?
-- Christoph bo****@gmail.com schrieb: It seems to be though as "ordered dictionary" are slowly to be confined
to only "ordered on order of change to the dictionary".
"Ordered dictionary" means that the keys are not an ordinary set like in
an ordinary dictionary, but an "ordered set." I think this definition is
pretty straightforward and common. An ordered set is the same as a
unique list, i.e. a list where all elements are unique.
When there is automatical ordering using a comparison function, I would
not speak of an "ordered directory", but of a "sorted directory." This
would be basically a dictionary plus a comparison function. The keys
would always be iterated in the order given by the comparison function.
It would be nice to have a sorted dictionary as well, even if you can
achieve the same by calling the sorted built-in on the keys. Think of a
sorted directory as a subclass of ordered directories. Implementing it
that way would even have perfomance benefits if the keys are inserted
using the bisect algorithm. This is better than calling sorted() on the
keys of an ordinary dictionary many times.
By the way, you will find the same terminology in Smalltalk, where
"SortedCollection" is a subclass of "OrderedCollection".
-- Christoph This thread has been closed and replies have been disabled. Please start a new discussion. |
