Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] 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?:action=browseasdf=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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 10:06:07 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 22 Nov 2005 03:07:47 -0800, [EMAIL PROTECTED] [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 10:26:22 +0100, Christoph Zwerschke [EMAIL PROTECTED]
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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-IxHash/lib/Tie/IxHash.pm http://search.cpan.org/dist/Tie-InsertOrderHash/InsertOrderHash.pm http://www.yapc.org/America/previous-years/19100/schedule/author/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.lang.ruby/browse_frm/thread/8ebe8d1c5830c801/6428a870925f23f4 * Smalltalk: Innately has unordered Dictionaries. People are asking for and implementing OrderedDictionaries as well, e.g. http://exept.eu.org:8080/ClassDoc/classDocOf:,OrderedDictionary * 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/python-dev/2005-March/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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman schrieb: Of course ours is ordered *and* orderable ! You can explicitly alter the sequence attribute to change the ordering. What I actually wanted to say is that there may be a confusion between a sorted dictionary (one where the keys are automatically sorted) and an ordered dictionary (where the keys are not automatically ordered, but have a certain order that is preserved). Those who suggested that the sorted function would be helpful probably thought of a sorted dictionary rather than an ordered dictionary. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: I'm mostly friendly ;-) I'm pretty sure you are :-) -- Chris -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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/Cookbook/Python/Recipe/438823 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747 http://pleac.sourceforge.net/pleac_python/hashes.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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote:
On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke [EMAIL PROTECTED]
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]
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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/Cookbook/Python/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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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/python-dev/2005-March/052041.html -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 21:24:29 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 20:15:18 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 22 Nov 2005 11:18:19 -0800, Kay Schluehr [EMAIL PROTECTED] wrote: Bengt Richter wrote: On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: On 22 Nov 2005 03:07:47 -0800, [EMAIL PROTECTED] [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 20:37:40 +0100, Christoph Zwerschke [EMAIL PROTECTED]
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/Cookbook/Python/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
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 22:06:12 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Tom Anderson [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 ? -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 22 Nov 2005 19:15:42 -0800, [EMAIL PROTECTED] [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] com [EMAIL PROTECTED] 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/api/java/util/SortedMap.html C++ STL map container is also a Sorted Associative container. See http://www.sgi.com/tech/stl/Map.html Ganesan -- Ganesan Rajagopal (rganesan at debian.org) | GPG Key: 1024D/5D8C12EA Web: http://employees.org/~rganesan| http://rganesan.blogspot.com -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 ? -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli wrote: [EMAIL PROTECTED] [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote: [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote: [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Op 2005-11-21, Christoph Zwerschke schreef [EMAIL PROTECTED]: [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote: [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote: 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? [snip..] (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...) So, so long as you want to use the dictionary less than six times - it's faster to store/access it as a list of tuples. ;-) Everytime you want to access (or assign to) the data structure as a dictionary, you have to re-create the index. Fuzzyman http://www.voidspace.org.uk/python/index.shtml /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote: ... d = somedict_from_db() prefer=['f','a',b'] def my_order(d): for x in prefer: if x in d: yield x s = frozenset(prefer) for x in d: if x not in s: yield x Yes, a much cleaner architecture (if you don't need any sorting on non-preferred keys of d) than the ponderous general one I proposed. A 'key' approach with this behavior would be: def my_key(k): try: return prefer.index(k) except ValueError: return len(prefer) Now, 'for x in sorted(d, key=my_key)' should be equivalent to 'for x in my_order(d)' thanks to the stability of sorting when the 'key' callable returns equal values. Neither of these way-simpler approaches is (I suspect) optimal for speed, in the unlikely event one cares about that. The idea of preprocessing the 'preferred' list once and for all outside of the function (which I used heavily in my previous post) might yield some speed-up, for example: def my_key_fast(k, _aux=dict((k,i) for i,k in enumerate(prefer), _l=len(prefer)): return _aux.get(k, _l) It's very unlikely that this situation warrants such optimization, of course, I'm just thinking aloud about abstract possibilities. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman wrote: [snip..] (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...) So, so long as you want to use the dictionary less than six times - it's faster to store/access it as a list of tuples. ;-) nope. that's not what I said. I said that you can recreate the index six times in the time it takes to create a single OrderedDict instance. if you need to use index more than that, it's not that hard to keep a reference to it. Everytime you want to access (or assign to) the data structure as a dictionary, you have to re-create the index. the use case we're talking about here (field descriptors) doesn't involve assigning to the data structure, once it's created. 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. for other use cases, things may be different, but nobody has presented such a use case yet. as I said earlier, let's assume we have another use case is not a valid use case. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ben Finney wrote: Another possibility: ordered dictionaries are not needed when Python 2.4 has the 'sorted' builtin. Christoph Zwerschke wrote: The 'sorted' function does not help in the case I have indicated, where I do not want the keys to be sorted alphabetically, but according to some criteria which cannot be derived from the keys themselves. Mike Meyer wrote: And how would an ordered dictionary help in this case? Maybe there is some confusion between an orderable and an ordered dictionary. When I talk about ordered dictionary, then in the simplest case I just set up my ordered dictionary with my preferred key order and it stays like that. This allows me to later iterate through the dictionary in this preferred order, while being still able to randomly access data from the dictionary at other places. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote: (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...) 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] 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh [EMAIL PROTECTED] wrote: ... (but assume that I have some other use case isn't a valid use case) +1 QOTW Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli wrote: Note the plural in 'insertion orderS': some people care about the FIRST time a key was added to a dict, some about the LAST time it was added, some about the latest time it was 'first inserted' (added and wasn't already there) as long as it's never been deleted since that occasion -- and these are just a few of the multifarious orders based on the time of insertions and deletions of keys. Ok, I start to understand that ambiguity emerges when you delete and insert items. I didn't think much about this problem because my use cases usually do not involve inserttion or deletion after the ordered dictionary has been created. But I think the following rule is natural enough to consider it as THE standard behavior of ordered dictionaries: Insertion: If the key exists: Don't change the order. If it does not exist: Append it to the sequence of keys. Deletion: Remove from the sequence of keys. I think this is also the behavior of associative arrays in PHP or Perl and could be considered as the ONE unambiguous definition. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
In article [EMAIL PROTECTED], Alex Martelli [EMAIL PROTECTED] wrote: I think you're wrong here. People in the past who have requested or implemented stuff they called 'ordered dicts' in the past had in mind drastically different things, based on some combination of insertion orders, keys, and _values_. So, ambiguity is definitely present in the phrase 'ordered dictionary', because there are so many different criteria whereby the 'ordering' could take place. Note the plural in 'insertion orderS': some people care about the FIRST time a key was added to a dict, some about the LAST time it was added, some about the latest time it was 'first inserted' (added and wasn't already there) as long as it's never been deleted since that occasion -- and these are just a few of the multifarious orders based on the time of insertions and deletions of keys. Ayup. In our application, not only do we have ordered dicts, we also have something called a sectioned dict, which is a dict-like object that also looks like a regular class instance with attribute access. The section part actually has multiple dicts (the sections) which are layered, so that a dict key in the top layer overrides the value of the key in lower layers. We traditionally have used it such that the sections are accessed in MRU orders; last week, we added a new feature that allows setting section values without changing section order (to allow setting a default, essentially). -- Aahz ([EMAIL PROTECTED]) * http://www.pythoncraft.com/ If you think it's expensive to hire a professional to do the job, wait until you hire an amateur. --Red Adair -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Sun, 20 Nov 2005, Alex Martelli wrote: Christoph Zwerschke [EMAIL PROTECTED] wrote: The 'sorted' function does not help in the case I have indicated, where I do not want the keys to be sorted alphabetically, but according to some criteria which cannot be derived from the keys themselves. Ah, but WHAT 'some criteria'? There's the rub! First insertion, last insertion, last insertion that wasn't subsequently deleted, last insertion that didn't change the corresponding value, or...??? All the requests for an ordered dictionary that i've seen on this group, and all the cases where i've needed on myself, want one which behaves like a list - order of first insertion, with no memory after deletion. Like the Larosa-Foord ordered dict. Incidentally, can we call that the Larosa-Foord ordered mapping? Then it sounds like some kind of rocket science discrete mathematics stuff, which (a) is cool and (b) will make Perl programmers feel even more inadequate when faced with the towering intellectual might of Python. Them and their Scwartzian transform. Bah! tom -- Baby got a masterplan. A foolproof masterplan. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote:
huh? if you want a list, use a list.
d = [('a', {...}), ('b', {})]
If one wants uniform access to a nested data structure like this one
usually starts writing a wrapper class. I do not think the requirement
is anyhow deeper than a standard wrapper around such a list ( as a
model ) but the implementation may be different with respect to optimal
time complexitiy of element access. But the interface of the wrapper
class of d might resemble that of a dict. While the interface is that
of a dict the implementation is closer to a nested list. An ordered
dict would lower the impedance between a dict and a list.
Kay
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 20 Nov 2005 21:12:52 -0800, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Bengt Richter wrote: On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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. ^^[1] [1] implies known info of before and after rearrangement. Where do these come from, and are the two states expressed as ordered sets of keys generated and stored somewhere? The point is, to re-order, you need a mapping from unordered data dict keys to values which the sorted builtin function will order in the way you want. (BTW, if you use DSU, make sure the data is not modifying your sort in an undesired way. Passing a key function to sorted makes it easy to exclude unwanted data from the sort). If you have data that determines a new ordering of keys, it has to be accessed somehow, so you just need to make it accessible to a handy helper that will generate your key function. E.g, with before and after lists of keys expressing e.g. drag-drop before and after orderings, lambda can do the job of getting you dict items in the new order, e.g., where bef and aft are lists that define the desired orderings before and after in the sense of sort_precedence = bef.index[key_in_bef] and same for aft. sorted(thedict.items(),key=lambda t:dict(zip(bef,((k in aft and aft.index(k) or len(aft)+bef.index(k)) for k in bef))[t[0]]) Ok, that one-liner grew a bit ;-) 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. Maybe you could keep the rearranged_keys vector in a per-user cookie, if it's a web app and amounts to a user personalization? ( posting delayed 12 hrs due to news server prob ;-/ ) Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Mon, 21 Nov 2005 01:27:22 +0100, Christoph Zwerschke [EMAIL PROTECTED]
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? 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] ???
The point is that Python is a nice lego set, and pre-molded castles
don't re-use well, even if they suit a particular you to a t ;-)
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 ;-)
I also wanted to mention the uglyness in the definition (nested tuples),
but then I understood that even an ordered dictionary would not
eliminate that uglyness, since the curly braces are part of the Python
syntax and cannot be used for creating ordered dictionaries anyway. I
would have to define the ordered dictionary in the very same ugly way:
d = odict(('pid', ('Employee ID', 'int')),
('name', ('Employee name', 'varchar')),
('sal', ('Salary', 'float')))
(Unless the Python syntax would be extend to use double curly braces or
something for ordered dictionaries - but I understand that this is not
an option.)
Whatever your odict does, if I had type a lot of definitions for it
I think I would write a QnD helper to make this work:
d = odict(prep(
pid, Employee ID, int
name, Employee name, varchar # (comments to be ignored)
sal, Salary, float # alignment as above not mandatory
other, Something else, long, additional elements, allowed in second tuple?
))
( posting delayed 12 hrs due to news server prob ;-/ )
Regards,
Bengt Richter
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 21 Nov 2005 01:54:38 -0800, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Fredrik Lundh wrote: [EMAIL PROTECTED] 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. 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 ;-) Then someone can take less time than many of these posts takes to make a list subclass that also acts like the dict when you want or a dict subclass that also acts like a list when you want. Which methods from which would you like as-is, and which modified? Any additional methods or properties? DYFR ;-) 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. 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. Well, if you want something specific, it WILL cost you the effort to DYFR in detail ;-) ( posting delayed 12 hrs due to news server prob ;-/ ) Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] wrote: ... But I think the following rule is natural enough to consider it as THE standard behavior of ordered dictionaries: Insertion: If the key exists: Don't change the order. If it does not exist: Append it to the sequence of keys. Deletion: Remove from the sequence of keys. I think this is also the behavior of associative arrays in PHP or Perl Perl hashes now keep track of 'order of keys'? That's new to me, they sure didn't back when I used Perl! It's been a while, but a little googling shows me, e.g at http://www.openarchives.org/pipermail/oai-implementers/2002-September/0 00642.html, assertions such as: Hashes don't maintain key order. To get them in sorted order try: foreach $i (sort keys(%afiliacao)) which fully match my memories. Could you produce a URL to support the hypothesis that Perl has changed its behavior? What about PHP? Thanks! and could be considered as the ONE unambiguous definition. 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. 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. If we ran such an experiment, what fraction do you think would serve to convince Guido that a dict 'ordered' by your definition is necessary in Python 2.5's standard library (presumably in module 'collections')? Alex -- http://mail.python.org/mailman/listinfo/python-list
Why are there no ordered dictionaries?
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.lang.python/msg/e652d2f771a49857 Are there plans to get it into the standard lib sometime? -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] 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? What answers have you received that have not been satisfactory? Some possible answers: The native dict is very fast, partly because the implementation doesn't need to ensure any particular ordering. Ordering the keys isn't the normal case, and can be done easily when needed. You asked why not rather than has anyone done this anyway; if you asked the latter of the Python Cookbook, you might find something like this: URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747 A little old, and pre-dates subclassable native types, but quite serviceable. 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. In what cases do you find yourself needing a dict that preserves its key order? Can you present a use case that would be improved by an ordered dict? I fully agree with the following posting where somebody complains why so very basic and useful things are not part of the standard library: For my part, I consider it a virtue of Python that the standard library doesn't change rapidly. It allows many competing implementations to be shaken out before everyone starts depending on any one of them. Are there plans to get it into the standard lib sometime? Where to find an answer: URL:http://www.python.org/peps/pep-.html Where to change that answer: URL:http://www.python.org/peps/pep-0001.html -- \ One of the most important things you learn from the internet | `\ is that there is no 'them' out there. It's just an awful lot of | _o__) 'us'. -- Douglas Adams | Ben Finney -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Uzytkownik Christoph Zwerschke [EMAIL PROTECTED] napisal w wiadomosci news:[EMAIL PROTECTED] 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.lang.python/msg/e652d2f771a49857 Are there plans to get it into the standard lib sometime? -- Christoph i am not sure what is the purpose of having ordered dictionaries built in python, could u provide any examples? i use a contruction: for x in sorted(d.keys()) cheers, przemek -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
przemek drochomirecki wrote:
i am not sure what is the purpose of having ordered dictionaries built in
python, could u provide any examples?
i use a contruction:
for x in sorted(d.keys())
By ordered dict, one usually wants order that is arbitary which cannot
be derived from the content, say insertion order(most ordered dict I
saw use this order).
I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting etc.), like this :
d = {'a':{...}, 'b':{}}
This dict would be passed to the Kid template system which would lay it
out into a HTML form. For quick and dirty forms, I don't want to code
each field individually in the HTML template but just from top to
bottom(or left to right for a table) with a for loop.
However, I still want to group certain fields together. This is my need
of an ordered dict. Or course, I can pass a list along with the dict
and loop over the list and retrieve value from the dict, but that would
mean another things to pass along. And given the constraint of Kid
where everything must be one-liner(expression, no block of code), it
makes thing a bit harder.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] wrote:
I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting etc.), like this :
d = {'a':{...}, 'b':{}}
This dict would be passed to the Kid template system which would lay it
out into a HTML form. For quick and dirty forms, I don't want to code
each field individually in the HTML template but just from top to
bottom(or left to right for a table) with a for loop.
However, I still want to group certain fields together. This is my need
of an ordered dict.
huh? if you want a list, use a list.
d = [('a', {...}), ('b', {})]
/F
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh wrote:
[EMAIL PROTECTED] wrote:
I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting etc.), like this :
d = {'a':{...}, 'b':{}}
This dict would be passed to the Kid template system which would lay it
out into a HTML form. For quick and dirty forms, I don't want to code
each field individually in the HTML template but just from top to
bottom(or left to right for a table) with a for loop.
However, I still want to group certain fields together. This is my need
of an ordered dict.
huh? if you want a list, use a list.
d = [('a', {...}), ('b', {})]
Didn't I say that for quick and dirty form(usually first draft), I want
a list ? But the same template, it would(may) be further enhanced by
graphic designers in which case, I need direct access to the field
names, thus the dict property.
In this way, I don't have to change the python code just because I
change the presentation in the template.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
You asked why not rather than has anyone done this anyway; if you asked the latter of the Python Cookbook, you might find something like this: URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/107747 A little old, and pre-dates subclassable native types, but quite serviceable. Here's a more recent and tested one, by yours truly (and Michael Foord): An Ordered Dictionary http://www.voidspace.org.uk/python/odict.html -- Nicola Larosa - [EMAIL PROTECTED] How wonderful the world would be if his behaviour and attitude was the default among rich people - using his money with a vision to improve the world, instead of getting 8 sportcars and a larger penis. -- barkholt on Slashdot, October 2005, referring to Mark Shuttleworth -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
What answers have you received that have not been satisfactory? I googled a little bit and haven't found many answers at all. Some were in the posting I mentioned: Stuff should go into the standard lib only when it is mature and right enough. However, we are already at Python 2.4 and there is still no ordered dictionary, though there is a lot of other specialized stuff. Some possible answers: The native dict is very fast, partly because the implementation doesn't need to ensure any particular ordering. Ok, but that's not an argument against providing ordered dictionaries as well. 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 asked why not rather than has anyone done this anyway; if you asked the latter of the Python Cookbook, you might find something like this. Yes, I also found that others have done it more than once, and I know that it's not so difficult to do. There are at least two recipes in the mentioned cookbook and there is odict in pythonutils. The question was why is it not available in the *standard* lib. In what cases do you find yourself needing a dict that preserves its key order? Can you present a use case that would be improved by an ordered dict? There are too many different situations and it would be too much to explain them here, usually in the case mentioned above where the keys are not sorted alphabetically. I often solve them by using two data structures, a list or tuple, plus a dictionary. For instance, the list could contain the names of database fields which shall be output in a certain order, and the dictionary values could contain human readable description of the database fields for headers or something. Instead of maintaining both data structures I feel it would be more natural to use only one ordered dictionary. For my part, I consider it a virtue of Python that the standard library doesn't change rapidly. It allows many competing implementations to be shaken out before everyone starts depending on any one of them. Ok, but this can be used as an argument to not add anything to the standard lib any more. There are already enough competing implementations. Also, the implementation details are not so important, there must be only agreement on the interface and behavior which should not be so difficult in this case. I simply wanted to ask why it is not available in the standard lib, since I simply don't know - has it not been demanded loud enough? - is it really not needed (if you need it it shows you are doing something wrong)? - because nobody presented a satisfying implementation yet? - are there hidden difficulties or controversial issues? -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] schrieb:
By ordered dict, one usually wants order that is arbitary which cannot
be derived from the content, say insertion order(most ordered dict I
saw use this order).
I am writing a web applications(simple forms) which has a number of
fields. Each field naturally has a name and a number of
attributes(formatting etc.), like this :
d = {'a':{...}, 'b':{}}
Things like that are also my typical use case. The keys usually contain
things like database fields or html form fields, the values contain the
corresponding description, formatting, data type or data itself etc.
The example above is a bit misleading, because using 'a', 'b' as keys
can give the impression that you just have to sort() the keys to have
what you want. So let's make it more realistic:
d = { 'pid': ('Employee ID', 'int'),
'name': ('Employee name', 'varchar'),
'sal': ('Salary', 'float') }
Now if I want these things to be presented in this order, I need to run
through a separate list ('pid', 'name', 'sal') that holds the order.
Ok, you could simply use a list instead of a dictionary:
d = ( ('pid', 'Employee ID', 'int'),
('name', 'Employee name', 'varchar'),
('sal', 'Salary', 'float') )
This works as long as you *only* have to go through the list
sequentially. But maybe you want to print the name with its description
at some other place as well. Now how do you access its description
'Employee name' so easily?
-- Christoph
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[restored my attribution line so we know who said what] Christoph Zwerschke [EMAIL PROTECTED] wrote: Ben Finney wrote: In what cases do you find yourself needing a dict that preserves its key order? Can you present a use case that would be improved by an ordered dict? There are too many different situations and it would be too much to explain them here, usually in the case mentioned above where the keys are not sorted alphabetically. Without an example, it's hard to know what you want to do and whether an ordered dictionary is the best way to do it. For my part, I consider it a virtue of Python that the standard library doesn't change rapidly. It allows many competing implementations to be shaken out before everyone starts depending on any one of them. Ok, but this can be used as an argument to not add anything to the standard lib any more. I hope not. Rather, it's an argument not to add something to the standard library until it's proven (to the BDFL's criteria) that it's better in than out. There are already enough competing implementations. Have they been sufficiently shaken out to show a clearly superior version? Is any version sufficiently beneficial to write a PEP for its inclusion in the standard library? I simply wanted to ask why it is not available in the standard lib, since I simply don't know - has it not been demanded loud enough? Loud demands don't count for much. PEPs with popular working implementations do. - is it really not needed (if you need it it shows you are doing something wrong)? You dismissed a request for your use cases with handwaving. How can we know? - because nobody presented a satisfying implementation yet? I'm not sure what you mean by satisfying. - are there hidden difficulties or controversial issues? Another possibility: ordered dictionaries are not needed when Python 2.4 has the 'sorted' builtin. -- \ Those who will not reason, are bigots, those who cannot, are | `\ fools, and those who dare not, are slaves. -- Lord George | _o__)Gordon Noel Byron | Ben Finney -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote:
The example above is a bit misleading, because using 'a', 'b' as keys
can give the impression that you just have to sort() the keys to have
what you want. So let's make it more realistic:
d = { 'pid': ('Employee ID', 'int'),
'name': ('Employee name', 'varchar'),
'sal': ('Salary', 'float') }
Now if I want these things to be presented in this order, I need to run
through a separate list ('pid', 'name', 'sal') that holds the order.
Ok, you could simply use a list instead of a dictionary:
d = ( ('pid', 'Employee ID', 'int'),
('name', 'Employee name', 'varchar'),
('sal', 'Salary', 'float') )
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
for key, (name, type) in d:
print key, name, type # e.g. generate form entry
This works as long as you *only* have to go through the list
sequentially. But maybe you want to print the name with its description
at some other place as well. Now how do you access its description
'Employee name' so easily?
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...
/F
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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. Of course there are more than one way to skin a cat(well it may be against the general idiom of python) but in some situation certain way is preferred. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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.
I also wanted to mention the uglyness in the definition (nested tuples),
but then I understood that even an ordered dictionary would not
eliminate that uglyness, since the curly braces are part of the Python
syntax and cannot be used for creating ordered dictionaries anyway. I
would have to define the ordered dictionary in the very same ugly way:
d = odict(('pid', ('Employee ID', 'int')),
('name', ('Employee name', 'varchar')),
('sal', ('Salary', 'float')))
(Unless the Python syntax would be extend to use double curly braces or
something for ordered dictionaries - but I understand that this is not
an option.)
-- Christoph
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ben Finney wrote: Another possibility: ordered dictionaries are not needed when Python 2.4 has the 'sorted' builtin. What does sorted() have anythng to do with orders like insertion order, or some arbitary order that instead of a,b,c,d,e, I want it as e, c, b, d, a ? 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. What I think is better is like the itertools recipe of giving example of how one can make their own based on the needs. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ben Finney wrote: Without an example, it's hard to know what you want to do and whether an ordered dictionary is the best way to do it. I have indicated an example, discussed in more detail in another subthread. There are already enough competing implementations. Have they been sufficiently shaken out to show a clearly superior version? Is any version sufficiently beneficial to write a PEP for its inclusion in the standard library? At least it shows I'm not the only one who thinks ordered dictionaries may be sometimes nice to have. I simply wanted to ask why it is not available in the standard lib, since I simply don't know - has it not been demanded loud enough? Loud demands don't count for much. PEPs with popular working implementations do. Sorry, I did not mean loud enough but often enough. The same what you are calling popular. - because nobody presented a satisfying implementation yet? I'm not sure what you mean by satisfying. You can take your own definition: sufficiently shaken out, working, popular, and succifiently beneficial and proven (to the BDFL's criteria). Another possibility: ordered dictionaries are not needed when Python 2.4 has the 'sorted' builtin. The 'sorted' function does not help in the case I have indicated, where I do not want the keys to be sorted alphabetically, but according to some criteria which cannot be derived from the keys themselves. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: [EMAIL PROTECTED] 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. Do you have an example for different options of behavior? As mentioned, most ordered dict I saw is insertion order based. I assume that is the need of their creators. But that is not my need, so there are at least two behaviour. What I need is a preferred order. Say if I have designed a web form(correspond to a database table), I just want say 3 fields that goes before anything else in the presentation. The rest I don't care as the DBA may create more fields later which I don't want to then update my code yet again. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] 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. Do you have an example for different options of behavior? -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
...
there are at least two behaviour. What I need is a preferred order.
Say if I have designed a web form(correspond to a database table), I
just want say 3 fields that goes before anything else in the
presentation. The rest I don't care as the DBA may create more fields
later which I don't want to then update my code yet again.
preferred_fields = ['foo', 'bar', 'baz']
def process_preferred_fields():
global preferred_fields
temp = {}
for i, field in enumerate(preferred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_fields = temp
process_preferred_fields()
del process_preferred_fields
def sort_key(akey, preferred_fields=preferred_fields):
return preferred_fields.get(akey, akey)
del preferred_fields
## ...build dictionary d...
# now output d...:
for k in sorted(d, key=sort_key):
print k, d[k]
Season to taste if you want non-preferred fields emitted other than
alphabetically, or if you want to wrap this stuff into a class, etc.
(Note: untested code, so typos c are quite possible). This assumes
that no 'real' key is a non-string, and no 'real' key starts with
chr(0), but it's quite easy to tweak for slightly different specs (at
worst by defining a custom type designed to always compare less than any
real key, and wrapping the preferred_fields entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_fields of the key they're wrapping, etc etc).
Alex
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] wrote: ... 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 I think you're wrong here. People in the past who have requested or implemented stuff they called 'ordered dicts' in the past had in mind drastically different things, based on some combination of insertion orders, keys, and _values_. So, ambiguity is definitely present in the phrase 'ordered dictionary', because there are so many different criteria whereby the 'ordering' could take place. Note the plural in 'insertion orderS': some people care about the FIRST time a key was added to a dict, some about the LAST time it was added, some about the latest time it was 'first inserted' (added and wasn't already there) as long as it's never been deleted since that occasion -- and these are just a few of the multifarious orders based on the time of insertions and deletions of keys. The number of variations is staggering, e.g., consider x['a'] = 1 x['b'] = 2 x['a'] = 1 in some applications you'd want to have 'b' come before 'a' because the last time of addition was earlier for 'b' -- but in others you might want 'a' first because the latest addition wasn't really one, since it didn't really change anything (because the value inserted was the same as the one already there -- it would be different, for those other apps, if the RHS of the third assignment was 0 rather than 1...). To get 'ordered dicts' into Python, you have to identify ONE unambiguous definition which has a large-enough number of use-cases, possibly customizable through some reasonably SIMPLE combination of flags and a callable or two, like the 'sorted' built-in has a 'reversed' flag and 'key' and 'cmp' optional callables. Expect a lot of flak from those who have been pining for an 'ordered dict' which does NOT match your one unambiguous definition...;-) If the field of use cases for 'ordered dicts' is just too fragmented, it's quite possible that it's best not to have any single kind built-in, even though, could all different use cases be combined (which by hypothesis is unfeasible), critical mass would be reached... Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] wrote: ... The 'sorted' function does not help in the case I have indicated, where I do not want the keys to be sorted alphabetically, but according to some criteria which cannot be derived from the keys themselves. Ah, but WHAT 'some criteria'? There's the rub! First insertion, last insertion, last insertion that wasn't subsequently deleted, last insertion that didn't change the corresponding value, or...??? Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] writes: Ben Finney wrote: Another possibility: ordered dictionaries are not needed when Python 2.4 has the 'sorted' builtin. The 'sorted' function does not help in the case I have indicated, where I do not want the keys to be sorted alphabetically, but according to some criteria which cannot be derived from the keys themselves. And how would an ordered dictionary help in this case? mike -- Mike Meyer [EMAIL PROTECTED] http://www.mired.org/home/mwm/ Independent WWW/Perforce/FreeBSD/Unix consultant, email for more information. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli wrote:
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
...
there are at least two behaviour. What I need is a preferred order.
Say if I have designed a web form(correspond to a database table), I
just want say 3 fields that goes before anything else in the
presentation. The rest I don't care as the DBA may create more fields
later which I don't want to then update my code yet again.
preferred_fields = ['foo', 'bar', 'baz']
def process_preferred_fields():
global preferred_fields
temp = {}
for i, field in enumerate(preferred_fields):
temp[field] = '%s%s' % (chr(0), chr(i))
preferred_fields = temp
process_preferred_fields()
del process_preferred_fields
def sort_key(akey, preferred_fields=preferred_fields):
return preferred_fields.get(akey, akey)
del preferred_fields
## ...build dictionary d...
# now output d...:
for k in sorted(d, key=sort_key):
print k, d[k]
Season to taste if you want non-preferred fields emitted other than
alphabetically, or if you want to wrap this stuff into a class, etc.
(Note: untested code, so typos c are quite possible). This assumes
that no 'real' key is a non-string, and no 'real' key starts with
chr(0), but it's quite easy to tweak for slightly different specs (at
worst by defining a custom type designed to always compare less than any
real key, and wrapping the preferred_fields entry in instances of that
custom type... having such instances compare with each other based on
the index within preferred_fields of the key they're wrapping, etc etc).
Thanks. For me, I don't need such complex thing, it is just like :
d = somedict_from_db()
prefer=['f','a',b']
def my_order(d):
for x in prefer:
if x in d: yield x
s = frozenset(prefer)
for x in d:
if x not in s: yield x
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] 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. You mean, like SQLite does? (http://www.sqlite.org/datatypes.html) -Peter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Peter Hansen wrote: [EMAIL PROTECTED] 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. You mean, like SQLite does? (http://www.sqlite.org/datatypes.html) Yup, they are using similar logic. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke [EMAIL PROTECTED]
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
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: On Sun, 20 Nov 2005 22:03:34 +0100, Christoph Zwerschke [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] [EMAIL PROTECTED] 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. URL:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234 -- \ Experience is that marvelous thing that enables you to | `\ recognize a mistake when you make it again. -- Franklin P. | _o__)Jones | Ben Finney -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ben Finney wrote: [EMAIL PROTECTED] [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
