Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Hello Christoph, I think re-ordering will be a very rare use case anyway and slicing even more. As a use case, I think of something like mixing different configuration files and default configuration parameters, while trying to keep a certain order of parameters and parameters blocks. In actual fact - being able to *reorder* the dictionary is the main way I use this dictionary. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Hmmm... it would be interesting to see if these tests can be used with odict. The odict implementation now has full functionality by the way. Optimisations to follow and maybe a few *minor* changes. Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
The semantics of assigning slices to d.keys[i:j] and d.values[i:j] are kind of tricky when the size changes and/or key names match or don't match in various ways, or the incoming data represents collapsing redundant keys that are legal sequential assignment overrides but change the size, etc. I have come against the same problem with slice assignment, when doing odict. :-) Allowing the size to change prevents a useful optimisation - but I dislike *preventing* programmers from doing things. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 1 Dec 2005 03:53:27 -0800, Fuzzyman [EMAIL PROTECTED] wrote:
Hmmm... it would be interesting to see if these tests can be used with
odict.
I assume you are referring to the pytest tests I posted, though I would
need some of the context you snipped to me more sure ;-)
Anyway, with some changes[1], they can.
The odict implementation now has full functionality by the way.
The one at
http://www.voidspace.org.uk/cgi-bin/voidspace/downman.py?file=odict.py
? It seems to be unchanged.
Optimisations to follow and maybe a few *minor* changes.
Anyway, test of the above results in:
C:\UTIL\\..\py.test test
= test process starts =
testing-mode: inprocess
executable: d:\python-2.4b1\mingw\python24.exe (2.4.0-beta-1)
using py lib: D:\bpy24\py-0.8.0-alpha2\py rev unknown
test\test_odicts.py[28] FF...FF....FFF..
test\test_odicts_candidate.py[0]
___
___ entrypoint: test_sanity ___
def test_sanity():
d = CandidateDict()
assert d.keys() == []
assert d.values() == []
assert d.items() == []
assert d == d
d = CandidateDict([(k,i*100) for i,k in enumerate('abcde')])
E assert repr(d) == %s([('a', 0), ('b', 100), ('c', 200), ('d', 300),
('e', 400)])%Can
dateDict.__name__
assert {'a': 0, 'b': 100, 'c': 200, 'd': 300, 'e': 400} ==
(%s([('a', 0), ('b', 100
('c', 200), ('d', 300), ('e', 400)]) % CandidateDict.__name__)
+ where {'a': 0, 'b': 100, 'c': 200, 'd': 300, 'e': 400} =
repr({'a': 0, 'b': 100,
c': 200, 'd': 300, 'e': 400})
[C:\pywk\ut\test\test_odicts.py:19]
___
Apparently you are still using plain dict repr format, not a format that could
(ideally) be exec'd
to reconstitute the thing repr'd.
from clp.odict import OrderedDict as CandidateDict
CandidateDict.__name__
'OrderedDict'
repr(CandidateDict())
'{}'
vs
from ut.creordict import Creordict as CandidateDict
CandidateDict.__name__
'Creordict'
repr(CandidateDict())
'Creordict([])'
Since the test uses CandidateDict.__name__, it should work either way.
__ entrypoint: test___init__ __
def test___init__():
d = CandidateDict()
assert d.keys() == []
assert d.values() == []
assert d.items() == []
assert d == d
d = CandidateDict([(k,i*100) for i,k in enumerate('abcde')])
E assert repr(d) == %s(%r)% (CandidateDict.__name__, d.items())
assert {'a': 0, 'b': 100, 'c': 200, 'd': 300, 'e': 400} == ('%s(%r)'
% ('OrderedDict
[('a', 0), ('b', 100), ('c', 200), ('d', 300), ('e', 400)]))
+ where {'a': 0, 'b': 100, 'c': 200, 'd': 300, 'e': 400} =
repr({'a': 0, 'b': 100,
c': 200, 'd': 300, 'e': 400})
[C:\pywk\ut\test\test_odicts.py:32]
___
(Duplicate from test_sanity)
entrypoint: test___delitem__ _
def test___delitem__():
d = CandidateDict([(k,i*100) for i,k in enumerate('abcde')])
print mkresult('abcde')
assert d == mkresult('abcde')
ditems = d.items()
print d['b']
print d.items()
del d['b']
assert d == mkresult('acde')
del d['a']
assert d == mkresult('cde')
del d['e']
assert d == mkresult('cd')
d = CandidateDict([(k,i*100) for i,k in enumerate('abcde')])
del d[1:3]
[C:\pywk\ut\test\test_odicts.py:70]
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
def __delitem__(self, key):
d = OrderedDict(((1, 3), (3, 2), (2, 1)))
del d[3]
d
{1: 3, 2: 1}
del d[3]
Traceback (most recent call last):
KeyError: 3
# do the dict.__delitem__ *first* as it raises
# the more appropriate error
E dict.__delitem__(self, key)
TypeError: unhashable type
[c:\pywk\clp\odict.py:137]
- - - - - - - - - - - test___delitem__: recorded stdout - - - - - - - - - - -
{'a': 0, 'b': 100, 'c': 200, 'd': 300, 'e': 400}
100
[('a', 0), ('b', 100), ('c', 200), ('d', 300), ('e', 400)]
___
You don't appear to accept slice operation syntax directly on the instance
__ entrypoint: test___repr__ __
def test___repr__():
E assert repr(CandidateDict()) == '%s([])'%CandidateDict.__name__
assert '{}' == ('%s([])' % CandidateDict.__name__)
+ where '{}' = repr({})
+where {} = CandidateDict()
Re: Why are there no ordered dictionaries?
On 1 Dec 2005 01:48:56 -0800, Fuzzyman [EMAIL PROTECTED] wrote: Christoph Zwerschke wrote: Hello Christoph, I think re-ordering will be a very rare use case anyway and slicing even more. As a use case, I think of something like mixing different configuration files and default configuration parameters, while trying to keep a certain order of parameters and parameters blocks. In actual fact - being able to *reorder* the dictionary is the main way I use this dictionary. Curious as to usage patterns 1) how many instances created, deleted 2) how many elements in an instance min, max? 3) how often updated? 3a) just ordering, no value or size change? 3b) just value change, no order or size change? 3c) changes involving size? 4) proportions of read vs write/delete/reorder accesses? Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Sun, 27 Nov 2005 12:00:23 +0100, Christoph Zwerschke [EMAIL PROTECTED] wrote: Bengt Richter wrote: d.keys[:] = newkeyseq Do you really mean just re-ordering the keys without a corresponding reording of values?? That would be a weird renaming of all values. Or do you means that any key should still retrieve the same value as before if used as d[key]? In which case the values must undergo the same permutation as the keys. I.e., you are assuming key-value pairings remain stable through any key reorderings? Since it is considered as being a dictionary in the first place, the key-value pairings should of course stay stable. In the usual implementation based on an ordinary dictionary with an additional key list (sequence in the Foord/Larosa and _keys in the Bejamin/Winter implementation), you would only set the key list, since the value list is generated dynamically. But if your implementation keeps internal values or items lists, these need to be adjusted as well. I will assume that d has is a Foord/Larosa ordered dict with sequence attribute in the following. Then, with other words, d.keys[:] = newkeyseq should do the same as: d.sequence = newkeyseq Exactly what, though? should e.g. d.keys[3] = newk3 mean (not a suggested implementation, just to define semantics) keys = d.keys() if newk3 in keys and keys.index(newk3)!=3: raise ValueError,'Attempt to introduce duplicate key' items = d.items() items[3] = (newk3, items[3][1]) d.clear() d.update(items) Yes, that would be the correct semantics. Of course this should not be the real implementation and use KeyError instead of ValueError. With other words, d.keys[i] = newkey sould be the same as: if d.sequence[i] != newkey: if newkey in d.sequence: raise KeyError,'Attempt to introduce duplicate key' else: d.sequence[i] = newkey This would allow what you might call renaming in place. Similarly d.keys[i:j] = newkeysij might have the semantics of keys = d.keys() outside = set(keys[:i])+set(keys[j:]) if outside set(newkeysij) or len(newkeysij) != len(set(newkeysij)): raise ValueError,'Attempt to introduce duplicate key(s)' items = d.items() items[i:j] = [(k, items[kx+i][1]) for kx,k in enumerate(newkeysij)] d.clear() d.update(items) Is this what is desired? Not quite, because it does not preserve the key-value pairings (see above) and it would behave strangely or raise an exception if the new slice is larger. The following code would do: keys = d.keys() outside = set(keys[:i])|set(keys[j:]) if outside set(newkeysij) or len(newkeysij) != len(set(newkeysij)): raise ValueError,'Attempt to introduce duplicate key(s)' items = d.items() items[i:j] = [(k, d.get(k, None)) for k in newkeysij] d.clear() d.update(items) (Note that there was a bug in the second line. You cannot add sets.) Oops, thinking about adding dicts ;-) Again, this would be equivalent to: seq = d.sequence newseq = seq[:] newseq[i:j] = newkeysij if len(newseq) != len(set(newseq)): raise KeyError,'Attempt to introduce duplicate key(s)' for k in set(seq[i:j]) - set(newkeysij): del d[k] for k in set(newkeysij) - set(seq[i:j]): d[k] = None d.sequence = newseq You don't keep track of the item lists, they need to be built on every occasion. That depends on how you implement ;-) Ok, I was thinking of the usual implementations. Back from holiday, so maybe I'll hack something out. Let us know when you have something to check out. Maybe Fuzzyman can make some moderate improvements to the existing odict.py, and you can do something more radical. Then we have two reference implementations and can compare how they prove regarding performance and usability. My code so far is a kludge to get functionality. Perhaps we can arrive at a spec by doing some TDD. My current kludge passes these tests (run by py.test which I downloaded from the pypy project site and made work (apparanently ;-) with IIRC a .pth file to point to py where I expanded the zip, and a cmd file to kick of python running py.test, and I think that was all there was. As you can see, it is super easy to define tests. If you want to try it, I think I can retrace my steps and describe the way I set it up (for windows NT) in a few turgid run-on paragraphs ;-) Maybe I'll get around to writing a downloading/checking/installing script for it, with a few interactive are-you-sure?'s and file tree placement options etc. I'm calling it a Creordict for now -- Created-order-dict. Here are the tests so far. Do you want to add some to refine what's supposed to happen. You may want to look at test_items, test_keys, test_values as those are the ones that provide d.items(), d.items[i], d.items[i:j] style accesses, with assign, eval, and del available for the latter two. also test___getitem__ for d[i] = value normal key access vs d[i:j] = another Creordict
Re: Why are there no ordered dictionaries?
I had the same idea to create a py.test to verify and compare various implementations. The doctests in odict.py are nice, but you can't use them for this purpose and they may not test enough. It would be also good to have something for testing and comparing performance. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 29 Nov 2005 23:30:45 +0100, Christoph Zwerschke [EMAIL PROTECTED] wrote: I had the same idea to create a py.test to verify and compare various implementations. The doctests in odict.py are nice, but you can't use them for this purpose and they may not test enough. It would be also good to have something for testing and comparing performance. Well, the previous post test file just grew to make a simple check for various aspects, so it's not super clean. I just grepped for defs in the implementation and bulk appended test_ to make an empty starting point. Then I just filled in tests after a preliminary sanity check test. But there are some things that could still accidentally be inherited from the base class when builtin utility functions are called on the dict object. Also there's a lot of cut-paste duplication an no full explorations of corner cases. There's neat generator-based test driving with different parameters that I didn't take advantage of, etc. etc. I should really read the py test docs and learn to use it better if I am going to use it. But anyway, it's a qd hack to show and sanity-check different usages. The semantics of assigning slices to d.keys[i:j] and d.values[i:j] are kind of tricky when the size changes and/or key names match or don't match in various ways, or the incoming data represents collapsing redundant keys that are legal sequential assignment overrides but change the size, etc. One could add keyword args to the constructor to vary key eq and cmp used on keys to determine key collisions between e.g. tuple keys and also for sort. You could even allow partially non-hashable keys that way if you got tricky. But maybe this is getting too tricky ;-) I'll make some simple mods to the test to allow applying it to arbitrary candidate implementations with different names and directory locations, so I can try it on odict.py and other versions. But are the semantics right? Doctest is handy, and in some ways I like examples showing up in the help docs, but maybe help should take a keyword arg to select showing them (and some other things too perhaps. A brief version excluding a lot of inheritance for classes might be nice. Or a pattern for method and class var inclusion. But I like the separation of the py.test tests with no need to mod the original. Where next? This ordered dict thing is kind of a side-track from a side-track for me ;-) Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: d.keys[:] = newkeyseq Do you really mean just re-ordering the keys without a corresponding reording of values?? That would be a weird renaming of all values. Or do you means that any key should still retrieve the same value as before if used as d[key]? In which case the values must undergo the same permutation as the keys. I.e., you are assuming key-value pairings remain stable through any key reorderings? Since it is considered as being a dictionary in the first place, the key-value pairings should of course stay stable. In the usual implementation based on an ordinary dictionary with an additional key list (sequence in the Foord/Larosa and _keys in the Bejamin/Winter implementation), you would only set the key list, since the value list is generated dynamically. But if your implementation keeps internal values or items lists, these need to be adjusted as well. I will assume that d has is a Foord/Larosa ordered dict with sequence attribute in the following. Then, with other words, d.keys[:] = newkeyseq should do the same as: d.sequence = newkeyseq Exactly what, though? should e.g. d.keys[3] = newk3 mean (not a suggested implementation, just to define semantics) keys = d.keys() if newk3 in keys and keys.index(newk3)!=3: raise ValueError,'Attempt to introduce duplicate key' items = d.items() items[3] = (newk3, items[3][1]) d.clear() d.update(items) Yes, that would be the correct semantics. Of course this should not be the real implementation and use KeyError instead of ValueError. With other words, d.keys[i] = newkey sould be the same as: if d.sequence[i] != newkey: if newkey in d.sequence: raise KeyError,'Attempt to introduce duplicate key' else: d.sequence[i] = newkey This would allow what you might call renaming in place. Similarly d.keys[i:j] = newkeysij might have the semantics of keys = d.keys() outside = set(keys[:i])+set(keys[j:]) if outside set(newkeysij) or len(newkeysij) != len(set(newkeysij)): raise ValueError,'Attempt to introduce duplicate key(s)' items = d.items() items[i:j] = [(k, items[kx+i][1]) for kx,k in enumerate(newkeysij)] d.clear() d.update(items) Is this what is desired? Not quite, because it does not preserve the key-value pairings (see above) and it would behave strangely or raise an exception if the new slice is larger. The following code would do: keys = d.keys() outside = set(keys[:i])|set(keys[j:]) if outside set(newkeysij) or len(newkeysij) != len(set(newkeysij)): raise ValueError,'Attempt to introduce duplicate key(s)' items = d.items() items[i:j] = [(k, d.get(k, None)) for k in newkeysij] d.clear() d.update(items) (Note that there was a bug in the second line. You cannot add sets.) Again, this would be equivalent to: seq = d.sequence newseq = seq[:] newseq[i:j] = newkeysij if len(newseq) != len(set(newseq)): raise KeyError,'Attempt to introduce duplicate key(s)' for k in set(seq[i:j]) - set(newkeysij): del d[k] for k in set(newkeysij) - set(seq[i:j]): d[k] = None d.sequence = newseq You don't keep track of the item lists, they need to be built on every occasion. That depends on how you implement ;-) Ok, I was thinking of the usual implementations. Back from holiday, so maybe I'll hack something out. Let us know when you have something to check out. Maybe Fuzzyman can make some moderate improvements to the existing odict.py, and you can do something more radical. Then we have two reference implementations and can compare how they prove regarding performance and usability. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: I will assume that d has is a Foord/Larosa ordered dict with sequence attribute in the following. Then, with other words, d.keys[:] = newkeyseq should do the same as: d.sequence = newkeyseq At least in the case where newkeyseq is a permutation of d.sequence. Otherwise, it should behave like the given implementation for setting slices, i.e. - if newkeyseq has duplicate elements, an exception should be raised. - if newkeyseq has elements not in d.sequence, then the dictionary should be updated with corresponding None values - if d.sequence has elements not in newkeyseq then these elements should be deleted from the dictionary -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Note that I've done two things with the Foord/Larosa dict. ;-) I've implemented slicing, including slice assignment and deletion. I've also 'hidden' ``sequence``, but you can pass arguments to keys, values and items. I've done a second (experimental) implementation of a custom keys object. This is effectively the managed list - which you can call as a method or mutate in place. You can't delete members from 'keys' but you can do slice assignment so long as the sequence you're replacing is the same length (and is a re -ordering of the set being replaced). I'll post it on Monday, and if people like it I'll complete it. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter schrieb:
OTOH,
{}[:]
Traceback (most recent call last):
File stdin, line 1, in ?
TypeError: unhashable type
I.e., slices are not valid keys for ordinary dicts, and slices tie in
very well with the ordered aspect of ordered dicts, so that's an
argument for permitting it via the indexing syntax, not just items[:]
or items()[:] which have related but not identical semantics.
I see it like that. BTW, the above error message is pretty bad.
I wonder who is going to use it for what.
I think re-ordering will be a very rare use case anyway and slicing even
more. As a use case, I think of something like mixing different
configuration files and default configuration parameters, while trying
to keep a certain order of parameters and parameters blocks.
-- Christoph
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Thu, 24 Nov 2005 18:42:45 +0100, Christoph Zwerschke [EMAIL PROTECTED]
wrote:
Bengt Richter schrieb:
d.setvalues((13, 14)) == d = OrderedDict((1, 13), (2, 14))
The implication above is that OrderedDict takes an *args argument,
but really it takes a single argument that is a sequence of k,v pairs,
(and maybe some keyword options).
Right. Interpret it as a short notation only, I did not want to change
the interface. I think it's a common mistake to forget the brackets
because you think one pair should be enough. At least I often forget it.
Ok, I forget this too.
You could make keys, values, and items custom descriptors which would define
__call__
for the old key() etc accesses, well as __getitem__ and __setitem__. Then
you could write
d.items[0], d.items[-1] = d.items[-1], d.items[0]
to swap the order of the first and last items in the thing (I hesitate to
say dict ;-)
You could also operate on slices.
Nice. You could also get the i-th value with d.values[i].
But is this considered good style or would it be considered dirty to
have a callable member that also supports indexing and slicing? (I don't
know, just asking?) Plus, it opens a can of worms by increasing the
complexity tremendously. Let's see whether this can be handled.
I suspect not that complex, but it has the same performance disadvantage as
properties.
BTW, before I showed an example where d[2:3] returned
a new dict instance rather than d.items()[:]. I think the items list
is better, since they naturally add, sort, reverse, etc as lists,
and you can write OrderedDict(d[2:3]+d[1:2]) if you want a new dict.
Not sure about that. I would rather expect that if you slice an object,
you get an object of the same type. And you can also add, sort, reverse,
etc the ordered dict if you want.
A slice assignment to d[i:j] is really sugar for something, but we have to
decide exactly
what in case of duplicate keys in the incoming items, either with each other
...
You mean slice assignments to d.items[i:j]. If you make the slice
assignment to d[i:j] then at least you cannot have conflicts in the
incoming items. The first question is: Should a slice assignment be
treated as deletion with subsequential addition (changing the order) or
as a replacement (i.e. try to not change the order)? I agree that the
second would be the expected semantics, but as you mentioned more
difficult to implement.
One way to define it would be
d.items[i:j] = itemseq
to be implemented as sugar for
newitems = d.items[:i] + list(itemseq) + d.items[j:]
d.clear()
d.update(newitems)
Which should be the same as
d = OrderedDict(d.items[:i] + list(itemseq) + d.items[j:])
Sounds reasonable.
Actually it's not the same, which is why I wrote it with update.
Analogous to slice assignment in lists, the referred-to object
gets mutated. Hence preexisting references to the object see the change too.
If you just rebind d with a new OrderedDict object, previous bindings
are not affected. I.e.,
d = OrderedDict(sorted((k,i)) for i,k in enumerate('abc'))
e = d
d = OrderedDict(d.items[:1] + [('b', 100)] + d.items[2:])
d.items()[1] # = ('b', 100)
e.items()[1] # = ('b', 1) # unaffected
So
d.reverse()
could be spelled
d.items[:] = d.items[::-1]
Slice assignment for keys and values would also allow to set a new key
order with
d.keys[:] = newkeyseq
Do you really mean just re-ordering the keys without a corresponding reording
of values??
That would be a weird renaming of all values. Or do you means that any key
should still
retrieve the same value as before if used as d[key]? In which case the values
must undergo
the same permutation as the keys. I.e., you are assuming key-value pairings
remain stable
through any key reorderings?
So no need to define a setkeys() method or let keys() take arguments.
If we want to allow this kind of things at all.
If you are using slices, you can safely use them directly in the __getitem__
of th dict interface,
as I did in the Que mas? post. So we don't have to write d.items[i:j] and
could write d[i:j].
The thing is, d[i:j] will tempt to skip .items in d.items[i] and write
d[i], which has the dict
key meaning, not the item list index. It is faster not have a
descriptor between though.
I still think d[i:j] should return an ordered dict, not an item list.
Easy to do either way.
I think maybe allowing write to keys or values is pretty iffy. There are too
many weird
re-associations of keys and values possible, and which you could do my other
means if you
really really wanted to. But I do think full index and slice read access
would be fine.
There are different opinions. Fuzzyman would probably say Don't trust
yourself? I myself am undecided. Perhaps you could expect that somebody
knows what he does if he makes a slice assignment to d.keys. In any way,
such an assignment should not break the directory (with
Re: Why are there no ordered dictionaries?
On Fri, 25 Nov 2005 19:42:49 +, Tom Anderson [EMAIL PROTECTED] wrote:
On Wed, 23 Nov 2005, Carsten Haese wrote:
On Wed, 2005-11-23 at 15:17, Christoph Zwerschke wrote:
Bengt Richter wrote:
E.g., it might be nice to have a mode that assumes d[key] is
d.items()[k][1] when
key is an integer, and otherwise uses dict lookup, for cases where
the use
case is just string dict keys.
I also thought about that and I think PHP has that feature, but it's
probably better to withstand the temptation to do that. It could lead
to an awful confusion if the keys are integers.
Thus quoth the Zen of Python:
Explicit is better than implicit.
In the face of ambiguity, refuse the temptation to guess.
With those in mind, since an odict behaves mostly like a dictionary, []
should always refer to keys. An odict implementation that wants to allow
access by numeric index should provide explicitly named methods for that
purpose.
+1
Overloading [] to sometimes refer to keys and sometimes to indices is a
really, really, REALLY bad idea. Let's have it refer to keys, and do
indices either via a sequence attribute or the return value of items().
More generally, if we're going to say odict is a subtype of dict, then we
have absolutely no choice but to make the methods that it inherits behave
the same way as in dict - that's what subtyping means. That means not
doing funky things with [], returning a copy from items() rather than a
live view, etc.
OTOH,
{}[:]
Traceback (most recent call last):
File stdin, line 1, in ?
TypeError: unhashable type
I.e., slices are not valid keys for ordinary dicts, and slices tie in
very well with the ordered aspect of ordered dicts, so that's an
argument for permitting it via the indexing syntax, not just items[:]
or items()[:] which have related but not identical semantics.
So, how do we provide mutatory access to the order of items? Of the
solutions discussed so far, i think having a separate attribute for it -
like items, a live view, not a copy (and probably being a variable rather
than a method) - is the cleanest, but i am starting to think that
overloading items to be a mutable sequence as well as a method is quite
neat. I like it in that the it combines two things - a live view of the
order and a copy of the order - that are really two aspects of one thing,
which seems elegant. However, it does strike me as rather unpythonic; it's
trying to cram a lot of functionality in an unexpected combination into
one place. Sparse is better than dense and all that. I guess the thing to
do is to try both out and see which users prefer.
I wonder who is going to use it for what.
Regards,
Bengt Richter
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Fuzzyman schrieb: d.keys() will still return a copy of the list, so d.keys()[i] will still be slower than d.sequence[i] Right, I forgot that. Bengt suggested to implement __call__ as well as __getitem__ and __setitem__ for keys, values and items. In this case, you could very effectively access it as d.values[i]. That means making keys, values, and items custom objects. Creating a new instance would have the overhead of creating 4 new objects instead of just 1. Is the added convenience worth it ? (Plus the extra layers of method calls for each access). I'm not sure. It's a nice idea in terms of using it (we could just leave the sequence attribute as an alias for the new keys attribute - for backwards compatibility). All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Le ruego me perdone.
replace('haber', random.choice('tener', 'hacer', 'lograr'))
Mi espanol es peor que mi python.
-- Christoph
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Sure - that was just an example of mutating the keys list without having direct access to it. If keys was implemented as an object (with a ``__call__`` method) then we could also implement sequence methods on it - making it easier to mutate the keys/values/items directly. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli wrote: Fuzzyman [EMAIL PROTECTED] wrote: There is already an update method of course. :-) Slicing an ordered dictionary is interesting - but how many people are actually going to use it ? (What's your use case) I detest and abhor almost-sequences which can't be sliced (I consider that a defect of collections.deque). If the ordered dictionary records by its sequencing the time order of key insertion, being able to ask for the last 5 keys entered or the first 3 keys entered seem to me to be perfectly natural use cases, and most naturally accomplished by slicing of course, d[-5:] and d[:3] respectively. If you slice an ordered dictionary, I assume you would expect to get an ordered dictionary back ? Fuzzyman http://www.voidspace.org.uk/python/index.shtml Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Sure - that was just an example of mutating the keys list without having direct access to it. If keys was implemented as an object (with a ``__call__`` method) then we could also implement sequence methods on it - making it easier to mutate the keys/values/items directly. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman wrote: That means making keys, values, and items custom objects. Creating a new instance would have the overhead of creating 4 new objects instead of just 1. Is the added convenience worth it ? (Plus the extra layers of method calls for each access). I'm not sure about that either. But since you are using odict for convenience reasons anyway, and not for performance reasons, it would be consequential. Performance testing should be made anyway, so this could be tested as well. I think that creating these 3 additional objects will not matter much if the dict has more than a handful of items. And the extra layers will be only called if you really access these keys, values or items attributes which will not happen very frequently. Normally, you just loop over an ordered directory and acess keyed values. I'm not sure. It's a nice idea in terms of using it (we could just leave the sequence attribute as an alias for the new keys attribute - for backwards compatibility). Yes, you could make it a deprecated feature. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman [EMAIL PROTECTED] wrote: ... If you slice an ordered dictionary, I assume you would expect to get an ordered dictionary back ? That would be helpful, yes, though there are precedents for types whose slicing doesn't return an instance of that type (e.g. slices of an mmap are instances of str, not of mmap, if I recall correctly), most sliceable sequences do follow that pattern. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Wed, 23 Nov 2005, Christoph Zwerschke 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. Speaking about ordered and sorted in the context of collections is not a new terminology I am introducing, but seems to be pretty common in computer science This is quite true. I haven't seen any evidence for 'rife' misunderstanding of these terms. That said ... Perhaps Pythonists are not used to that terminology, since they use the term list for an ordered collection. An ordered dictionary is a dictionary whose keys are a (unique) list. Sometimes it is also called a sequence Maybe we should call it a 'sequenced dictionary' to fit better with pythonic terminology? tom -- YOU HAVE NO CHANCE TO ARRIVE MAKE ALTERNATIVE TRAVEL ARRANGEMENTS. -- Robin May -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Wed, 23 Nov 2005, Carsten Haese wrote: On Wed, 2005-11-23 at 15:17, Christoph Zwerschke wrote: Bengt Richter wrote: E.g., it might be nice to have a mode that assumes d[key] is d.items()[k][1] when key is an integer, and otherwise uses dict lookup, for cases where the use case is just string dict keys. I also thought about that and I think PHP has that feature, but it's probably better to withstand the temptation to do that. It could lead to an awful confusion if the keys are integers. Thus quoth the Zen of Python: Explicit is better than implicit. In the face of ambiguity, refuse the temptation to guess. With those in mind, since an odict behaves mostly like a dictionary, [] should always refer to keys. An odict implementation that wants to allow access by numeric index should provide explicitly named methods for that purpose. +1 Overloading [] to sometimes refer to keys and sometimes to indices is a really, really, REALLY bad idea. Let's have it refer to keys, and do indices either via a sequence attribute or the return value of items(). More generally, if we're going to say odict is a subtype of dict, then we have absolutely no choice but to make the methods that it inherits behave the same way as in dict - that's what subtyping means. That means not doing funky things with [], returning a copy from items() rather than a live view, etc. So, how do we provide mutatory access to the order of items? Of the solutions discussed so far, i think having a separate attribute for it - like items, a live view, not a copy (and probably being a variable rather than a method) - is the cleanest, but i am starting to think that overloading items to be a mutable sequence as well as a method is quite neat. I like it in that the it combines two things - a live view of the order and a copy of the order - that are really two aspects of one thing, which seems elegant. However, it does strike me as rather unpythonic; it's trying to cram a lot of functionality in an unexpected combination into one place. Sparse is better than dense and all that. I guess the thing to do is to try both out and see which users prefer. tom -- YOU HAVE NO CHANCE TO ARRIVE MAKE ALTERNATIVE TRAVEL ARRANGEMENTS. -- Robin May -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Wed, 23 Nov 2005, Christoph Zwerschke wrote: Tom Anderson wrote: 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.). 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. Think of it similar as the case of an ordinary dictionary: There is conceptually a set here (the set of keys), but you cannot manipulate it directly, but only through the according dictionary methods. Which is a shame! For an ordedred dictionary, there is conceptually a list (or more specifically a unique list). Again you should not manipulate it directly, but only through methods of the ordered dictionary. This sounds at first more complicated, but is in reality more easy. For instance, if I want to put the last two keys of an ordered dict d at the beginning, I would do it as d = d[:-2] + d[-2:]. As i mentioned elsewhere, i think using [] like this is a terrible idea - and definitely not easier. With the list attribute (called sequence in odict, you would have to write: d.sequence = d.sequence[:-2] + d.sequence[-2:]. This is not only longer to write down, but you also have to know that the name of the attribute is sequence. True, but that's not exactly rocket science. I think the rules governing when your [] acts like a dict [] and when it acts like a list [] are vastly more complex than the name of one attribute. Python's strength is that you don't have to keep many details in mind because it has a small basic vocabulary and orthogonal use. No it isn't - it's in having a wide set of basic building blocks which do one simple thing well, and thus which are easy to use, but which can be composed to do more complex things. What are other examples of this kind of 'orthogonal use'? I prefer the ordered dictionary does not introduce new concepts or attributes if everything can be done intuitively with the existing Python methods and operators. I strongly agree. However, i don't think your overloading of [] is at all intuitive. tom -- YOU HAVE NO CHANCE TO ARRIVE MAKE ALTERNATIVE TRAVEL ARRANGEMENTS. -- Robin May -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Tom Anderson schrieb: Maybe we should call it a 'sequenced dictionary' to fit better with pythonic terminology? That's not such a bad idea. Note that it is called like that in the Python version of the Programming Language Examples Alike Cookbook: http://pleac.sourceforge.net/pleac_python/hashes.html#AEN250 Anyway, I still favor the more common term ordered dictionary. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
It seems everybody is in full agreement here. I have the same mixed feeling about letting keys/values/items become both managed list attributes and still returning copies of the lists when called in the usual way as methods. I don't know any precedent for doing things that way and i'm unsure whether it meets the Zen of Python. But anyway the idea is nice enough to try it out. -- Chris -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Tom Anderson wrote: True, but that's not exactly rocket science. I think the rules governing when your [] acts like a dict [] and when it acts like a list [] are vastly more complex than the name of one attribute. I think it's not really rocket science either to assume that an ordered dictionary behaves like a dictionary if you access items by subscription and like a list if you use slices (since slice indexes must evaluate to integers anyway, they can only be used as indexes, not as keys). Python's strength is that you don't have to keep many details in mind because it has a small basic vocabulary and orthogonal use. No it isn't - it's in having a wide set of basic building blocks which do one simple thing well, and thus which are easy to use, but which can be composed to do more complex things. What are other examples of this kind of 'orthogonal use'? I mean for instance that you can deal with a tuple in the same way as with a string and things like that. Concerning small: Somebody coined the good slogan Python fits my brain but I could also say Python fits *into* my brain (I mean without the batteries of course ;-) - you pretty soon have all the built-in functins, datatypes and their use in your head. On the other side of course, Python is a huge field and you can discuss endlessly as we are doing here. Anyway, my argument was not good (avoiding new attributes names in order to keep the vocabulary small). And by the way, what both of us listed as strengths of Python will be probably claimed by protagonists of any other language as well. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Fri, 25 Nov 2005, Christoph Zwerschke wrote: Tom Anderson wrote: True, but that's not exactly rocket science. I think the rules governing when your [] acts like a dict [] and when it acts like a list [] are vastly more complex than the name of one attribute. I think it's not really rocket science either to assume that an ordered dictionary behaves like a dictionary if you access items by subscription and like a list if you use slices (since slice indexes must evaluate to integers anyway, they can only be used as indexes, not as keys). When you put it that way, it makes a certain amount of sense - [:] is always about index, and [] is always about key. It's still icky, but it is completely unambiguous. tom -- I content myself with the Speculative part [...], I care not for the Practick. I seldom bring any thing to use, 'tis not my way. Knowledge is my ultimate end. -- Sir Nicholas Gimcrack -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli wrote: Fuzzyman [EMAIL PROTECTED] wrote: ... - the internal keys list should be hidden I disagree. It is exposed so that you can manually change the order (e.g. to create a sorted dict, rather than one ordered by key insertion). What do you *gain* by hiding it ? Freedom of implementation, of course. E.g., I can perhaps get better performance by keeping a red-black tree of (insertiontime,key) pairs, so for example deleting a key is O(log(N)) rather than O(N) as it would have to be if the sequence had to be kept as a Python list. What ELSE do you ever gain by enforcing abstraction and information hiding? Conceptual integrity and implementation freedom... The poster I was replying to inferred that we should hide it to protect him from breaking it. :-) Your reason is much more valid than the one I inferred. (And probably worth chanign the code for). - list methods should be mixed in instead Hmm... I did consider this. Which list methods would you consider appropriate ? The difficulty is that integers are valid keys for a dictionary. Perhaps a subclass that uses integers as indexes instead... What about allowing slicing, taking advantage of the fact that slices are NOT valid dictionary keys? Hmm... ok, simple enough to implement. What would anyone *use* it for though ? Presumably sort and reverse methods are also desired. Yeah - good idea. Insert is also good - I can't remember if we provide this or not. Thanks Fuzzyman http://www.voidspac.org.uk/python/index.shtml You can always perform list operations on the ``sequence`` attribute of course. But NOT having to expose .sequence as a real mutable list whose changes affect ordering has many advantages, as above noticed. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ok. That answers a question in the post I've just made. This thread is hard to follow. Thanks Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Fuzzyman wrote: So what do you want returned when you ask for d1[1] ? The member keyed by 1, or the item in position 1 ? In case of conflict, the ordered dictionary should behave like a dictionary, not like a list. So d1[1] should be the member keyed by 1, not the item in position 1. Only in case there is no member keyed by 1, the item in position 1 could be returned, but I think that would be too adventurous a hattrick and can lead to big confusion. Better to raise a KeyError in that case. I agree - hard to trace bugs lie this way [snip..] Instead of writing d.sequence = new_sequence, I would write d.setkeys(new_sequence). But I'm not sure what to do if new_sequence is not a permutation of the old one. Raise a KeyError? Or even swallow this? For instance This is an interesting question - I don't know which is the best behaviour here. It's probably better to raise a KeyError - that way the error will occur when it happens. The simplest way of doing this is to check that the new key list (sorted) is the same as the original one (sorted). This is potentially quite an expensive operation. It might be faster to compare sets with Python 2.4 - but we intend to retain compatibility with Python 2.2. d = OrderedDict((1,11), (2,12)) d.setkeys((2, 1)) == d = OrderedDict((2, 11), (1, 12)) d.setkeys((3, 4)) == d = OrderedDict((3, 11), (4, 12)) (or KeyError?) d.setvalues((12, 11)) == d = OrderedDict((1, 12), (2, 11)) d.setvalues((13, 14)) == d = OrderedDict((1, 13), (2, 14)) (always ok) (Or maybe better set_keys in analogy to has_key?) I hesitate making keys and values managed properties, because this would conflict with them being methods in ordinary dicts. Ordered dicts should resemble ordinary dicts as closely as possible. And giving it a different name like sequence I find confusing and unintuitive. You really want to be able to set values as a sequence ? I suppose it's even easier to implement than changing keys, but I'd never considered it. A resort could be the following: If keys() is given a sequence as argument, then use this as the new sequence of keys, and similar with values(). This way, no new methods need to be introduced. That's not a bad idea. I'll chat with Nicola Larosa and see what he thinks. It does break backawards compatibility of course... All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote:
Duncan Booth schrieb:
In Javascript Object properties (often used as an associative array)
are defined as unordered although as IE seems to always store them in
the order of original insertion it wouldn't surprise me if there are
a lot of websites depending on that behaviour.
You're right with both. The ECMA language definition says object
properties are an unordered collection, but MSIE and probably other
browsers keep the order in which they were created. Of course one
should not rely on that.
Yes, the real fun bit is arrays. If you create an array using the 'new
Array' or [ ... ] then a for..in loop might well trick you into thinking it
is going to go through the elements in order, but if you assign to elements
directly it breaks down:
a = ['a', 'b', 'c'];
a[4] = 'e';
a[3] = 'd';
for (var k in a) {
alert(a[k]+'='+a[k]);
}
On IE this will go through elements in the order 0, 1, 2, 4, 3.
Also, it is original order of insertion which matters, not the 'last
in/last out' you might have expected. In other words it looks rather as
though IE simply sets deleted properties to undefined (and skips them on
iteration), it never really deletes a property, so anyone who tries to use
a Javascript object as an associative array with lots of rapidly changing
keys could be in for a nasty shock.
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Carsten Haese wrote: On Wed, 23 Nov 2005 23:39:22 +0100, Christoph Zwerschke wrote Carsten Haese schrieb: Thus quoth the Zen of Python: Explicit is better than implicit. In the face of ambiguity, refuse the temptation to guess. With those in mind, since an odict behaves mostly like a dictionary, [] should always refer to keys. An odict implementation that wants to allow access by numeric index should provide explicitly named methods for that purpose. Exactly. But I don't think in this case such methods would be needed. You easily get the i-th value in the ordered dict as d.values()[i]. -- Chris True enough, but unless the odict has its list of values on hand, you're asking the odict to build a list of all its values just so that you can get the i'th element. Having a method that does the equivalent of d[d.sequence[i]] would be cleaner and more efficient. I'm going to add some of the sequence methods. I'm *not* going to allow indexing, but I will allow slicing. You can also do d[d.keys()[i]] This provides two ways of fetching values by index, so I don't want to add another. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -Carsten -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] (CZ) escribió: CZ Eso es exactamente lo que yo queria haber! ¿Haber? ¿Tener? :=( -- Piet van Oostrum [EMAIL PROTECTED] URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C4] Private email: [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
By the way, Nicola and I will be working on an improving odict in line with several of the suggestions in this thread. See : http://www.voidspace.org.uk/python/weblog/arch_d7_2005_11_19.shtml#e140 All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Duncan Booth schrieb: On IE this will go through elements in the order 0, 1, 2, 4, 3. Oops! I bet most people would not expect that, and it is probably not mentioned in most Javascript tutorials. I think this is a weakpoint of the ECMA definition, not MSIE. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Tom Anderson wrote: 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 I am now in favour of hiding hte sequence attribute. You will be able to mutate the the keys list through : d1 = OrderedDict(some_sequence_of_items) keys = d1.keys() keys.sort() # or other mutation d1.keys(keys) Admittedly this is a lot slower than : d1 = OrderedDict(some_sequence_of_items) d1.sequence.sort() *but* it frees the squence attribute from any implementation details. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml 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 Wed, 23 Nov 2005 23:00:29 +0100, Christoph Zwerschke [EMAIL PROTECTED] wrote: Fuzzyman wrote: So what do you want returned when you ask for d1[1] ? The member keyed by 1, or the item in position 1 ? In case of conflict, the ordered dictionary should behave like a dictionary, not like a list. So d1[1] should be the member keyed by 1, not the item in position 1. Only in case there is no member keyed by 1, the item in position 1 could be returned, but I think that would be too adventurous a hattrick and can lead to big confusion. Better to raise a KeyError in that case. But no other way to directly manipulate the keys should be provided. Why - don't trust yourself with it ? No, because I think it is not needed if list operations like insert are directly possible on your dictionary. But maybe methods such as setkeys() and setvalues() would be nice to have in addition. Instead of writing d.sequence = new_sequence, I would write d.setkeys(new_sequence). But I'm not sure what to do if new_sequence is not a permutation of the old one. Raise a KeyError? Or even swallow this? For instance d = OrderedDict((1,11), (2,12)) d.setkeys((2, 1)) == d = OrderedDict((2, 11), (1, 12)) d.setkeys((3, 4)) == d = OrderedDict((3, 11), (4, 12)) (or KeyError?) d.setvalues((12, 11)) == d = OrderedDict((1, 12), (2, 11)) d.setvalues((13, 14)) == d = OrderedDict((1, 13), (2, 14)) (always ok) Too many weird possibilities for unexpected key-value associations. d.setitems() might be safer, but see d.items[i:j] below (without eliminating d.items() ;-) The implication above is that OrderedDict takes an *args argument, but really it takes a single argument that is a sequence of k,v pairs, (and maybe some keyword options). (Or maybe better set_keys in analogy to has_key?) I hesitate making keys and values managed properties, because this would conflict with them being methods in ordinary dicts. Ordered dicts should resemble ordinary dicts as closely as possible. And giving it a different name like sequence I find confusing and unintuitive. A resort could be the following: If keys() is given a sequence as argument, then use this as the new sequence of keys, and similar with values(). This way, no new methods need to be introduced. You could make keys, values, and items custom descriptors which would define __call__ for the old key() etc accesses, well as __getitem__ and __setitem__. Then you could write d.items[0], d.items[-1] = d.items[-1], d.items[0] to swap the order of the first and last items in the thing (I hesitate to say dict ;-) You could also operate on slices. BTW, before I showed an example where d[2:3] returned a new dict instance rather than d.items()[:]. I think the items list is better, since they naturally add, sort, reverse, etc as lists, and you can write OrderedDict(d[2:3]+d[1:2]) if you want a new dict. A slice assignment to d[i:j] is really sugar for something, but we have to decide exactly what in case of duplicate keys in the incoming items, either with each other (effictively a shorter incoming list with the last key:value pairs replacing prior pairs with the same key, but the first key determining placement -- but where? what if a key doesn't exists outside of the target slice (hence not within the eliminated slice, since the whole target dict item list has unique keys)? One way to define it would be d.items[i:j] = itemseq to be implemented as sugar for newitems = d.items[:i] + list(itemseq) + d.items[j:] d.clear() d.update(newitems) so d.reverse() could be spelled d.items[:] = d.items[::-1] If you are using slices, you can safely use them directly in the __getitem__ of th dict interface, as I did in the Que mas? post. So we don't have to write d.items[i:j] and could write d[i:j]. The thing is, d[i:j] will tempt to skip .items in d.items[i] and write d[i], which has the dict key meaning, not the item list index. It is faster not have a descriptor between though. I think maybe allowing write to keys or values is pretty iffy. There are too many weird re-associations of keys and values possible, and which you could do my other means if you really really wanted to. But I do think full index and slice read access would be fine. I think also that d1==d2 should effectively be implemented as d1[:] == d2[:] -- i.e, compare the item lists to implement comparisons. Detailed requirements are most of the work ;-) I'm thinking now to try subclassing list in a constrained way instead of dict, but well see. Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman schrieb: I'm going to add some of the sequence methods. I'm *not* going to allow indexing, but I will allow slicing. You can also do d[d.keys()[i]] This provides two ways of fetching values by index, so I don't want to add another. And this would be probably faster than d.values()[i] in the usual implementation where values() has to be built first as Carsten noted. -- Chris -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
d.keys() will still return a copy of the list, so d.keys()[i] will still be slower than d.sequence[i] Slicing shouldn't be too much slower though. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: On Wed, 23 Nov 2005 23:00:29 +0100, Christoph Zwerschke [EMAIL PROTECTED] wrote: [snip..] I think also that d1==d2 should effectively be implemented as d1[:] == d2[:] -- i.e, compare the item lists to implement comparisons. IIUC then the odict effectively already does this. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml Detailed requirements are most of the work ;-) I'm thinking now to try subclassing list in a constrained way instead of dict, but well see. Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman wrote: You will be able to mutate the the keys list through : d1 = OrderedDict(some_sequence_of_items) keys = d1.keys() keys.sort() # or other mutation d1.keys(keys) Admittedly this is a lot slower than : d1 = OrderedDict(some_sequence_of_items) d1.sequence.sort() *but* it frees the squence attribute from any implementation details. You should also implement d1.sort() or d1.sortkeys() which will have no performance drawbacks. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter schrieb: d.setvalues((13, 14)) == d = OrderedDict((1, 13), (2, 14)) The implication above is that OrderedDict takes an *args argument, but really it takes a single argument that is a sequence of k,v pairs, (and maybe some keyword options). Right. Interpret it as a short notation only, I did not want to change the interface. I think it's a common mistake to forget the brackets because you think one pair should be enough. At least I often forget it. You could make keys, values, and items custom descriptors which would define __call__ for the old key() etc accesses, well as __getitem__ and __setitem__. Then you could write d.items[0], d.items[-1] = d.items[-1], d.items[0] to swap the order of the first and last items in the thing (I hesitate to say dict ;-) You could also operate on slices. Nice. You could also get the i-th value with d.values[i]. But is this considered good style or would it be considered dirty to have a callable member that also supports indexing and slicing? (I don't know, just asking?) Plus, it opens a can of worms by increasing the complexity tremendously. Let's see whether this can be handled. BTW, before I showed an example where d[2:3] returned a new dict instance rather than d.items()[:]. I think the items list is better, since they naturally add, sort, reverse, etc as lists, and you can write OrderedDict(d[2:3]+d[1:2]) if you want a new dict. Not sure about that. I would rather expect that if you slice an object, you get an object of the same type. And you can also add, sort, reverse, etc the ordered dict if you want. A slice assignment to d[i:j] is really sugar for something, but we have to decide exactly what in case of duplicate keys in the incoming items, either with each other ... You mean slice assignments to d.items[i:j]. If you make the slice assignment to d[i:j] then at least you cannot have conflicts in the incoming items. The first question is: Should a slice assignment be treated as deletion with subsequential addition (changing the order) or as a replacement (i.e. try to not change the order)? I agree that the second would be the expected semantics, but as you mentioned more difficult to implement. One way to define it would be d.items[i:j] = itemseq to be implemented as sugar for newitems = d.items[:i] + list(itemseq) + d.items[j:] d.clear() d.update(newitems) Which should be the same as d = OrderedDict(d.items[:i] + list(itemseq) + d.items[j:]) Sounds reasonable. So d.reverse() could be spelled d.items[:] = d.items[::-1] Slice assignment for keys and values would also allow to set a new key order with d.keys[:] = newkeyseq So no need to define a setkeys() method or let keys() take arguments. If we want to allow this kind of things at all. If you are using slices, you can safely use them directly in the __getitem__ of th dict interface, as I did in the Que mas? post. So we don't have to write d.items[i:j] and could write d[i:j]. The thing is, d[i:j] will tempt to skip .items in d.items[i] and write d[i], which has the dict key meaning, not the item list index. It is faster not have a descriptor between though. I still think d[i:j] should return an ordered dict, not an item list. I think maybe allowing write to keys or values is pretty iffy. There are too many weird re-associations of keys and values possible, and which you could do my other means if you really really wanted to. But I do think full index and slice read access would be fine. There are different opinions. Fuzzyman would probably say Don't trust yourself? I myself am undecided. Perhaps you could expect that somebody knows what he does if he makes a slice assignment to d.keys. In any way, such an assignment should not break the directory (with broken I mean that the internal keys sequence does not match the keys of the internal dictionary). If anything does not match, it should raise a KeyException. If it is implemented that way, I think we can allow it. I think also that d1==d2 should effectively be implemented as d1[:] == d2[:] -- i.e, compare the item lists to implement comparisons. Wouldn't it be more performant to compare for d1.internal_dict==d2.internal_dict and d1.internal_sequence==d2.internal_sequence? You don't keep track of the item lists, they need to be built on every occasion. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman schrieb: d.keys() will still return a copy of the list, so d.keys()[i] will still be slower than d.sequence[i] Right, I forgot that. Bengt suggested to implement __call__ as well as __getitem__ and __setitem__ for keys, values and items. In this case, you could very effectively access it as d.values[i]. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
hacer probablemente. DCA. Piet van Oostrum wrote: Christoph Zwerschke [EMAIL PROTECTED] (CZ) escribió: CZ Eso es exactamente lo que yo queria haber! ¿Haber? ¿Tener? :=( -- Piet van Oostrum [EMAIL PROTECTED] URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C4] Private email: [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: This is probably a FAQ, but I dare to ask it nevertheless since I haven't found a satisfying answer yet: Why isn't there an ordered dictionary class at least in the standard list? Time and again I am missing that feature. Maybe there is something wrong with my programming style, but I rather think it is generally useful. I fully agree with the following posting where somebody complains why so very basic and useful things are not part of the standard library: http://groups.google.com/group/comp.lang.python/msg/e652d2f771a49857 Are there plans to get it into the standard lib sometime? We're always encouraging new posters to use good subject lines. Several hundred posts after your original question I think everyone can agree that this was a *very* good subject line :-) Perhaps now the answer top your question is more obvious: there is by no means universal agreement on what an ordered dictionary should do. Given the ease with which Python allows you to implement your chosen functionality it would be presumptuous of the core developers to favour any one of the several reasonable alternatives that might be chosen. regards Steve -- Steve Holden +44 150 684 7255 +1 800 494 3119 Holden Web LLC www.holdenweb.com PyCon TX 2006 www.python.org/pycon/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: I still believe that the concept of an ordered dictionary (behave like dict, only keep the order of the keys) is intuitive and doesn't give you so much scope for ambiguity. But probably I need to work on an implementation to become more clear about possible hidden subtleties. Bengt Richter schrieb: Does that mean that the Larosa/Foord odict.py implementation in PyPI does not do what you want? Basically, it is what I had in mind. But I'm now seeing some things that could be improved/supplemented, e.g. - performance improvements Implementation changes to follow, based on suggestions in this thread. For *optimal* performance it needs to be implemented in C of course. :-) As F points out, a list of tuples may give you a data structure that can be accessed quicker (although some operations will be slower). An ordered dictionary will be a lot easier to use and make your code more readable though. - the internal keys list should be hidden I disagree. It is exposed so that you can manually change the order (e.g. to create a sorted dict, rather than one ordered by key insertion). What do you *gain* by hiding it ? - list methods should be mixed in instead Hmm... I did consider this. Which list methods would you consider appropriate ? The difficulty is that integers are valid keys for a dictionary. Perhaps a subclass that uses integers as indexes instead... You can always perform list operations on the ``sequence`` attribute of course. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: On 22 Nov 2005 02:16:22 -0800, Fuzzyman [EMAIL PROTECTED] wrote: Kay Schluehr wrote: Christoph Zwerschke wrote: That would be also biased (in favour of Python) by the fact that probably very little people would look for and use the package in the cheese shop if they were looking for ordered dicts. Does anyone actually use this site? While the Vaults offered a nice place and a nice interface the Cheese Shop has the appeal of a code slum. Hmmm.. it's *the* repository for Python code. I expect quite a few people use it... :-) I hadn't realized how much stuff was there. I generally google for stuff, but I will be looking directly now. BTW, I made a mod[1] to your odict that I think/hope is going to be generally faster. It requires 2.4 though. It passes the same doctest, so its probably close to the same. It stores the ordering info differently, but is also a dict subclass. odict maintains compatibility with Python 2.2 - so it's not a change we'd put back into the module I don't think. Changes that keep compatibility are very welcoemd though. Do you happen to have a timing test that exercises various aspects, so I can try it before I embarrass myself? Otherwise I guess I'll write something. The only tests we have are the ones in the module. If you create some timing tests we'd be interested in having access to them though. They would be a useful addition. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml Would the would-be users chime in with some idea of what kinds of operations are most important timing-wise? Which would get the most use? How dynamic would ordering typically be? [1] fairly pervasive little mods actually [ 9:15] C:\pywk\clpdiffodict.py odictb.py |wc 146458 4948 [ 9:15] C:\pywk\clpwc odict*.py 467 1228 12483 odict.py 511 1500 14728 odictb.py 978 2728 27211 Totals Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Steve Holden wrote: Perhaps now the answer top your question is more obvious: there is by no means universal agreement on what an ordered dictionary should do. Given the ease with which Python allows you to implement your chosen functionality it would be presumptuous of the core developers to favour any one of the several reasonable alternatives that might be chosen. It seems to be though as ordered dictionary are slowly to be confined to only ordered on order of change to the dictionary. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: One implementation detail that I think needs further consideration is in which way to expose the keys and to mix in list methods for ordered dictionaries. In http://aspn.activestate.com/ASPN/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). So don't do it. ;-) I think it would be probably the best to hide the keys list from the public, but to provide list methods for reordering them (sorting, slicing etc.). For instance: d1 = OrderedDict( (1, 11), (2, 12), 3, 13) ) d1[1:] == OrderedDict( (2, 12), 3, 13) ) So what do you want returned when you ask for d1[1] ? The member keyed by 1, or the item in position 1 ? You can access the members using list operations on the sequence attribute. E.g. d1[d1.sequence[index]] This could probably be made more convenient. d1[0] + d1[2] == OrderedDict( (1, 11), (3, 13) ) d1.reverse() == OrderedDict( (3, 13), (2, 12), 1, 11) ) Interesting idea. d1.insert(1, (4, 14)) == OrderedDict( (1, 11), (4, 14), (2, 12), 3, 13) ) Also an interesting idea. etc. But no other way to directly manipulate the keys should be provided. Why - don't trust yourself with it ? All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
There is already an update method of course. :-) Slicing an ordered dictionary is interesting - but how many people are actually going to use it ? (What's your use case) You can already slice the sequence atribute and iterate over that. All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
While we're on the subject, it would be useful to be able to paste in a changelog as well as a description. Currently when updating versions you have to include the changelog in the description - or not at all... All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] wrote: Steve Holden wrote: Perhaps now the answer top your question is more obvious: there is by no means universal agreement on what an ordered dictionary should do. Given the ease with which Python allows you to implement your chosen functionality it would be presumptuous of the core developers to favour any one of the several reasonable alternatives that might be chosen. It seems to be though as ordered dictionary are slowly to be confined to only ordered on order of change to the dictionary. While I'm only +0 for a standard odict I'm wondering that discussing this topic leads to the auctoritative conclusion that it is unsolvable, we have to accept infinite diversity etc. where people like me seeing a classification immediately ( mathematical education? ) . Of course this matter is trivial but we already know about monster-threads revolving around decorator syntax ( including hurt souls and semi-scientific papers ) and abandoning the print statement in Python 3.0. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Ok, I just did a little research an compared support for ordered dicts in some other languages: Just to add to your list: In Javascript Object properties (often used as an associative array) are defined as unordered although as IE seems to always store them in the order of original insertion it wouldn't surprise me if there are a lot of websites depending on that behaviour. Javascript Array indexes are also stored as properties and are therefore also unordered. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 23 Nov 2005 01:24:46 -0800, Kay Schluehr [EMAIL PROTECTED] wrote: [EMAIL PROTECTED] wrote: Steve Holden wrote: Perhaps now the answer top your question is more obvious: there is by no means universal agreement on what an ordered dictionary should do. Given the ease with which Python allows you to implement your chosen functionality it would be presumptuous of the core developers to favour any one of the several reasonable alternatives that might be chosen. It seems to be though as ordered dictionary are slowly to be confined to only ordered on order of change to the dictionary. While I'm only +0 for a standard odict I'm wondering that discussing this topic leads to the auctoritative conclusion that it is unsolvable, we have to accept infinite diversity etc. where people like me seeing a classification immediately ( mathematical education? ) . Of course this matter is trivial but we already know about monster-threads revolving around decorator syntax ( including hurt souls and semi-scientific papers ) and abandoning the print statement in Python 3.0. I think the concept has converged to a replace-or-append-by-key ordering of key:value items with methods approximately like a dict. We're now into usability aspects such as syntactic sugar vs essential primitives, and default behaviour vs selectable modes, ISTM. E.g., it might be nice to have a mode that assumes d[key] is d.items()[k][1] when key is an integer, and otherwise uses dict lookup, for cases where the use case is just string dict keys. But feature creep is sure a threat to clean design. Regards, Bengt Richter -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman [EMAIL PROTECTED] wrote in news:[EMAIL PROTECTED]: Christoph Zwerschke wrote: - the internal keys list should be hidden I disagree. It is exposed so that you can manually change the order (e.g. to create a sorted dict, rather than one ordered by key insertion). What do you *gain* by hiding it ? The internal list should be 'hidden' in the sense that it itself would not be modifiable, though it should be routine to obtain a copy of it at any time. That copy could then be arranged as needed. Any rearrangement of the original list's order destroys the reason for having an entry- or change-ordered dict in the first place. -- rzed -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ganesan Rajagopal wrote: [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 In Python it's simple to keep a list sorted using bisect.insort. import bisect l=[] bisect.insort(l,4) bisect.insort(l,3) bisect.insort(l,5) bisect.insort(l,1) bisect.insort(l,6) bisect.insort(l,2) l [1, 2, 3, 4, 5, 6] Assuming a list with n tuples, where the first m elements in each tuple is the key, we can also fetch elements through keys (interval matches as well as exact matches) with O(log n) performance. I guess those who thinks this isn't enough should push for placing something like Zope's BTree classes in the standard library. Fredrik already showed how simple and cheap it was to make a dict out of a list. I think this is a superior solution to odicts as suggested, but by all means, if people want odicts, make sure that there is a good implementation available, use it, show that it's useful to others, and maybe, some time in the future, it will be considered for inclusion in the standard library. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 2005-11-22 at 20:44, Tom Anderson wrote: On Tue, 22 Nov 2005, Carsten Haese wrote: On Tue, 2005-11-22 at 14:37, Christoph Zwerschke wrote: In Foord/Larosa's odict, the keys are exposed as a public member which also seems to be a bad idea (If you alter the sequence list so that it no longer reflects the contents of the dictionary, you have broken your OrderedDict). That could easily be fixed by making the sequence a managed property whose setter raises a ValueError if you try to set it to something that's not a permutation of what it was. I'm not a managed property expert (although there's a lovely studio in Bayswater you might be interested in), but how does this stop you doing: my_odict.sequence[0] = Shrubbery() It would only break if the getter returns the internal list directly. The getter should return a copy instead, which is what the keys() method already does anyway. This would ensure that the only way to alter the sequence is by replacing it in its entirety. -Carsten. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Rick Wotnaz wrote: Fuzzyman [EMAIL PROTECTED] wrote in news:[EMAIL PROTECTED]: Christoph Zwerschke wrote: - the internal keys list should be hidden I disagree. It is exposed so that you can manually change the order (e.g. to create a sorted dict, rather than one ordered by key insertion). What do you *gain* by hiding it ? The internal list should be 'hidden' in the sense that it itself would not be modifiable, though it should be routine to obtain a copy of it at any time. That copy could then be arranged as needed. Any rearrangement of the original list's order destroys the reason for having an entry- or change-ordered dict in the first place. That's not the only use case. Other use cases are to have a specific order, not based on entry time. Simple example : d1 = OrderedDict(some_dict.items()) d1.sequence.sort() d1 is now an ordered dict with the keys in alphabetic order. If you don't want to modify sequence, don't. If you want a copy do : seq = d1.sequence[:] All the best, Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- rzed -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman [EMAIL PROTECTED] wrote: ... - the internal keys list should be hidden I disagree. It is exposed so that you can manually change the order (e.g. to create a sorted dict, rather than one ordered by key insertion). What do you *gain* by hiding it ? Freedom of implementation, of course. E.g., I can perhaps get better performance by keeping a red-black tree of (insertiontime,key) pairs, so for example deleting a key is O(log(N)) rather than O(N) as it would have to be if the sequence had to be kept as a Python list. What ELSE do you ever gain by enforcing abstraction and information hiding? Conceptual integrity and implementation freedom... - list methods should be mixed in instead Hmm... I did consider this. Which list methods would you consider appropriate ? The difficulty is that integers are valid keys for a dictionary. Perhaps a subclass that uses integers as indexes instead... What about allowing slicing, taking advantage of the fact that slices are NOT valid dictionary keys? Presumably sort and reverse methods are also desired. You can always perform list operations on the ``sequence`` attribute of course. But NOT having to expose .sequence as a real mutable list whose changes affect ordering has many advantages, as above noticed. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman [EMAIL PROTECTED] wrote: There is already an update method of course. :-) Slicing an ordered dictionary is interesting - but how many people are actually going to use it ? (What's your use case) I detest and abhor almost-sequences which can't be sliced (I consider that a defect of collections.deque). If the ordered dictionary records by its sequencing the time order of key insertion, being able to ask for the last 5 keys entered or the first 3 keys entered seem to me to be perfectly natural use cases, and most naturally accomplished by slicing of course, d[-5:] and d[:3] respectively. Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Steve Holden schrieb: Perhaps now the answer top your question is more obvious: there is by no means universal agreement on what an ordered dictionary should do. Given the ease with which Python allows you to implement your chosen functionality it would be presumptuous of the core developers to favour any one of the several reasonable alternatives that might be chosen. The discussion showed indeed that there are some points which are not so straightforward as I believed. But I still don't see the several reasonable alternatives. So far all implementations I have seen are basically pretty similar. Is there any implementation that is basically different from Foord/Larosa's odict? I still don't see a principal problem here, just the problem that the existing implementations are not well enough thought-out and sophisticated enough. Given the ease with which Python allows you to implement your chosen functionality it would be presumptuous of the core developers to favour any one of the several reasonable alternatives that might be chosen. You could say the same about the idea of sets in Python, and it is probably the reason why it took so much time until they became a part of Python. I wished that had happened earlier, since sets are the basic mathematic structure. I'm now very happy to have sets not only in the standard lib but even as built-in types and I'm sure there hasn't been universal agreement on how sets should be implemented either. I don't think it was presumptuous to finally settle down on one implementation. Of course, ordered dictionaries are no candidates for becoming built-in data types, and the existing implementations are not sophisticated and mature enough to go to the standard lib right now. But principally, if an improved version is developed (maybe on the occasion of this thread) and will be tested and proven, why should it not go to the standard lib some day? BTW, somebody has suggested it could go to collections which sounds like the right place, but the description says the module is intended for High-performance container datatypes, and, as has been discussed, ordered dictionaries are not used for performance or efficiency reasons, but rather for reasons of convenience. So *if* they ever go to the standard lib, I'm not sure whether collections would be the right place. Or collections will need a different description - maybe there are other interesting basic collection types which are chosen for convenience, not for performance (for instance, ordered sets)? -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
[EMAIL PROTECTED] schrieb: It seems to be though as ordered dictionary are slowly to be confined to only ordered on order of change to the dictionary. Ordered dictionary means that the keys are not an ordinary set like in an ordinary dictionary, but an ordered set. I think this definition is pretty straightforward and common. An ordered set is the same as a unique list, i.e. a list where all elements are unique. When there is automatical ordering using a comparison function, I would not speak of an ordered directory, but of a sorted directory. This would be basically a dictionary plus a comparison function. The keys would always be iterated in the order given by the comparison function. It would be nice to have a sorted dictionary as well, even if you can achieve the same by calling the sorted built-in on the keys. Think of a sorted directory as a subclass of ordered directories. Implementing it that way would even have perfomance benefits if the keys are inserted using the bisect algorithm. This is better than calling sorted() on the keys of an ordinary dictionary many times. By the way, you will find the same terminology in Smalltalk, where SortedCollection is a subclass of OrderedCollection. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: I think the concept has converged to a replace-or-append-by-key ordering of key:value items with methods approximately like a dict. We're now into usability aspects such as syntactic sugar vs essential primitives, and default behaviour vs selectable modes, ISTM. Yes, and we would be good if we do not stop the discussion at this point with nothing, but really create such a sophisticated implementation. Whether it will become popular or go to the standard lib some day is a completely different question. E.g., it might be nice to have a mode that assumes d[key] is d.items()[k][1] when key is an integer, and otherwise uses dict lookup, for cases where the use case is just string dict keys. I also thought about that and I think PHP has that feature, but it's probably better to withstand the temptation to do that. It could lead to an awful confusion if the keys are integers. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
* C++ has a Map template in the STL which is ordered (a Sorted Associative Container). Alex Martelli wrote: Ordered *by comparisons on keys*, NOT by order of insertion -- an utterly and completely different idea. Shame on me. I talked so much about the difference between ordered and sorted and now I wrote such a confusing sentence. You're right, C++ Maps are not an example for ordered dictionaries, but for sorted dictionaries. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Duncan Booth schrieb: In Javascript Object properties (often used as an associative array) are defined as unordered although as IE seems to always store them in the order of original insertion it wouldn't surprise me if there are a lot of websites depending on that behaviour. You're right with both. The ECMA language definition says object properties are an unordered collection, but MSIE and probably other browsers keep the order in which they were created. Of course one should not rely on that. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Wed, 2005-11-23 at 15:17, Christoph Zwerschke wrote: Bengt Richter wrote: I think the concept has converged to a replace-or-append-by-key ordering of key:value items with methods approximately like a dict. We're now into usability aspects such as syntactic sugar vs essential primitives, and default behaviour vs selectable modes, ISTM. Yes, and we would be good if we do not stop the discussion at this point with nothing, but really create such a sophisticated implementation. Whether it will become popular or go to the standard lib some day is a completely different question. E.g., it might be nice to have a mode that assumes d[key] is d.items()[k][1] when key is an integer, and otherwise uses dict lookup, for cases where the use case is just string dict keys. I also thought about that and I think PHP has that feature, but it's probably better to withstand the temptation to do that. It could lead to an awful confusion if the keys are integers. Thus quoth the Zen of Python: Explicit is better than implicit. In the face of ambiguity, refuse the temptation to guess. With those in mind, since an odict behaves mostly like a dictionary, [] should always refer to keys. An odict implementation that wants to allow access by numeric index should provide explicitly named methods for that purpose. -Carsten -- 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. I'm sorry again. Please don't conclude that others are as uneducated as I am (I haven't studied computer science but mathematics). Speaking about ordered and sorted in the context of collections is not a new terminology I am introducing, but seems to be pretty common in computer science (see, e.g. http://www.gamespp.com/java/dataStructuresInJavaPart6.html). Perhaps Pythonists are not used to that terminology, since they use the term list for an ordered collection. An ordered dictionary is a dictionary whose keys are a (unique) list. Sometimes it is also called a sequence (therefore in the odict implementation, the keys attribute has this name). A unique list, in turn, can also be called an ordered set, so you can also understand an ordered dictionary as a dictionary whose keys are an ordered set. I think all of this is pretty logical ;-) -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Ganesan Rajagopal wrote: 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 Exactly, that's sorted. Ordered means the same there is some order between the existing elements, but there is no magic (i.e. a general comparison function) for ordering new elements. Thus, if you add an element to an ordered collection, it simply gets appended (is considered as the greatest of all elements) by convention, whereas if you add an element to a sorted collection, it will be inserted into the correct place by using the comparison function. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli schrieb: I detest and abhor almost-sequences which can't be sliced (I consider that a defect of collections.deque). If the ordered dictionary records by its sequencing the time order of key insertion, being able to ask for the last 5 keys entered or the first 3 keys entered seem to me to be perfectly natural use cases, and most naturally accomplished by slicing of course, d[-5:] and d[:3] respectively. I agree. A use case was requested: Say your dictionary holds form fields, and you know the last field is always a hidden field you wont to ignore in your output, or your dictionary holds attributes of a database, and you don't want to print the first attribute which is always some kind of uninteresting OID, then you would write for field in d[1:] or for field in d[:-1]. (Otherwise, you would have to write for field in d.keys()[1:] etc.) -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote:
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?
Eso es exactamente lo que yo queria haber!
-- Chris
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
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.). Tom Anderson wrote: 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. Think of it similar as the case of an ordinary dictionary: There is conceptually a set here (the set of keys), but you cannot manipulate it directly, but only through the according dictionary methods. For an ordedred dictionary, there is conceptually a list (or more specifically a unique list). Again you should not manipulate it directly, but only through methods of the ordered dictionary. This sounds at first more complicated, but is in reality more easy. For instance, if I want to put the last two keys of an ordered dict d at the beginning, I would do it as d = d[:-2] + d[-2:]. With the list attribute (called sequence in odict, you would have to write: d.sequence = d.sequence[:-2] + d.sequence[-2:]. This is not only longer to write down, but you also have to know that the name of the attribute is sequence. Python's strength is that you don't have to keep many details in mind because it has a small basic vocabulary and orthogonal use. I prefer the ordered dictionary does not introduce new concepts or attributes if everything can be done intuitively with the existing Python methods and operators. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman wrote: So what do you want returned when you ask for d1[1] ? The member keyed by 1, or the item in position 1 ? In case of conflict, the ordered dictionary should behave like a dictionary, not like a list. So d1[1] should be the member keyed by 1, not the item in position 1. Only in case there is no member keyed by 1, the item in position 1 could be returned, but I think that would be too adventurous a hattrick and can lead to big confusion. Better to raise a KeyError in that case. But no other way to directly manipulate the keys should be provided. Why - don't trust yourself with it ? No, because I think it is not needed if list operations like insert are directly possible on your dictionary. But maybe methods such as setkeys() and setvalues() would be nice to have in addition. Instead of writing d.sequence = new_sequence, I would write d.setkeys(new_sequence). But I'm not sure what to do if new_sequence is not a permutation of the old one. Raise a KeyError? Or even swallow this? For instance d = OrderedDict((1,11), (2,12)) d.setkeys((2, 1)) == d = OrderedDict((2, 11), (1, 12)) d.setkeys((3, 4)) == d = OrderedDict((3, 11), (4, 12)) (or KeyError?) d.setvalues((12, 11)) == d = OrderedDict((1, 12), (2, 11)) d.setvalues((13, 14)) == d = OrderedDict((1, 13), (2, 14)) (always ok) (Or maybe better set_keys in analogy to has_key?) I hesitate making keys and values managed properties, because this would conflict with them being methods in ordinary dicts. Ordered dicts should resemble ordinary dicts as closely as possible. And giving it a different name like sequence I find confusing and unintuitive. A resort could be the following: If keys() is given a sequence as argument, then use this as the new sequence of keys, and similar with values(). This way, no new methods need to be introduced. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman wrote: - the internal keys list should be hidden I disagree. It is exposed so that you can manually change the order (e.g. to create a sorted dict, rather than one ordered by key insertion). What do you *gain* by hiding it ? See my other posting. Of course hiding the list can only be done, if - list methods be mixed in instead In this case, you can change the order directly by using the list methods on the dictionary. Sorting would be an example. Instead of d.sequence = sorted(d.sequence) you could simply write d.sort() which does the same. Hmm... I did consider this. Which list methods would you consider appropriate ? Everything method that does not clash with the use as dictionary. For instance, both lists and dicts have __getitem__ and __setitem__, so im this case, the dictionary method must take precedence. But a dictionary has not __getslice__ and __setslice__, so here the list methods can be used (__getslice__ is actually deprecated, but you get the idea). In some cases, like __delitem__, both have it, but there is no clash. Other interesting methods are sort() and reverse(). Here, we have another problem however: There is not only the list of keys, but also the list of values, and sometimes, as in the case of sort() and reverse(), it would be also nice to have it operate on the list of values. How should this be done? PHP solves it by using two different methods ksort and asort for keys and values. In this notation: d = OrderedDict( (1,13), (3,12), (2,11) ) d.ksort() == d = ( (1,13), (2,11), (3,12) ) d.asort() == d = ( (2,11), (3,12), (1,13) ) Similar for reverse(). If the keys() and values() methods would be extended to be setters, then d.ksort() = d.keys(sorted(d.keys())) and d.asort() = d.values(sorted(d.values())) Anyway, I don't like ksort and asort. If it must be, I'd rather use d.ksort() = d.sortkeys() d.asort() = d.sortvalues() d.sort() could default to one of them (not sure which one). -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fuzzyman wrote: That's not the only use case. Other use cases are to have a specific order, not based on entry time. Simple example : d1 = OrderedDict(some_dict.items()) d1.sequence.sort() d1 is now an ordered dict with the keys in alphabetic order. As I said, I would not need to access the sequence, if I can write d1.sort() or d1.sortkeys() If you don't want to modify sequence, don't. If you want a copy do : seq = d1.sequence[:] This is not needed since you can do the same with: seq = d1.keys() -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Carsten Haese schrieb: Thus quoth the Zen of Python: Explicit is better than implicit. In the face of ambiguity, refuse the temptation to guess. With those in mind, since an odict behaves mostly like a dictionary, [] should always refer to keys. An odict implementation that wants to allow access by numeric index should provide explicitly named methods for that purpose. Exactly. But I don't think in this case such methods would be needed. You easily get the i-th value in the ordered dict as d.values()[i]. -- Chris -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Here is another old posting I just found which again gives the same use cases and semantics: http://mail.python.org/pipermail/python-dev/2005-March/051974.html Keys are iterated over in the order that they are added. Setting a value using a key that compares equal to one already in the dict replaces the value, but not the key, and does not change the iteration order. Removing a key (and value) then re-adding it moves the key to the end of the iteration order. So far all those who would like to have an ordered dict seem to have the same semantics in mind. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Wed, 23 Nov 2005 23:39:22 +0100, Christoph Zwerschke wrote Carsten Haese schrieb: Thus quoth the Zen of Python: Explicit is better than implicit. In the face of ambiguity, refuse the temptation to guess. With those in mind, since an odict behaves mostly like a dictionary, [] should always refer to keys. An odict implementation that wants to allow access by numeric index should provide explicitly named methods for that purpose. Exactly. But I don't think in this case such methods would be needed. You easily get the i-th value in the ordered dict as d.values()[i]. -- Chris True enough, but unless the odict has its list of values on hand, you're asking the odict to build a list of all its values just so that you can get the i'th element. Having a method that does the equivalent of d[d.sequence[i]] would be cleaner and more efficient. -Carsten -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] wrote: ... d.ksort() = d.sortkeys() d.asort() = d.sortvalues() d.sort() could default to one of them (not sure which one). Define JUST d.sort, you can trivially implement the other as d.sort(key=d.get). Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Tom Anderson wrote: Incidentally, can we call that the Larosa-Foord ordered mapping? The implementation, sure. Then it sounds like some kind of rocket science discrete mathematics stuff But math folks usually name things after the person(s) who came up with the idea, not just some random implementer. The idea of combining unordered mappings and ordered sequences is older than Python itself. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli schrieb:
Perl hashes now keep track of 'order of keys'? That's new to me, they
sure didn't back when I used Perl!
Maybe I shouldn't have talked about Perl when I'm an ignoramus about
that language... You're right, Perl has unordered arrays. That was new
to me since I associate the term array always with ordered and I
just remembered that PHP's assoc arrays are similar to Perl's but in
fact, and the examples I have read did not mention about that problem.
What about PHP?
You can conclude that PHP's assoc arrays are ordered from the fact that
the language provides a ksort() function to order the keys. And I think
PHP's insertion order is the one I mentioned in my last post.
Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
first insertion (since the last deletion if any) is ONE unambiguous
definition, but surely not _the_ ONE with emphasis on ``the''.
I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
*last* insertion, for example; indeed if phrased as upon insertion, put
the key at the end of the sequence (whether it was already elsewhere in
the sequence of not), with no need for conditionals regarding previous
existence, it might appear more conceptually compact.
But it would not satisfy the concept of keys of a dictionary which are
always unique.
BTW, there are some boundary conditions that should be fulfilled for the
insertion order, most obviously:
If you define an ordered dict that way:
d = odict()
d['a'] = 1
d['b'] = 2
d['c'] = 3
The keys should then be orderes as ('a', 'b', 'c').
Anyway -- subclassing dict to implement your definition is reasonably
easy, and we could put the resulting package on the Cheese Shop. I hope
python.org keeps good enough statistics to be able to tell us, a couple
months later, how many people downloaded said package, vs how many
people downloaded a complete Python distro; of course, that ratio is
biased (in favour of the package) by the fact that many people already
have a complete distro available, while initially nobody would have the
package, but if we measure when things settle, after letting a month of
two or 'transient' pass, that effect might be lessened.
That would be also biased (in favour of Python) by the fact that
probably very little people would look for and use the package in the
cheese shop if they were looking for ordered dicts. I for example would
probably use ordered dicts if they were part of the standard lib, but
not if I have to install it as an obscure separate package. So I don't
think that will give us a real clue how many people would like ordered
dicts in the standard lib.
But anyway, if I find some time, I will research a little bit more about
the issue and create such a package, because it seems to me that the
existing packages and recipes are not really satisfying and you're right
it seems to be reasonably easy. It's on my todo list now...
-- Christoph
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter schrieb: Ok, so if not in the standard library, what is the problem? Can't find what you want with google and PyPI etc.? Or haven't really settled on what your _requirements_ are? That seems to be the primary problem people who complain with why no sprollificator mode? questions. What I don't understand is why legitimate questions such as why are there no ordered dictionaries are immediately interpreted as *complaints* and not just as questions. If I ask such a question, I am not complaining but trying to simply figure out *why* there is no such thing. Probably there are reasons and all I want to know is find these reasons and learn a little bit more about Python in doing so. Why can't such questions be discussed in a factual, calm and friendly way? They don't know what they really mean when it comes down to a DYFR (Define Your Felicitous Requirements) challenge. I don't think that this was true in this case, and even if this is the outcome, those who asked the question will have learned something. I think a discussion group is not there for only presenting mature, sophisticated thoughts and concepts, but also for thinking loud together with other about these issues. We all know that clarifying our thoughts works often best if you discuss them with others. And I think that's one purpose of discussion lists. Asking questions should not be immediately be discouraged, even silly questions. If it is really a FAQ, you can simply point to the FAQ or add the answer in the FAQ list if it is missing there. -- Chris -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Alex Martelli wrote: What about PHP? Thanks! according to some random PHP documentation I found on the intarweb: An array in PHP is actually an ordered map. A map is a type that maps values to keys. and later: A key may be either an integer or a string. If a key is the standard representation of an integer, it will be interpreted as such (i.e. 8 will be interpreted as 8, while 08 will be interpreted as 08). Floats in key are truncated to integer. and later: You cannot use arrays or objects as keys. Doing so will result in a warning: Illegal offset type. at which point my brain raised an exception. /F -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote:
d = OrderedDict(); d[1]='one'; d[2]='two' = list(d) = [1, 2]
ok, now we do d[1]='ein' and what is the order? list(d) = [2, 1] ??
Or do replacements not count as insertions?
If you simply set a value for a key that already exists, the order
should not be changed. I think this is intuitive.
Or maybe you want to permit append and NOT prevent
[('a',1), ('a':2)] and maybe d['a'] = [1, 2] ???
You could ask the same question about dict. I think that is not an
option. Why should you want odict behave different than dict?
I still believe that the concept of an ordered dictionary (behave
like dict, only keep the order of the keys) is intuitive and doesn't
give you so much scope for ambiguity. But probably I need to work on an
implementation to become more clear about possible hidden subtleties.
-- Christoph
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: That would be also biased (in favour of Python) by the fact that probably very little people would look for and use the package in the cheese shop if they were looking for ordered dicts. Does anyone actually use this site? While the Vaults offered a nice place and a nice interface the Cheese Shop has the appeal of a code slum. Kay -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Fredrik Lundh wrote: [snip..] You're right; I found creating a Larosa/Foord OrderedDict in this example to be even 8 times slower than an ordinary dict. However, two things need to be said here: 1) The dictionary in my exmaple was pretty small (only 3 items), so you are not really measuring the performance of the ordered dict, but mainly the overhead of using a user derived class in comparison with the built-in dict type. And 2) the implementation by Larosa/Foord is very slow and can be easily improved, for instance like that: def __init__(self, init_val = ()): dict.__init__(self, init_val) self.sequence = [x[0] for x in init_val] But that doesn't allow you to create an ordered dict from another ordered dict. It also allows duplicates in the sequence attribute. It's a useful idea though. Thanks Fuzzyman http://www.voidspace.org.uk/python/index.shtml With this change, creating the ordered dictionary is considerably faster and for an average size dictionary, the factor of 8 pretty quickly converges against 1. But of course, it will always be slower since it is constructed on top of the built-in dict. In end effect, you always have to maintain a sequence *plus* a dictionary, which will be always slower than a sheer dictionary. The ordered dictionary class just hides this uglyness of having to maintain a dictionary plus a sequence, so it's rather an issue of convenience in writing and reading programs than a performance issue. It may be different if the ordered dict would be implemented directly as an ordered hash table in C. -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Kay Schluehr wrote: Christoph Zwerschke wrote: That would be also biased (in favour of Python) by the fact that probably very little people would look for and use the package in the cheese shop if they were looking for ordered dicts. Does anyone actually use this site? While the Vaults offered a nice place and a nice interface the Cheese Shop has the appeal of a code slum. Hmmm.. it's *the* repository for Python code. I expect quite a few people use it... :-) Fuzzyman http://www.voidspace.org.uk/python/index.shtml Kay -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On Tue, 22 Nov 2005 09:20:34 +0100, Fredrik Lundh wrote: Tom Anderson wrote: Incidentally, can we call that the Larosa-Foord ordered mapping? The implementation, sure. Then it sounds like some kind of rocket science discrete mathematics stuff But math folks usually name things after the person(s) who came up with the idea, not just some random implementer. No no no! In maths things are usually named after Euler, or the first person to discover them after Euler. -- Steven. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: But please see my other reply: If the dictionary has more than 3 items (say 10 or 20), and an effective ordered dict is used, it's not really a lot slower. At least if we are talking about a situation were on demand is always. So, on the other side there isn't such a big performance loss when using ordered dictionaries as well. There is no performance issue involved with this usecase at all! It doesn't matter if it's hundreds of tuples of strings in a list if it's supposed to be presented in a GUI. Recreating a dict from that is bound to be magnitudes faster than getting the stuff visible on the screen, at least if we're talking web apps. So is using a reasonable odict implementation, if that's what you want. I think the issue is not to overload the already extensive standard library with trivial things that can easily be replaced by your own three line wrapper, especially if there are a number of different semantics that could be imagined for such a thingie. The C++ std lib has an ordered dict class called map, and that's ordered by key. Others suggested ordering by value, and there are a number of different interpretations of the 'order by insertion time' theme in the air. This clearly smells like fix your own thing and leave it out of the standard library. With one of these solutions picked as Python's ordered dict, we'll make things slightly more convenient for a few programmers and just burden others with something that sounds right for them, but turns out not to solve their problems. Or, we could try to make a bunch of different solution, increasing the cognitive burden for all who learn Python while solving non-problems. This just isn't going to happen! -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Bengt Richter wrote: Ok, so if not in the standard library, what is the problem? Can't find what you want with google and PyPI etc.? Or haven't really settled on what your _requirements_ are? That seems to be the primary problem people who complain with why no sprollificator mode? questions. They don't know what they really mean when it comes down to a DYFR (Define Your Felicitous Requirements) challenge. So DYFR ;-) Beat me. I am not the one asking the question. parsing or not parsing is not the point, and parsing/converting is still create a new view of an existing data structure. So you'd like the mechanics to be automated and hidden? Then you need to DYFR for using the black box you want. Methods, semantics. Lose you. don't know what you want to say. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Bengt Richter schrieb: Ok, so if not in the standard library, what is the problem? Can't find what you want with google and PyPI etc.? Or haven't really settled on what your _requirements_ are? That seems to be the primary problem people who complain with why no sprollificator mode? questions. What I don't understand is why legitimate questions such as why are there no ordered dictionaries are immediately interpreted as *complaints* and not just as questions. If I ask such a question, I am not complaining but trying to simply figure out *why* there is no such thing. Probably there are reasons and all I want to know is find these reasons and learn a little bit more about Python in doing so. Why can't such questions be discussed in a factual, calm and friendly way? Using why can't is already too much. Even you turn it into is there a thing for ordered dict, you would get similar treatment Get used to it :-) They don't know what they really mean when it comes down to a DYFR (Define Your Felicitous Requirements) challenge. I don't think that this was true in this case, and even if this is the outcome, those who asked the question will have learned something. I think a discussion group is not there for only presenting mature, sophisticated thoughts and concepts, but also for thinking loud together with other about these issues. We all know that clarifying our thoughts works often best if you discuss them with others. And I think that's one purpose of discussion lists. Asking questions should not be immediately be discouraged, even silly questions. If it is really a FAQ, you can simply point to the FAQ or add the answer in the FAQ list if it is missing there. Well, different groups has different personality, just don't be scared. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: Fredrik Lundh wrote: I'll repeat this one last time: for the use cases presented by Zwerschke and bonono, using a list as the master data structure, and creating the dictionary on demand, is a lot faster than using a ready-made ordered dict implementation. if you will access things via the dictionary a lot, you can cache the dictionary somewhere. if not, you can recreate it several times and still get a net win. You're right in pointing out that the advantage of ordered dictionaries (unless you use an omptimized C implementation) is not a performance gain. But please see my other reply: If the dictionary has more than 3 items (say 10 or 20), and an effective ordered dict is used, it's not really a lot slower. At least if we are talking about a situation were on demand is always. So, on the other side there isn't such a big performance loss when using ordered dictionaries as well. The advantage of using an ordered dictionary is that you can set up your ordered dictionary (say, describing your database columns) once, and then can access it in any way you like in the following: Iterate over it in a guaranteed order or access item, always refering to the same object, without needing to care about building and caching auxiliary objects with different names depending on what you are doing. Well, I don't think performance is the concern(at least not for me), but how best to blend with the rest of the code which I have no interest to explain as I am not here to convincing anyone for such a thing. I just present a use case, if they see it, fine. If not, that is fine too. But I did learn something that creating a dict on a list cost me nothing, I would be less worry about the performance hit in the future. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
On 22 Nov 2005 01:41:44 -0800, Kay Schluehr [EMAIL PROTECTED] wrote: Does anyone actually use this site? While the Vaults offered a nice place and a nice interface the Cheese Shop has the appeal of a code slum. Looking at the Cheese Shop's home page at http://cheeseshop.python.org/pypi, which lists recent package updates, three packages were updated on 11/22, and three on 11/21. Two on 11/20, six on 11/19 (someone was busy!). Looking at the Vaults's 'latest' page at http://py.vaults.ca/apyllo.py?a=l, two packages were updated on 08/23, and five on 08/06. What would improve the Cheese Shop's interface for you? --amk -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
A.M. Kuchling wrote: On 22 Nov 2005 01:41:44 -0800, Kay Schluehr [EMAIL PROTECTED] wrote: Does anyone actually use this site? While the Vaults offered a nice place and a nice interface the Cheese Shop has the appeal of a code slum. Looking at the Cheese Shop's home page at http://cheeseshop.python.org/pypi, which lists recent package updates, three packages were updated on 11/22, and three on 11/21. Two on 11/20, six on 11/19 (someone was busy!). Looking at the Vaults's 'latest' page at http://py.vaults.ca/apyllo.py?a=l, two packages were updated on 08/23, and five on 08/06. What would improve the Cheese Shop's interface for you? --amk From the treasures of the vaults to cheese shops - an upside down evolution :( Personally I find the usability of the Vaults quite well and it's design o.k. I guess it is a technical detail that causes the Vaults to be phased out. If I'd try something more innovative by myself I'd think about accessing and filtering packages through the Python console itself. Probably an enhanced standard console enabling SQL commands. Updates of a local database ( e.g. SQLite ) should be cheap and may be performed by only one request. Searching, filtering, loading, installing would be done in a Python+SQL environment. Kay -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Of course ours is ordered *and* orderable ! You can explicitly alter the sequence attribute to change the ordering. I think we're looking at improving performance based on some of the suggestions here - as well as possibly widening it to include some of the alternative use cases. (Or at least Nicola Larosa will do it and I'll criticise it). All for another day though... Fuzzyman http://www.voidspace.org.uk/python/index.shtml -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Fredrik Lundh [EMAIL PROTECTED] wrote: ... But math folks usually name things after the person(s) who came up with the idea, not just some random implementer. The idea of Wrong: you're forgetting Stigler's Law of Misonomy (which I imagine must have NOT been discovered by Stigler...;-). The Poisson distribution was in fact described earlier by Bernoulli, Gosset's z-test is universally known as Student's t-test, etc, etc. Salsburg's delightful The Lady Tasting Tea has a lot of fun with Stigler's law in the footnotes...;-) Alex -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote: I still believe that the concept of an ordered dictionary (behave like dict, only keep the order of the keys) is intuitive and doesn't give you so much scope for ambiguity. Sure. Others think so too. The problem is that if you and these other people actually write down exactly how this unambigous ordered dict should behave, you'll end up with a dozen different sets of semantics, which can be divided in at least three main groups. People use different idioms, and often gather collections of classes and functions that fit their style of coding and their typical problem domains. There is nothing wrong with that, and they might well be made publically available if they are more generally useful. When adding things to the standard library, there are some more things to consider, particularly for something general such as an odict class: Is is general enough, and does it add enough value to outweigh the increased cognitive burden of more classes/functions/types in the library? For a beginner, it's easy to believe that things would be easier if the tool you use had already solved the problem you have at hand for you, but it turns out that the world has so many problems, that you would end up with a impenetrable forest of standard library modules if we actually tried to achieve this. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke [EMAIL PROTECTED] wrote:
Alex Martelli schrieb:
Perl hashes now keep track of 'order of keys'? That's new to me, they
sure didn't back when I used Perl!
Maybe I shouldn't have talked about Perl when I'm an ignoramus about
that language... You're right, Perl has unordered arrays. That was new
to me since I associate the term array always with ordered and I
just remembered that PHP's assoc arrays are similar to Perl's but in
fact, and the examples I have read did not mention about that problem.
Perl's _arrays_ are a bit like Python _lists_, and ordered; it's the
_hashes_ that are a bit like Python _dicts_, and unordered. PHP's use
of array for both concepts may indeed be a bit confusing.
What about PHP?
You can conclude that PHP's assoc arrays are ordered from the fact that
the language provides a ksort() function to order the keys. And I think
PHP's insertion order is the one I mentioned in my last post.
Anyway, it would be interesting to examine this in detail and how this
is implemented in other languages.
Yep. After just a bit of research I suspect you're right re PHP but
haven't found a specific reference-manual page URL about it.
first insertion (since the last deletion if any) is ONE unambiguous
definition, but surely not _the_ ONE with emphasis on ``the''.
I see nothing _ambiguous_ (nor _unnatural_) in being interested in the
*last* insertion, for example; indeed if phrased as upon insertion, put
the key at the end of the sequence (whether it was already elsewhere in
the sequence of not), with no need for conditionals regarding previous
existence, it might appear more conceptually compact.
But it would not satisfy the concept of keys of a dictionary which are
always unique.
Why not? Since keys are unique, any 'sequence' of keys is a permutation
of a set, a perfectly well-defined concept.
BTW, there are some boundary conditions that should be fulfilled for the
insertion order, most obviously:
If you define an ordered dict that way:
d = odict()
d['a'] = 1
d['b'] = 2
d['c'] = 3
The keys should then be orderes as ('a', 'b', 'c').
Yep, but both 'first-insertion' and 'latest-insertion' (and many other
rules) meet that constraint.
That would be also biased (in favour of Python) by the fact that
probably very little people would look for and use the package in the
cheese shop if they were looking for ordered dicts. I for example would
probably use ordered dicts if they were part of the standard lib, but
not if I have to install it as an obscure separate package. So I don't
think that will give us a real clue how many people would like ordered
dicts in the standard lib.
A package on cheese shop need not be obscure -- that depends on
announcing it well, etc. And the standard library is so huge that many
things inside IT are in fact obscure -- I find myself often pointing out
standard-library solutions to rather experienced Pythonistas who had
been rolling their own, unaware of the stdlib alternative (thus making
the stdlib even bigger has a cost...). So, I don't think this effect
invalidates the experiment; while not all who download an add-on would
like it in the stdlib, and vice versa, there is surely a correlation
between amount of interest/need for the add-on's functionality, and both
rate of downloads as well as interest in having it in the stdlib.
But anyway, if I find some time, I will research a little bit more about
the issue and create such a package, because it seems to me that the
existing packages and recipes are not really satisfying and you're right
it seems to be reasonably easy. It's on my todo list now...
It presumably should have a C implementation for speed and a Python one
for wide availability and ease of installation (the latter gives all the
advantages of prototyping in fixing the API c, and is made especially
easy by the existence of UserDict.DictMixin in the stdlib). I'll be
glad to help out with the C part when it gets to that, just holler...
Alex
--
http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
A.M. Kuchling [EMAIL PROTECTED] wrote in message news:[EMAIL PROTECTED] [...] 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Why are there no ordered dictionaries?
Christoph Zwerschke wrote:
But of course, it will always be slower since it is constructed on top
of the built-in dict. In end effect, you always have to maintain a
sequence *plus* a dictionary, which will be always slower than a sheer
dictionary. The ordered dictionary class just hides this uglyness of
having to maintain a dictionary plus a sequence, so it's rather an issue
of convenience in writing and reading programs than a performance issue.
It may be different if the ordered dict would be implemented directly as
an ordered hash table in C.
The problem with hashing is that one is storing data from a possibly
wildly varying range in a set of values with a limited range. That's
where the ordering problems come from in the first place. If one wants
to solve it once and for all one has to give up the speed advantage
that makes hashing so popular. I wonder if optimized C code using
bisect would be very much slower for small ranges?
The current set implementation uses dicts to implement sets, while sets
are a more basic data type than dicts. At least dicts and sets should
be derived from the same type. Just speaking from an intuitive point of
view of course :-)
Here's a sorted dict implementation without using hashes, which maybe
would be fast if implemented in C. The insertion order can be retrieved
using the keys and values lists from the object itself, items() gives a
sorted sequence.
Anton.
NB warning untested code.
When using mutables as keys which is possible by this implementation,
don't change the keys after they're used in the object.
from array import array
class VDict:
def __init__(self,sequence = []):
self.keys = []
self.values = []
self.unranks = array('L',[])
for key,value in sequence:
self[key] = value
def __setitem__(self,key,value):
keys = self.keys
values = self.values
unranks = self.unranks
n = len(keys)
i = self.bisect_left(key)
if i == n or keys[unranks[i]] != key:
keys.append(key)
values.append(value)
unranks.insert(i,n)
else:
values[i] = value
def __getitem__(self,key):
i = self.bisect_left(key)
return self.values[self.unranks[i]]
def bisect_left(self,key, lo=0, hi=None):
keys = self.keys
unranks = self.unranks
if hi is None:
hi = len(keys)
while lo hi:
mid = (lo+hi)//2
if keys[unranks[mid]] key:
lo = mid+1
else:
hi = mid
return lo
def __contains__(self,key):
keys = self.keys
unranks = self.unranks
n = len(keys)
i = self.bisect_left(key)
return i n and keys[unranks[i]] == key
def __len__(self):
return len(self.keys)
def items(self):
keys = self.keys
values = self.values
unranks = self.unranks
return [(keys[i],values[i]) for i in unranks]
def __iter__(self):
return iter(self.items())
def remove(self,key):
keys = self.keys
values = self.values
unranks = self.unranks
n = len(keys)
i = self.bisect_left(key)
x = unranks[i]
if i n and keys[x] == key:
del keys[x]
del values[x]
del unranks[i]
for j,k in enumerate(unranks):
if k x:
unranks[j] -= 1
def test():
V = VDict()
L = [1,2,3]
V[L] = 10
print V[L]
V[L] = 20
print V[L]
V.remove(L)
print V.items()
V = VDict(zip('edcba',range(5)))
print V.items()
print V['d']
V.remove('d')
print V.items()
if __name__=='__main__':
test()
--
http://mail.python.org/mailman/listinfo/python-list
