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  10272 
On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke <ci**@online.de> wrote: Ordering the keys isn't the normal case, and can be done easily when
needed.
That depends. Maybe I do not want the keys to be sorted alphabetically,
but according to some criteria which cannot be derived from the keys
themselves.
You mean involving also the values? What's wrong with
sorted(plaindict.items(), key=your_ordering_function) ? def show(*a): print a
... sorted(dict((c,ord(c)) for c in 'abcd').items(), key=show)
(('a', 97),)
(('c', 99),)
(('b', 98),)
(('d', 100),)
[('a', 97), ('c', 99), ('b', 98), ('d', 100)]
What key function would you like, to generate the value that is actually used
to define the ordering?
sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[0])
[('a', 97), ('b', 98), ('c', 99), ('d', 100)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[1])
[('a', 97), ('b', 98), ('c', 99), ('d', 100)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:-t[1])
[('d', 100), ('c', 99), ('b', 98), ('a', 97)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[1]&1)
[('b', 98), ('d', 100), ('a', 97), ('c', 99)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,t[1]))
[('b', 98), ('d', 100), ('a', 97), ('c', 99)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,-t[1]))
[('d', 100), ('b', 98), ('c', 99), ('a', 97)]
And being able to reverse the end result is handy sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,-t[1]), reverse=True)
[('a', 97), ('c', 99), ('b', 98), ('d', 100)]
You may need to upgrade your Python though ;-)
Regards,
Bengt Richter
On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke <ci**@online.de> wrote: Ordering the keys isn't the normal case, and can be done easily when
needed.
That depends. Maybe I do not want the keys to be sorted alphabetically,
but according to some criteria which cannot be derived from the keys
themselves.
You mean involving also the values? What's wrong with
sorted(plaindict.items(), key=your_ordering_function) ? def show(*a): print a
... sorted(dict((c,ord(c)) for c in 'abcd').items(), key=show)
(('a', 97),)
(('c', 99),)
(('b', 98),)
(('d', 100),)
[('a', 97), ('c', 99), ('b', 98), ('d', 100)]
What key function would you like, to generate the value that is actually used
to define the ordering?
sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[0])
[('a', 97), ('b', 98), ('c', 99), ('d', 100)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[1])
[('a', 97), ('b', 98), ('c', 99), ('d', 100)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:-t[1])
[('d', 100), ('c', 99), ('b', 98), ('a', 97)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:t[1]&1)
[('b', 98), ('d', 100), ('a', 97), ('c', 99)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,t[1]))
[('b', 98), ('d', 100), ('a', 97), ('c', 99)] sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,-t[1]))
[('d', 100), ('b', 98), ('c', 99), ('a', 97)]
And being able to reverse the end result is handy sorted(dict((c,ord(c)) for c in 'abcd').items(), key=lambda t:(t[1]&1,-t[1]), reverse=True)
[('a', 97), ('c', 99), ('b', 98), ('d', 100)]
You may need to upgrade your Python though ;-)
Regards,
Bengt Richter
Bengt Richter wrote: On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke <ci**@online.de> wrote: Ordering the keys isn't the normal case, and can be done easily when
needed.
That depends. Maybe I do not want the keys to be sorted alphabetically,
but according to some criteria which cannot be derived from the keys
themselves.
You mean involving also the values? What's wrong with
sorted(plaindict.items(), key=your_ordering_function) ?
Not according to the content of the data, not just the "key". Or in
other words, some other metadata that is not present in the data. A
typical thing, like order of creation. Or some arbitary order. For
example :
I present a data grid/table in a HTML form and the user just drag and
drop and rearrange the columns order.
Of course, you may say, just put another column that represent
this(some reporting programs I have seen do it this way) and that is an
option but not the only option.
Ben Finney wrote: bo****@gmail.com <bo****@gmail.com> wrote: [sort by] some other metadata that is not present in the data.
[...]
Of course, you may say, just put another column that represent
this(some reporting programs I have seen do it this way) and that is
an option but not the only option.
It's a pretty good option, and very commonly used. It's known as the
"Schwartzian transform", or more descriptively, the "Decorate, Sort,
Undecorate" pattern.
Whether it is a good option is judged by the person implement it as he
is the one seeing the whole thing, and not some snippet(or concept) on
the usenet.
Ben Finney wrote: bo****@gmail.com <bo****@gmail.com> wrote: [sort by] some other metadata that is not present in the data.
[...]
Of course, you may say, just put another column that represent
this(some reporting programs I have seen do it this way) and that is
an option but not the only option.
It's a pretty good option, and very commonly used. It's known as the
"Schwartzian transform", or more descriptively, the "Decorate, Sort,
Undecorate" pattern.
Whether it is a good option is judged by the person implement it as he
is the one seeing the whole thing, and not some snippet(or concept) on
the usenet. bo****@gmail.com wrote: Fredrik Lundh wrote: but you can easily generate an index when you need it:
index = dict(d)
name, type = index["pid"]
print name
the index should take less than a microsecond to create, and since it
points to the members of the original dict, it doesn't use much memory
either...
Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.
No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
There's no parsing involved, nor any type guessing. And given the use case,
it's more than fast enough, and doesn't copy any data.
If you think that's the same thing as parsing strings, you've completely missed
the point.
</F> bo****@gmail.com wrote: Fredrik Lundh wrote: but you can easily generate an index when you need it:
index = dict(d)
name, type = index["pid"]
print name
the index should take less than a microsecond to create, and since it
points to the members of the original dict, it doesn't use much memory
either...
Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.
No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
There's no parsing involved, nor any type guessing. And given the use case,
it's more than fast enough, and doesn't copy any data.
If you think that's the same thing as parsing strings, you've completely missed
the point.
</F>
Fredrik Lundh wrote: bo****@gmail.com wrote:
Fredrik Lundh wrote: but you can easily generate an index when you need it:
index = dict(d)
name, type = index["pid"]
print name
the index should take less than a microsecond to create, and since it
points to the members of the original dict, it doesn't use much memory
either...
Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.
No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
There's no parsing involved, nor any type guessing. And given the use case,
it's more than fast enough, and doesn't copy any data.
If you think that's the same thing as parsing strings, you've completely missed
the point.
Well, forget about the missing/not missing the point.
My point is, there are various of reasons why we need different data
types in an RDBMS, just the same as why we need list, dict. There is
nothing stop me from using a list as dict(just scan it till I find it),
why would I I create a dict(your new view of the same data) ? Coding
convenience, speed or whatever.
If I need the dict feature 90% of the time, and the list feature 10% of
the time. I want an ordered dict. Rather than a list and create this
new view every time and every where I want to use it as a dict.
parsing or not parsing is not the point, and parsing/converting is
still "create a new view" of an existing data structure.
Fredrik Lundh wrote: bo****@gmail.com wrote:
Fredrik Lundh wrote: but you can easily generate an index when you need it:
index = dict(d)
name, type = index["pid"]
print name
the index should take less than a microsecond to create, and since it
points to the members of the original dict, it doesn't use much memory
either...
Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.
No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
There's no parsing involved, nor any type guessing. And given the use case,
it's more than fast enough, and doesn't copy any data.
If you think that's the same thing as parsing strings, you've completely missed
the point.
Well, forget about the missing/not missing the point.
My point is, there are various of reasons why we need different data
types in an RDBMS, just the same as why we need list, dict. There is
nothing stop me from using a list as dict(just scan it till I find it),
why would I I create a dict(your new view of the same data) ? Coding
convenience, speed or whatever.
If I need the dict feature 90% of the time, and the list feature 10% of
the time. I want an ordered dict. Rather than a list and create this
new view every time and every where I want to use it as a dict.
parsing or not parsing is not the point, and parsing/converting is
still "create a new view" of an existing data structure. bo****@gmail.com wrote: If I need the dict feature 90% of the time, and the list feature 10% of
the time.
Wasn't your use case that you wanted to specify form fields in
a given order (LIST), render a default view of the form in that
order (LIST), and, later on, access the field specifiers in an
arbitrary order, based on their key (DICT). Sure looks like it's
the LIST aspect that's important here...
("but assume that I have some other use case" isn't a valid use
case)
I want an ordered dict. Rather than a list and create this new view every
time and every where I want to use it as a dict.
You want an ordered dict because you say you want one, not be-
cause it's the best way to address your use case. That's fine, but
it's not really related to the question asked in the subject line.
parsing or not parsing is not the point, and parsing/converting is
still "create a new view" of an existing data structure.
Copying the entire data structure hardly qualifies as "creating a
new view". dict() doesn't do that; in this use case, it doesn't cost
you anything to use it.
Everything has a cost in Python. Things aren't free just because
they're implemented by some other module.
But when things are free, they're often a good choice.
</F> bo****@gmail.com wrote: If I need the dict feature 90% of the time, and the list feature 10% of
the time.
Wasn't your use case that you wanted to specify form fields in
a given order (LIST), render a default view of the form in that
order (LIST), and, later on, access the field specifiers in an
arbitrary order, based on their key (DICT). Sure looks like it's
the LIST aspect that's important here...
("but assume that I have some other use case" isn't a valid use
case)
I want an ordered dict. Rather than a list and create this new view every
time and every where I want to use it as a dict.
You want an ordered dict because you say you want one, not be-
cause it's the best way to address your use case. That's fine, but
it's not really related to the question asked in the subject line.
parsing or not parsing is not the point, and parsing/converting is
still "create a new view" of an existing data structure.
Copying the entire data structure hardly qualifies as "creating a
new view". dict() doesn't do that; in this use case, it doesn't cost
you anything to use it.
Everything has a cost in Python. Things aren't free just because
they're implemented by some other module.
But when things are free, they're often a good choice.
</F>
Fredrik Lundh wrote: bo****@gmail.com wrote:
If I need the dict feature 90% of the time, and the list feature 10% of
the time.
Wasn't your use case that you wanted to specify form fields in
a given order (LIST), render a default view of the form in that
order (LIST), and, later on, access the field specifiers in an
arbitrary order, based on their key (DICT). Sure looks like it's
the LIST aspect that's important here...
Yes. But whether LIST aspect or DICT is important is well, opinion. So
let's leave it there. I want an ordered dict. Rather than a list and create this new view every
time and every where I want to use it as a dict.
You want an ordered dict because you say you want one, not be-
cause it's the best way to address your use case. That's fine, but
it's not really related to the question asked in the subject line.
Again, best way is decided by ME. If I am entering a coding contest
which is organized by YOU, that is a different story. As for related to
the subject line, since when I said my preference or use case has
anything to do with the subject line ? I have said in another post that
I don't think there should be one in the standard library, which is
directly about the subject line.
parsing or not parsing is not the point, and parsing/converting is
still "create a new view" of an existing data structure.
Copying the entire data structure hardly qualifies as "creating a
new view". dict() doesn't do that; in this use case, it doesn't cost
you anything to use it.
doesn't cost me anything ? That is good news to me.
Fredrik Lundh wrote: bo****@gmail.com wrote:
If I need the dict feature 90% of the time, and the list feature 10% of
the time.
Wasn't your use case that you wanted to specify form fields in
a given order (LIST), render a default view of the form in that
order (LIST), and, later on, access the field specifiers in an
arbitrary order, based on their key (DICT). Sure looks like it's
the LIST aspect that's important here...
Yes. But whether LIST aspect or DICT is important is well, opinion. So
let's leave it there. I want an ordered dict. Rather than a list and create this new view every
time and every where I want to use it as a dict.
You want an ordered dict because you say you want one, not be-
cause it's the best way to address your use case. That's fine, but
it's not really related to the question asked in the subject line.
Again, best way is decided by ME. If I am entering a coding contest
which is organized by YOU, that is a different story. As for related to
the subject line, since when I said my preference or use case has
anything to do with the subject line ? I have said in another post that
I don't think there should be one in the standard library, which is
directly about the subject line.
parsing or not parsing is not the point, and parsing/converting is
still "create a new view" of an existing data structure.
Copying the entire data structure hardly qualifies as "creating a
new view". dict() doesn't do that; in this use case, it doesn't cost
you anything to use it.
doesn't cost me anything ? That is good news to me.
Op 2005-11-21, Christoph Zwerschke schreef <ci**@online.de>: bo****@gmail.com wrote: Personally, I have needs for ordered dict but I don't think it should
be in standard library though, as different situation called for
different behaviour for "ordered" and skewing my code to a standard lib
way is no good.
I have started the thread in the first place because I believed it is
pretty unabmiguous what an "ordered dictionary" is and how it should
behave. That's why I asked myself why something that straigthforward has
not been added to the standard lib yet. Maybe I'm wrong; I must admit
that I haven't meditated about it very much.
Well it doesn't seem that obvious, because the two recipes you have
gotten, do something different from what I understand as an ordered
dictionary.
The two recipes order the keys by insertion order.
My idea would have been that some order was defined
on your keys in advance and that when you iterated over
the dictionary, the results would be ordered in sequence
of key order.
Do you have an example for different options of behavior?
Well you have two above. Maybe someone can think of something
else.
Which behaviour are you looking for?
--
Antoon Pardon
Op 2005-11-21, Christoph Zwerschke schreef <ci**@online.de>: bo****@gmail.com wrote: Personally, I have needs for ordered dict but I don't think it should
be in standard library though, as different situation called for
different behaviour for "ordered" and skewing my code to a standard lib
way is no good.
I have started the thread in the first place because I believed it is
pretty unabmiguous what an "ordered dictionary" is and how it should
behave. That's why I asked myself why something that straigthforward has
not been added to the standard lib yet. Maybe I'm wrong; I must admit
that I haven't meditated about it very much.
Well it doesn't seem that obvious, because the two recipes you have
gotten, do something different from what I understand as an ordered
dictionary.
The two recipes order the keys by insertion order.
My idea would have been that some order was defined
on your keys in advance and that when you iterated over
the dictionary, the results would be ordered in sequence
of key order.
Do you have an example for different options of behavior?
Well you have two above. Maybe someone can think of something
else.
Which behaviour are you looking for?
--
Antoon Pardon
Fredrik Lundh wrote: bo****@gmail.com wrote: Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.
No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
This is interesting; I would have thought that the tuple is read and a
dictionary created by inserting each pair sequentially. Is this not the
case?
--
Ben Sizer
Fredrik Lundh wrote: bo****@gmail.com wrote: Using the same logic, we don't need types other than string in a DBMS
as we can always convert a string field into some other types when it
is needed.
No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
This is interesting; I would have thought that the tuple is read and a
dictionary created by inserting each pair sequentially. Is this not the
case?
--
Ben Sizer
Ben Sizer wrote: No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
This is interesting; I would have thought that the tuple is read and a
dictionary created by inserting each pair sequentially. Is this not the
case?
pointers to the members of each pair, yes. but a pointer copy is a
cheap operation (for the given use case, we're only talking about a
few dozen pairs anyway, at the most).
this is a common fallacy; Python programmers underestimate the
cost of adding extra layers to their code (e.g. by using an ordered
dict data structure that has to incrementally update both a list and
a dictionary), and overestimate the cost of letting the C layer do
bulk operations.
(as an example, on my machine, using Foord's OrderedDict class
on Zwerschke's example, creating the dictionary in the first place
takes 5 times longer than the index approach, and accessing an
item takes 3 times longer. you can in fact recreate the index 6
times before OrderedDict is faster; if you keep the index around,
the OrderedDict approach never wins...)
</F>
Ben Sizer wrote: No, that's not the same logic. The dict() in my example doesn't convert be-
tween data types; it provides a new way to view an existing data structure.
This is interesting; I would have thought that the tuple is read and a
dictionary created by inserting each pair sequentially. Is this not the
case?
pointers to the members of each pair, yes. but a pointer copy is a
cheap operation (for the given use case, we're only talking about a
few dozen pairs anyway, at the most).
this is a common fallacy; Python programmers underestimate the
cost of adding extra layers to their code (e.g. by using an ordered
dict data structure that has to incrementally update both a list and
a dictionary), and overestimate the cost of letting the C layer do
bulk operations.
(as an example, on my machine, using Foord's OrderedDict class
on Zwerschke's example, creating the dictionary in the first place
takes 5 times longer than the index approach, and accessing an
item takes 3 times longer. you can in fact recreate the index 6
times before OrderedDict is faster; if you keep the index around,
the OrderedDict approach never wins...)
</F>
Tom Anderson wrote: Incidentally, can we call that the "Larosa-Foord ordered mapping"?
The implementation, sure.
Then it sounds like some kind of rocket science discrete mathematics stuff
But math folks usually name things after the person(s) who came
up with the idea, not just some random implementer. The idea of
combining unordered mappings and ordered sequences is older than
Python itself.
</F>
Alex Martelli schrieb: Perl hashes now keep track of 'order of keys'? That's new to me, they
sure didn't back when I used Perl!
Maybe I shouldn't have talked about Perl when I'm an ignoramus about
that language... You're right, Perl has unordered arrays. That was new
to me since I associate the term "array" always with "ordered" and I
just remembered that PHP's assoc arrays are similar to Perl's but in
fact, and the examples I have read did not mention about that problem.
What about PHP?
You can conclude that PHP's assoc arrays are ordered from the fact that
the language provides a ksort() function to order the keys. And I think
PHP's insertion order is the one I mentioned in my last post.
Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
"first insertion (since the last deletion if any)" is ONE unambiguous
definition, but surely not "_the_ ONE" with emphasis on ``the''.
I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
*last* insertion, for example; indeed if phrased as "upon insertion, put
the key at the end of the sequence" (whether it was already elsewhere in
the sequence of not), with no need for conditionals regarding previous
existence, it might appear more "conceptually compact".
But it would not satisfy the concept of "keys of a dictionary" which are
always unique.
BTW, there are some boundary conditions that should be fulfilled for the
insertion order, most obviously:
If you define an ordered dict that way:
d = odict()
d['a'] = 1
d['b'] = 2
d['c'] = 3
The keys should then be orderes as ('a', 'b', 'c').
Anyway -- subclassing dict to implement your definition is reasonably
easy, and we could put the resulting package on the Cheese Shop. I hope
python.org keeps good enough statistics to be able to tell us, a couple
months later, how many people downloaded said package, vs how many
people downloaded a complete Python distro; of course, that ratio is
biased (in favour of the package) by the fact that many people already
have a complete distro available, while initially nobody would have the
package, but if we measure when things settle, after letting a month of
two or 'transient' pass, that effect might be lessened.
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. I for example would
probably use ordered dicts if they were part of the standard lib, but
not if I have to install it as an obscure separate package. So I don't
think that will give us a real clue how many people would like ordered
dicts in the standard lib.
But anyway, if I find some time, I will research a little bit more about
the issue and create such a package, because it seems to me that the
existing packages and recipes are not really satisfying and you're right
it seems to be reasonably easy. It's on my todo list now...
-- Christoph
Bengt Richter schrieb: 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.
What I don't understand is why legitimate questions such as "why are
there no ordered dictionaries" are immediately interpreted as
*complaints* and not just as questions. If I ask such a question, I am
not complaining but trying to simply figure out *why* there is no such
thing. Probably there are reasons and all I want to know is find these
reasons and learn a little bit more about Python in doing so.
Why can't such questions be discussed in a factual, calm and friendly way?
They don't know what they really mean when it comes down to a DYFR
(Define Your Felicitous Requirements) challenge.
I don't think that this was true in this case, and even if this is the
outcome, those who asked the question will have learned something.
I think a discussion group is not there for only presenting mature,
sophisticated thoughts and concepts, but also for "thinking loud"
together with other about these issues. We all know that clarifying our
thoughts works often best if you discuss them with others. And I think
that's one purpose of discussion lists. Asking questions should not be
immediately be discouraged, even silly questions. If it is really a FAQ,
you can simply point to the FAQ or add the answer in the FAQ list if it
is missing there.
-- Chris
Alex Martelli wrote: What about PHP? Thanks!
according to some random PHP documentation I found on the intarweb:
An array in PHP is actually an ordered map. A map is a type that
maps values to keys.
and later:
A key may be either an integer or a string. If a key is the standard
representation of an integer, it will be interpreted as such (i.e. "8"
will be interpreted as 8, while "08" will be interpreted as "08"). Floats
in key are truncated to integer.
and later:
You cannot use arrays or objects as keys. Doing so will result in a
warning: Illegal offset type.
at which point my brain raised an exception.
</F>
Christoph Zwerschke wrote: Fredrik Lundh wrote:
[snip..] You're right; I found creating a Larosa/Foord OrderedDict in this
example to be even 8 times slower than an ordinary dict. However, two
things need to be said here: 1) The dictionary in my exmaple was pretty
small (only 3 items), so you are not really measuring the performance of
the ordered dict, but mainly the overhead of using a user derived class
in comparison with the built-in dict type. And 2) the implementation by
Larosa/Foord is very slow and can be easily improved, for instance like
that:
def __init__(self, init_val = ()):
dict.__init__(self, init_val)
self.sequence = [x[0] for x in init_val]
But that doesn't allow you to create an ordered dict from another
ordered dict.
It also allows duplicates in the sequence attribute. It's a useful idea
though.
Thanks
Fuzzyman
http://www.voidspace.org.uk/python/index.shtml
With this change, creating the ordered dictionary is considerably faster
and for an average size dictionary, the factor of 8 pretty quickly
converges against 1.
But of course, it will always be slower since it is constructed on top
of the built-in dict. In end effect, you always have to maintain a
sequence *plus* a dictionary, which will be always slower than a sheer
dictionary. The ordered dictionary class just hides this uglyness of
having to maintain a dictionary plus a sequence, so it's rather an issue
of convenience in writing and reading programs than a performance issue.
It may be different if the ordered dict would be implemented directly as
an ordered hash table in C.
-- Christoph
Bengt Richter wrote: 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"?
If you simply set a value for a key that already exists, the order
should not be changed. I think this is intuitive.
Or maybe you want to permit append and NOT prevent
[('a',1), ('a':2)] and maybe d['a'] => [1, 2] ???
You could ask the same question about dict. I think that is not an
option. Why should you want odict behave different than dict?
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.
-- Christoph
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.
Kay
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...
:-)
Fuzzyman
http://www.voidspace.org.uk/python/index.shtml
Kay
On Tue, 22 Nov 2005 09:20:34 +0100, Fredrik Lundh wrote: Tom Anderson wrote:
Incidentally, can we call that the "Larosa-Foord ordered mapping"?
The implementation, sure.
Then it sounds like some kind of rocket science discrete mathematics stuff
But math folks usually name things after the person(s) who came
up with the idea, not just some random implementer.
No no no! In maths things are usually named after Euler, or the first
person to discover them after Euler.
--
Steven.
Christoph Zwerschke wrote: But please see my other reply: If the dictionary has more than 3 items
(say 10 or 20), and an effective ordered dict is used, it's not really
"a lot" slower. At least if we are talking about a situation were "on
demand" is "always". So, on the other side there isn't such a big
performance loss when using ordered dictionaries as well.
There is no performance issue involved with this usecase at all!
It doesn't matter if it's hundreds of tuples of strings in a list
if it's supposed to be presented in a GUI. Recreating a dict from
that is bound to be magnitudes faster than getting the stuff
visible on the screen, at least if we're talking web apps. So is
using a reasonable odict implementation, if that's what you want.
I think the issue is not to overload the already extensive standard
library with trivial things that can easily be replaced by your own
three line wrapper, especially if there are a number of different
semantics that could be imagined for such a thingie.
The C++ std lib has an ordered "dict" class called map, and that's
ordered by key. Others suggested ordering by value, and there are a
number of different interpretations of the 'order by insertion time'
theme in the air. This clearly smells like "fix your own thing and
leave it out of the standard library".
With one of these solutions picked as Python's "ordered dict", we'll
make things slightly more convenient for a few programmers and just
burden others with something that sounds right for them, but turns
out not to solve their problems. Or, we could try to make a bunch
of different solution, increasing the cognitive burden for all who
learn Python while solving non-problems. This just isn't going to
happen!
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. > 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.
Christoph Zwerschke wrote: Bengt Richter schrieb: 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.
What I don't understand is why legitimate questions such as "why are
there no ordered dictionaries" are immediately interpreted as
*complaints* and not just as questions. If I ask such a question, I am
not complaining but trying to simply figure out *why* there is no such
thing. Probably there are reasons and all I want to know is find these
reasons and learn a little bit more about Python in doing so.
Why can't such questions be discussed in a factual, calm and friendly way?
Using "why can't" is already too much. Even you turn it into "is there
a thing for ordered dict", you would get similar treatment
Get used to it :-) > They don't know what they really mean when it comes down to a DYFR
> (Define Your Felicitous Requirements) challenge.
I don't think that this was true in this case, and even if this is the
outcome, those who asked the question will have learned something.
I think a discussion group is not there for only presenting mature,
sophisticated thoughts and concepts, but also for "thinking loud"
together with other about these issues. We all know that clarifying our
thoughts works often best if you discuss them with others. And I think
that's one purpose of discussion lists. Asking questions should not be
immediately be discouraged, even silly questions. If it is really a FAQ,
you can simply point to the FAQ or add the answer in the FAQ list if it
is missing there.
Well, different groups has different "personality", just don't be
scared.
Christoph Zwerschke wrote: Fredrik Lundh wrote: I'll repeat this one last time: for the use cases presented by Zwerschke
and "bonono", using a list as the master data structure, and creating the
dictionary on demand, is a lot faster than using a ready-made ordered
dict implementation. if you will access things via the dictionary a lot,
you can cache the dictionary somewhere. if not, you can recreate it
several times and still get a net win.
You're right in pointing out that the advantage of ordered dictionaries
(unless you use an omptimized C implementation) is not a performance gain.
But please see my other reply: If the dictionary has more than 3 items
(say 10 or 20), and an effective ordered dict is used, it's not really
"a lot" slower. At least if we are talking about a situation were "on
demand" is "always". So, on the other side there isn't such a big
performance loss when using ordered dictionaries as well.
The advantage of using an ordered dictionary is that you can set up your
ordered dictionary (say, describing your database columns) once, and
then can access it in any way you like in the following: Iterate over it
in a guaranteed order or access item, always refering to the same
object, without needing to care about building and caching auxiliary
objects with different names depending on what you are doing.
Well, I don't think performance is the concern(at least not for me),
but how best to blend with the rest of the code which I have no
interest to explain as I am not here to convincing anyone for such a
thing. I just present a use case, if they see it, fine. If not, that is
fine too.
But I did learn something that creating a dict on a list cost me
nothing, I would be less worry about the performance hit in the future.
On 22 Nov 2005 01:41:44 -0800,
Kay Schluehr <ka**********@gmx.net> wrote: 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.
Looking at the Cheese Shop's home page at http://cheeseshop.python.org/pypi, which lists recent package updates,
three packages were updated on 11/22, and three on 11/21. Two on
11/20, six on 11/19 (someone was busy!).
Looking at the Vaults's 'latest' page at http://py.vaults.ca/apyllo.py?a=l, two packages were updated on 08/23,
and five on 08/06.
What would improve the Cheese Shop's interface for you?
--amk
A.M. Kuchling wrote: On 22 Nov 2005 01:41:44 -0800,
Kay Schluehr <ka**********@gmx.net> wrote: 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.
Looking at the Cheese Shop's home page at
http://cheeseshop.python.org/pypi, which lists recent package updates,
three packages were updated on 11/22, and three on 11/21. Two on
11/20, six on 11/19 (someone was busy!).
Looking at the Vaults's 'latest' page at
http://py.vaults.ca/apyllo.py?a=l, two packages were updated on 08/23,
and five on 08/06.
What would improve the Cheese Shop's interface for you?
--amk
From the treasures of the vaults to cheese shops - an upside down
evolution :( Personally I find the usability of the Vaults quite well
and it's design o.k. I guess it is a technical detail that causes the
Vaults to be phased out.
If I'd try something more innovative by myself I'd think about
accessing and filtering packages through the Python console itself.
Probably an enhanced standard console enabling SQL commands. Updates of
a local database ( e.g. SQLite ) should be cheap and may be performed
by only one request. Searching, filtering, loading, installing would be
done in a Python+SQL environment.
Kay
Of course ours is ordered *and* orderable ! You can explicitly alter
the sequence attribute to change the ordering.
I think we're looking at improving performance based on some of the
suggestions here - as well as possibly widening it to include some of
the alternative use cases. (Or at least Nicola Larosa will do it and
I'll criticise it).
All for another day though...
Fuzzyman http://www.voidspace.org.uk/python/index.shtml
Christoph Zwerschke <ci**@online.de> wrote: Alex Martelli schrieb: Perl hashes now keep track of 'order of keys'? That's new to me, they
sure didn't back when I used Perl!
Maybe I shouldn't have talked about Perl when I'm an ignoramus about
that language... You're right, Perl has unordered arrays. That was new
to me since I associate the term "array" always with "ordered" and I
just remembered that PHP's assoc arrays are similar to Perl's but in
fact, and the examples I have read did not mention about that problem.
Perl's _arrays_ are a bit like Python _lists_, and ordered; it's the
_hashes_ that are a bit like Python _dicts_, and unordered. PHP's use
of "array" for both concepts may indeed be a bit confusing.
What about PHP?
You can conclude that PHP's assoc arrays are ordered from the fact that
the language provides a ksort() function to order the keys. And I think
PHP's insertion order is the one I mentioned in my last post.
Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
Yep. After just a bit of research I suspect you're right re PHP but
haven't found a specific reference-manual page URL about it.
"first insertion (since the last deletion if any)" is ONE unambiguous
definition, but surely not "_the_ ONE" with emphasis on ``the''.
I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
> *last* insertion, for example; indeed if phrased as "upon insertion, put
> the key at the end of the sequence" (whether it was already elsewhere in
> the sequence of not), with no need for conditionals regarding previous
existence, it might appear more "conceptually compact".
But it would not satisfy the concept of "keys of a dictionary" which are
always unique.
Why not? Since keys are unique, any 'sequence' of keys is a permutation
of a set, a perfectly well-defined concept.
BTW, there are some boundary conditions that should be fulfilled for the
insertion order, most obviously:
If you define an ordered dict that way:
d = odict()
d['a'] = 1
d['b'] = 2
d['c'] = 3
The keys should then be orderes as ('a', 'b', 'c').
Yep, but both 'first-insertion' and 'latest-insertion' (and many other
rules) meet that constraint.
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. I for example would
probably use ordered dicts if they were part of the standard lib, but
not if I have to install it as an obscure separate package. So I don't
think that will give us a real clue how many people would like ordered
dicts in the standard lib.
A package on cheese shop need not be "obscure" -- that depends on
announcing it well, etc. And the standard library is so huge that many
things inside IT are in fact obscure -- I find myself often pointing out
standard-library solutions to rather experienced Pythonistas who had
been rolling their own, unaware of the stdlib alternative (thus making
the stdlib even bigger has a cost...). So, I don't think this effect
invalidates the experiment; while not all who download an add-on would
like it in the stdlib, and vice versa, there is surely a correlation
between amount of interest/need for the add-on's functionality, and both
rate of downloads as well as interest in having it in the stdlib.
But anyway, if I find some time, I will research a little bit more about
the issue and create such a package, because it seems to me that the
existing packages and recipes are not really satisfying and you're right
it seems to be reasonably easy. It's on my todo list now...
It presumably should have a C implementation for speed and a Python one
for wide availability and ease of installation (the latter gives all the
advantages of prototyping in fixing the API &c, and is made especially
easy by the existence of UserDict.DictMixin in the stdlib). I'll be
glad to help out with the C part when it gets to that, just holler...
Alex
Fredrik Lundh <fr*****@pythonware.com> wrote:
... But math folks usually name things after the person(s) who came
up with the idea, not just some random implementer. The idea of
Wrong: you're forgetting Stigler's Law of Misonomy (which I imagine must
have NOT been discovered by Stigler...;-). The Poisson distribution was
in fact described earlier by Bernoulli, Gosset's z-test is universally
known as Student's t-test, etc, etc.
Salsburg's delightful "The Lady Tasting Tea" has a lot of fun with
Stigler's law in the footnotes...;-)
Alex
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.
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.
People use different idioms, and often gather collections of classes
and functions that fit their style of coding and their typical problem
domains. There is nothing wrong with that, and they might well be made
publically available if they are more generally useful.
When adding things to the standard library, there are some more things
to consider, particularly for something general such as an odict class:
Is is general enough, and does it add enough value to outweigh the
increased cognitive burden of more classes/functions/types in the
library?
For a beginner, it's easy to believe that things would be easier if
the tool you use had already solved the problem you have at hand for
you, but it turns out that the world has so many problems, that you
would end up with a impenetrable forest of standard library modules
if we actually tried to achieve this.
"A.M. Kuchling" <am*@amk.ca> wrote in message news:9s********************@speakeasy.net...
[...] What would improve the Cheese Shop's interface for you?
Getting rid of those damn top level links to old versions.
Seeing a long list of old versions, when 99% of visitors are
only interested in the current version, is just visual noise,
and really lame. Move the old version links onto the page
describing the software.
Christoph Zwerschke wrote: But of course, it will always be slower since it is constructed on top
of the built-in dict. In end effect, you always have to maintain a
sequence *plus* a dictionary, which will be always slower than a sheer
dictionary. The ordered dictionary class just hides this uglyness of
having to maintain a dictionary plus a sequence, so it's rather an issue
of convenience in writing and reading programs than a performance issue.
It may be different if the ordered dict would be implemented directly as
an ordered hash table in C.
The problem with hashing is that one is storing data from a possibly
wildly varying range in a set of values with a limited range. That's
where the ordering problems come from in the first place. If one wants
to solve it once and for all one has to give up the speed advantage
that makes hashing so popular. I wonder if optimized C code using
bisect would be very much slower for small ranges?
The current set implementation uses dicts to implement sets, while sets
are a more basic data type than dicts. At least dicts and sets should
be derived from the same type. Just speaking from an intuitive point of
view of course :-)
Here's a sorted dict implementation without using hashes, which maybe
would be fast if implemented in C. The insertion order can be retrieved
using the keys and values lists from the object itself, items() gives a
sorted sequence.
Anton.
NB warning untested code.
When using mutables as keys which is possible by this implementation,
don't change the keys after they're used in the object.
from array import array
class VDict:
def __init__(self,sequence = []):
self.keys = []
self.values = []
self.unranks = array('L',[])
for key,value in sequence:
self[key] = value
def __setitem__(self,key,value):
keys = self.keys
values = self.values
unranks = self.unranks
n = len(keys)
i = self.bisect_left(key)
if i == n or keys[unranks[i]] != key:
keys.append(key)
values.append(value)
unranks.insert(i,n)
else:
values[i] = value
def __getitem__(self,key):
i = self.bisect_left(key)
return self.values[self.unranks[i]]
def bisect_left(self,key, lo=0, hi=None):
keys = self.keys
unranks = self.unranks
if hi is None:
hi = len(keys)
while lo < hi:
mid = (lo+hi)//2
if keys[unranks[mid]] < key:
lo = mid+1
else:
hi = mid
return lo
def __contains__(self,key):
keys = self.keys
unranks = self.unranks
n = len(keys)
i = self.bisect_left(key)
return i < n and keys[unranks[i]] == key
def __len__(self):
return len(self.keys)
def items(self):
keys = self.keys
values = self.values
unranks = self.unranks
return [(keys[i],values[i]) for i in unranks]
def __iter__(self):
return iter(self.items())
def remove(self,key):
keys = self.keys
values = self.values
unranks = self.unranks
n = len(keys)
i = self.bisect_left(key)
x = unranks[i]
if i < n and keys[x] == key:
del keys[x]
del values[x]
del unranks[i]
for j,k in enumerate(unranks):
if k > x:
unranks[j] -= 1
def test():
V = VDict()
L = [1,2,3]
V[L] = 10
print V[L]
V[L] = 20
print V[L]
V.remove(L)
print V.items()
V = VDict(zip('edcba',range(5)))
print V.items()
print V['d']
V.remove('d')
print V.items()
if __name__=='__main__':
test()
Fredrik Lundh wrote: Ben Sizer wrote: This is interesting; I would have thought that the tuple is read and a
dictionary created by inserting each pair sequentially. Is this not the
case?
pointers to the members of each pair, yes. but a pointer copy is a
cheap operation (for the given use case, we're only talking about a
few dozen pairs anyway, at the most).
I was really thinking more about the other work, such as the hashing
and whatever, but I guess that is very efficient anyway.
this is a common fallacy; Python programmers underestimate the
cost of adding extra layers to their code (e.g. by using an ordered
dict data structure that has to incrementally update both a list and
a dictionary), and overestimate the cost of letting the C layer do
bulk operations.
If it was me I would probably have just used a list and searched it
linearly: premature optimisation is the root of all evil, etc. But then
I've never found a need for an ordered dictionary anyway; I always felt
they were more an artifact of the language implementation than a
reflection of something inherently useful.
However, you have to forgive people for falling prey to the 'fallacy'
you describe - for years there's been an attempt to teach people to use
proper data structures and algorithms instead of relying on
micro-optimisations (ie. "it's too slow: redo it in assembly"). So
often, the first port of call for a good programmer will be to try and
find a structure that maps directly to the problem.
--
Ben Sizer
Stuart McGraw wrote What would improve the Cheese Shop's interface for you?
Getting rid of those damn top level links to old versions.
Seeing a long list of old versions, when 99% of visitors are
only interested in the current version, is just visual noise,
and really lame. Move the old version links onto the page
describing the software.
hmm? the pypi package automatically hides old versions when
you post new ones, and it's been that way for ages...
(which is bloody annoying if you're a package developers, since it
means that alphas for the next release hides the most recent stable
version)
looking at the full index, ZODB seems to be the only package that's
available in more than just one stable and one development version...
</F>
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.
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.
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
"Fredrik Lundh" <fr*****@pythonware.com> wrote in message news:ma***************************************@pyt hon.org... Stuart McGraw wrote
What would improve the Cheese Shop's interface for you?
Getting rid of those damn top level links to old versions.
Seeing a long list of old versions, when 99% of visitors are
only interested in the current version, is just visual noise,
and really lame. Move the old version links onto the page
describing the software.
hmm? the pypi package automatically hides old versions when
you post new ones, and it's been that way for ages...
(which is bloody annoying if you're a package developers, since it
means that alphas for the next release hides the most recent stable
version)
looking at the full index, ZODB seems to be the only package that's
available in more than just one stable and one development version... http://cheeseshop.python.org/pypi?:a...rowse&asdf=405
- ClientForm-0.1.17
- ClientForm-0.2.1b
....
- EmPy_3.1
- EmPy_3.1.1
- EmPy_3.2
- EmPy_3.3
....
- FauxIdent-1.1
- FauxIdent-1.2
- FauxIdent-1.2.1
....
Well, it is better than I remember it being a while (year?) ago, my
recollection is that many packages had many, many old versions
listed but now I usualy see only a couple versions.
Hmm, so two versions means one is a development version,
and the other is a stable version? I did not know that, and did
not see it documented on the site. I would say documenting
that would be an interface improvement.
I still think it would be better to have just a package name
(with current version) listed in the index page(s), and have alternate
versions (old, alpha testing, etc) listed on the package's description
page.
On Tue, 22 Nov 2005 10:06:07 +0100, Christoph Zwerschke <ci**@online.de> wrote: Bengt Richter schrieb: 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.
What I don't understand is why legitimate questions such as "why are
there no ordered dictionaries" are immediately interpreted as
*complaints* and not just as questions. If I ask such a question, I am
not complaining but trying to simply figure out *why* there is no such
thing. Probably there are reasons and all I want to know is find these
reasons and learn a little bit more about Python in doing so.
Why can't such questions be discussed in a factual, calm and friendly way?
Sorry, I was tired and vented some impatience. I'm mostly friendly ;-)
I took the "why" in a different sense than it was meant, I guess.
Sort of like hearing "why haven't I been served yet" in a restaurant, and
having to say, "I don't work here, you'll have to ask the waiter."
They don't know what they really mean when it comes down to a DYFR
(Define Your Felicitous Requirements) challenge.
I don't think that this was true in this case, and even if this is the
outcome, those who asked the question will have learned something.
I agree again.
I think a discussion group is not there for only presenting mature,
sophisticated thoughts and concepts, but also for "thinking loud"
together with other about these issues. We all know that clarifying our
thoughts works often best if you discuss them with others. And I think
that's one purpose of discussion lists. Asking questions should not be
immediately be discouraged, even silly questions. If it is really a FAQ,
you can simply point to the FAQ or add the answer in the FAQ list if it
is missing there.
Agreed again. Thank you for your nice reply.
Regards,
Bengt Richter
Stuart McGraw wrote: Hmm, so two versions means one is a development version,
and the other is a stable version? I did not know that, and did
not see it documented on the site. I would say documenting
that would be an interface improvement.
well, that's up to the developer. when you upload a new version, all
older ones are automagically hidden. the only way to make old versions
appear again is to "unhide" them via a web form. for the few packages
I sampled, the older versions were stable, and the latest one was "less
stable", but I didn't check all of the...
I still think it would be better to have just a package name
(with current version) listed in the index page(s), and have alternate
versions (old, alpha testing, etc) listed on the package's description
page.
agreed.
a "nonstable"-property in the setup file would be nice too (so that stable
versions don't disappear when you upload an alpha or beta...)
</F>
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.
>> > 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.
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.
I still don't know whether it will be of any user w.r.t. the requirements of anyone
on the bandwagon of asking for some kind of ordered dict, but we'll see what we'll see ;-)
Regards,
Bengt Richter
On Tue, 22 Nov 2005 10:26:22 +0100, Christoph Zwerschke <ci**@online.de> wrote: Bengt Richter wrote:
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"?
If you simply set a value for a key that already exists, the order
should not be changed. I think this is intuitive.
Or maybe you want to permit append and NOT prevent
[('a',1), ('a':2)] and maybe d['a'] => [1, 2] ???
You could ask the same question about dict. I think that is not an
option. Why should you want odict behave different than dict?
Well, it was beginning to remind of RDB with possible non-unique keys,
where a select can get you multiple records back.
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.
Does that mean that the Larosa/Foord odict.py implementation in PyPI
does not do what you want?
Regards,
Bengt Richter
Alex Martelli wrote: Perl's _arrays_ are a bit like Python _lists_, and ordered; it's the
_hashes_ that are a bit like Python _dicts_, and unordered. PHP's use
of "array" for both concepts may indeed be a bit confusing.
Perl's _hashes_ have been also called _associative arrays_ originally. Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
Ok, I just did a little research an compared support for ordered dicts
in some other languages:
* Perl has hashes (associative arrays) which are not ordered.
Here also people are asking for and implementing "ordered hashes",
e.g. http://perltraining.com.au/tips/2005-06-29.html http://search.cpan.org/dist/Tie-IxHa.../Tie/IxHash.pm http://search.cpan.org/dist/Tie-Inse...rtOrderHash.pm http://www.yapc.org/America/previous...or/pinyan.html
* Ruby hashes are not ordered.
Again people are asking for and implementing "ordered hashes".
e.g. http://raa.ruby-lang.org/project/orderedhash/ http://groups.google.com/group/comp....28a870925f23f4
* Smalltalk: Innately has unordered Dictionaries.
People are asking for and implementing "OrderedDictionaries" as well,
e.g. http://exept.eu.org:8080/ClassDoc/cl...eredDictionary
* Lisp has (ordered) "association lists".
* PHP has ordered associative arrays.
* Awk, TCL: Associative arrays are unordered.
* C++ has a Map template in the STL which is ordered (a "Sorted
Associative Container").
* Java: Has "LinkedHashMap" which is ordered.
So ordered dictionaries don't seem to be such an exotic idea.
All implementations I found were pretty unequivocally the same that I
had in mind, using insertion order, appending the latest inserted keys
at the end, not changing the order if an existing key is re-inserted,
and deleting keys together with entries.
I also found a discussion thread like the current where similar
arguments were mentioned for and against ordered dictionaries:
In http://mail.python.org/pipermail/pyt...ch/052041.html,
Nick Coghlan raises the following rhetorical question:
Would the default semantics below really be that suprising?
"An ordered dictionary remembers the order in which keys are first seen
and, when iterated over, returns entries based on that order. This
applies to direct iteration, iteration over values and (key, value)
pairs, to the list-producing methods (i.e. keys(), values() and items())
and to any other operations that involve implicit iteration (e.g.
converting to a string representation). 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. This behaviour is analagous to that of a list constructed using
only list.append() to add items (indeed, the key order can be thought of
as a list constructed in this fashion, with keys appended to the list
when they are first encountered)."
This was also the semantics I immediately had in mind when I thought
about ordered dictionaries, though I hadn't read anything about ordered
dictionaries before and it is the same semantics that I found others
have implemented in other languages.
I can't help but I still find it unambiguous and intuitive enough to
consider it "the one" standard implementation for ordered dictionaries.
Also, in the use cases mentioned (describing database columns, html form
fields, configuration parameters etc.), the dictionary is usually only
created once and then not changed, so different handling of re-insertion
or deletion of keys would not even be relevant in these cases.
-- Christoph
Bengt Richter wrote: I'm mostly friendly ;-)
I'm pretty sure you are :-)
-- Chris This thread has been closed and replies have been disabled. Please start a new discussion. |
