Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Python: Dev

Proposal: add odict to collections

 

 

First page Previous page 1 2 3 Next page Last page  View All Python dev RSS feed   Index | Next | Previous | View Threaded


armin.ronacher at active-4

Jun 14, 2008, 4:39 PM

Post #1 of 54 (6918 views)
Permalink
Proposal: add odict to collections

Hi,

I noticed lately that quite a few projects are implementing their own
subclasses of `dict` that retain the order of the key/value pairs.
However half of the implementations I came across are not implementing
the whole dict interface which leads to weird bugs, also the performance
of a Python implementation is not that great.

To fight that problem I want to proposed a new class in "collections"
called odict which is a dict that keeps the items sorted, similar to
a PHP array.

The interface would be fully compatible with dict and implemented as
dict subclass. Updates to existing keys does not change the order of
a key but new keys are inserted at the end.

Additionally it would support slicing where a list of key, value tuples
is returned and sort/reverse/index methods that work like their list
equivalents. Index based lookup could work via odict.byindex().

An implementation of that exists as part of the ordereddict implementation
which however goes beyond that and is pretty much a fork of the python
dict[1].

Some reasons why ordered dicts are a useful feature:

- in XML/HTML processing it's often desired to keep the attributes of
an tag ordered during processing. So that input ordering is the
same as the output ordering.

- Form data transmitted via HTTP is usually ordered by the position
of the input/textarea/select field in the HTML document. That
information is currently lost in most Python web applications /
frameworks.

- Eaiser transition of code from Ruby/PHP which have sorted
associative arrays / hashmaps.

- Having an ordered dict in the standard library would allow other
libraries support them. For example a PHP serializer could return
odicts rather then dicts which drops the ordering information.
XML libraries such as etree could add support for it when creating
elements or return attribute dicts.

Regards,
Armin


[1]: http://www.xs4all.nl/~anthon/Python/ordereddict/

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


fuzzyman at voidspace

Jun 14, 2008, 4:44 PM

Post #2 of 54 (6820 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Armin Ronacher wrote:
> Hi,
>
> I noticed lately that quite a few projects are implementing their own
> subclasses of `dict` that retain the order of the key/value pairs.
> However half of the implementations I came across are not implementing
> the whole dict interface which leads to weird bugs, also the performance
> of a Python implementation is not that great.
>
>

I'm +1 - but this proposal has been made many times before and people
always argue about what features are needed or desirable. :-(

Michael Foord

> To fight that problem I want to proposed a new class in "collections"
> called odict which is a dict that keeps the items sorted, similar to
> a PHP array.
>
> The interface would be fully compatible with dict and implemented as
> dict subclass. Updates to existing keys does not change the order of
> a key but new keys are inserted at the end.
>
> Additionally it would support slicing where a list of key, value tuples
> is returned and sort/reverse/index methods that work like their list
> equivalents. Index based lookup could work via odict.byindex().
>
> An implementation of that exists as part of the ordereddict implementation
> which however goes beyond that and is pretty much a fork of the python
> dict[1].
>
> Some reasons why ordered dicts are a useful feature:
>
> - in XML/HTML processing it's often desired to keep the attributes of
> an tag ordered during processing. So that input ordering is the
> same as the output ordering.
>
> - Form data transmitted via HTTP is usually ordered by the position
> of the input/textarea/select field in the HTML document. That
> information is currently lost in most Python web applications /
> frameworks.
>
> - Eaiser transition of code from Ruby/PHP which have sorted
> associative arrays / hashmaps.
>
> - Having an ordered dict in the standard library would allow other
> libraries support them. For example a PHP serializer could return
> odicts rather then dicts which drops the ordering information.
> XML libraries such as etree could add support for it when creating
> elements or return attribute dicts.
>
> Regards,
> Armin
>
>
> [1]: http://www.xs4all.nl/~anthon/Python/ordereddict/
>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev [at] python
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/fuzzyman%40voidspace.org.uk
>


--
http://www.ironpythoninaction.com/
http://www.theotherdelia.co.uk/
http://www.voidspace.org.uk/
http://www.ironpython.info/
http://www.resolverhacks.net/

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


marek at xivilization

Jun 14, 2008, 4:53 PM

Post #3 of 54 (6820 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Hi,

Armin Ronacher <armin.ronacher <at> active-4.com> writes:

> To fight that problem I want to proposed a new class in "collections"
> called odict which is a dict that keeps the items sorted, similar to
> a PHP array.

I'm also +1 on this. I've used the implementation you mentioned in a compiler
project of mine and found it to be quite useful. It is hard for me to mention
any other uses but there definitely are many occasions where people need them
and either go for (key, value)-tuples or use some lib which does only provide
this single data type. I am pretty optimistic that the addition will find its
usecases, once it is in the stdlib.

regards,
Marek

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


nd at perlig

Jun 14, 2008, 4:57 PM

Post #4 of 54 (6806 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

* Armin Ronacher wrote:

> Some reasons why ordered dicts are a useful feature:
>
> - in XML/HTML processing it's often desired to keep the attributes of
> an tag ordered during processing. So that input ordering is the
> same as the output ordering.
>
> - Form data transmitted via HTTP is usually ordered by the position
> of the input/textarea/select field in the HTML document. That
> information is currently lost in most Python web applications /
> frameworks.
>
> - Eaiser transition of code from Ruby/PHP which have sorted
> associative arrays / hashmaps.
>
> - Having an ordered dict in the standard library would allow other
> libraries support them. For example a PHP serializer could return
> odicts rather then dicts which drops the ordering information.
> XML libraries such as etree could add support for it when creating
> elements or return attribute dicts.

I find this collection of cases pretty weak as an argument for implementing
that in the stdlib. A lot of special purpose types would fit into such
reasoning, but do you want to have all of them maintained here?

nd
--
Da fällt mir ein, wieso gibt es eigentlich in Unicode kein
"i" mit einem Herzchen als Tüpfelchen? Das wär sooo süüss!

-- Björn Höhrmann in darw
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


jimjjewett at gmail

Jun 14, 2008, 7:06 PM

Post #5 of 54 (6811 views)
Permalink
Proposal: add odict to collections [In reply to]

The odict (as proposed here, ordered on time of key insertion) looks
like a close match to the dlict needed by some of the optimization
proposals.

http://python.org/dev/peps/pep-0267/

-jJ
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


guido at python

Jun 14, 2008, 8:26 PM

Post #6 of 54 (6814 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

On Sat, Jun 14, 2008 at 4:57 PM, André Malo <nd [at] perlig> wrote:
> * Armin Ronacher wrote:
>
>> Some reasons why ordered dicts are a useful feature:
>>
>> - in XML/HTML processing it's often desired to keep the attributes of
>> an tag ordered during processing. So that input ordering is the
>> same as the output ordering.
>>
>> - Form data transmitted via HTTP is usually ordered by the position
>> of the input/textarea/select field in the HTML document. That
>> information is currently lost in most Python web applications /
>> frameworks.
>>
>> - Eaiser transition of code from Ruby/PHP which have sorted
>> associative arrays / hashmaps.
>>
>> - Having an ordered dict in the standard library would allow other
>> libraries support them. For example a PHP serializer could return
>> odicts rather then dicts which drops the ordering information.
>> XML libraries such as etree could add support for it when creating
>> elements or return attribute dicts.
>
> I find this collection of cases pretty weak as an argument for implementing
> that in the stdlib. A lot of special purpose types would fit into such
> reasoning, but do you want to have all of them maintained here?

No, but an ordered dict happens to be a *very* common thing to need,
for a variety of reasons. So I'm +0.5 on adding this to the
collections module. However someone needs to contribute working code.
It would also be useful to verify that it actually fulfills the needs
of some actual use case. Perhaps looking at how Django uses its
version would be helpful.

--
--Guido van Rossum (home page: http://www.python.org/~guido/)
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


talin at acm

Jun 14, 2008, 8:42 PM

Post #7 of 54 (6825 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Michael Foord wrote:
> Armin Ronacher wrote:
>> Hi,
>>
>> I noticed lately that quite a few projects are implementing their own
>> subclasses of `dict` that retain the order of the key/value pairs.
>> However half of the implementations I came across are not implementing
>> the whole dict interface which leads to weird bugs, also the performance
>> of a Python implementation is not that great.
>>
>>
>
> I'm +1 - but this proposal has been made many times before and people
> always argue about what features are needed or desirable. :-(

There's been a lot of controversy/confusion about ordered dicts. One of
the sources of confusion is that people mean different things when they
use the term "ordered dict": In some cases, the term is used to mean a
dictionary that remembers the order of insertions, and in other cases it
is used to mean a sorted dict, i.e. an associative data structure in
which the entries are kept sorted. (And I'm not sure that those are the
only two possibilities.)

I would be more in favor of the idea if we could come up with a less
ambiguous naming scheme.

-- Talin

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


bjourne at gmail

Jun 14, 2008, 9:37 PM

Post #8 of 54 (6822 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

On Sat, Jun 14, 2008 at 11:39 PM, Armin Ronacher
<armin.ronacher [at] active-4> wrote:
> Some reasons why ordered dicts are a useful feature:


And for metaclasses or for LRU caches or for removing duplicates in a
list while maintaining order. I think that the name ordereddict would
be more readable though, and match the existing defaultdict class in
the collections module.


--
mvh Björn
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


hasan.diwan at gmail

Jun 14, 2008, 9:38 PM

Post #9 of 54 (6826 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

2008/6/14 Talin <talin [at] acm>:
> There's been a lot of controversy/confusion about ordered dicts. One of the
> sources of confusion is that people mean different things when they use the
> term "ordered dict": In some cases, the term is used to mean a dictionary
> that remembers the order of insertions, and in other cases it is used to
> mean a sorted dict, i.e. an associative data structure in which the entries
> are kept sorted. (And I'm not sure that those are the only two
> possibilities.)

Have the comparison function passed in as a parameter then, if it's
None, then have it maintain the order of insertion? Something like:
def __init__(self, cmpfunc = None):
self.dict = dict()

def __getattr__(self, key):
try: return self.key

--
Cheers,
Hasan Diwan <hasan.diwan [at] gmail>
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


martin at v

Jun 14, 2008, 9:55 PM

Post #10 of 54 (6815 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

> Have the comparison function passed in as a parameter then, if it's
> None, then have it maintain the order of insertion?

No. This would contribute to the confusion, not resolve it. If it's
called "ordered dictionary", it shouldn't do sorting at all. If it does
sorting, it should be called "sorted dictionary", and mandate a
comparison function (which might default to cmp).

Regards,
Martin
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


wolever at cs

Jun 14, 2008, 9:59 PM

Post #11 of 54 (6819 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

On 14-Jun-08, at 8:39 PM, Armin Ronacher wrote:
> ...
> I noticed lately that quite a few projects are implementing their own
> subclasses of `dict` that retain the order of the key/value pairs.
> ...
I'm +1 on this one too, as there are at least a couple of times in
recent memory when I would have found this useful.

And, as far as questions about the definition of an ordered
dictionary, is there any good reason not to simply treat the dict as
a list? Something like (with the obvious bits left out):

class odict(dict):
def __init__(self, *args): self._order = []
def __setitem__(self, key, val): if key not in self:
self._order.append(key)
def __iter__(self): return self._order
def items(self): return ([item, self[item] for item in self._order])
def sort(self): self._order.sort()
... and so on ...

That way all the order-related functions are well defined, so it
would be hard claim that it doesn't do the "right thing" without
claiming that lists don't do the "right thing".
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


ncoghlan at gmail

Jun 14, 2008, 10:25 PM

Post #12 of 54 (6813 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Talin wrote:
> Michael Foord wrote:
>> Armin Ronacher wrote:
>>> Hi,
>>>
>>> I noticed lately that quite a few projects are implementing their own
>>> subclasses of `dict` that retain the order of the key/value pairs.
>>> However half of the implementations I came across are not implementing
>>> the whole dict interface which leads to weird bugs, also the performance
>>> of a Python implementation is not that great.
>>>
>>>
>>
>> I'm +1 - but this proposal has been made many times before and people
>> always argue about what features are needed or desirable. :-(
>
> There's been a lot of controversy/confusion about ordered dicts. One of
> the sources of confusion is that people mean different things when they
> use the term "ordered dict": In some cases, the term is used to mean a
> dictionary that remembers the order of insertions, and in other cases it
> is used to mean a sorted dict, i.e. an associative data structure in
> which the entries are kept sorted. (And I'm not sure that those are the
> only two possibilities.)
>
> I would be more in favor of the idea if we could come up with a less
> ambiguous naming scheme.

I think Armin's proposal addresses this nicely by the analogy to lists:
the ordered dict is in key insertion order by default, but you can
invoke odict.sort() to sort it instead.

Given the synergy with the Py3k metaclass enhancements, I believe this
would be a good thing to have.

Cheers,
Nick.

--
Nick Coghlan | ncoghlan [at] gmail | Brisbane, Australia
---------------------------------------------------------------
http://www.boredomandlaziness.org
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


armin.ronacher at active-4

Jun 14, 2008, 10:34 PM

Post #13 of 54 (6820 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Guido van Rossum <guido <at> python.org> writes:

>
> On Sat, Jun 14, 2008 at 4:57 PM, André Malo <nd <at> perlig.de> wrote:
> > I find this collection of cases pretty weak as an argument for implementing
> > that in the stdlib. A lot of special purpose types would fit into such
> > reasoning, but do you want to have all of them maintained here?
>
> No, but an ordered dict happens to be a *very* common thing to need,
> for a variety of reasons. So I'm +0.5 on adding this to the
> collections module. However someone needs to contribute working code.
> It would also be useful to verify that it actually fulfills the needs
> of some actual use case. Perhaps looking at how Django uses its
> version would be helpful.

I compared multiple ordered dicts now (including Babel, Django and the
C-implementation I mentioned earlier) and implemented a python version
of the ordered dict as reference implementation:

http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py


Regards,
Armin



_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


armin.ronacher at active-4

Jun 14, 2008, 10:37 PM

Post #14 of 54 (6811 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

BJörn Lindqvist <bjourne <at> gmail.com> writes:

> I think that the name ordereddict would be more readable though, and
> match the existing defaultdict class in the collections module.
While I agree that "ordered" makes more sense, it's pretty stupid to type
with two 'd's right after another.


Regards,
Armin

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


armin.ronacher at active-4

Jun 14, 2008, 10:42 PM

Post #15 of 54 (6807 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Hasan Diwan <hasan.diwan <at> gmail.com> writes:

>
> 2008/6/14 Talin <talin <at> acm.org>:
> > There's been a lot of controversy/confusion about ordered dicts. One of the
> > sources of confusion is that people mean different things when they use the
> > term "ordered dict": In some cases, the term is used to mean a dictionary
> > that remembers the order of insertions, and in other cases it is used to
> > mean a sorted dict, i.e. an associative data structure in which the entries
> > are kept sorted. (And I'm not sure that those are the only two
> > possibilities.)
>
> Have the comparison function passed in as a parameter then, if it's
> None, then have it maintain the order of insertion? Something like:
> def __init__(self, cmpfunc = None):
> self.dict = dict()
>
>
I think that would be contraproductive and would make the constructor
incompatible with the normal dict constructor which accepts keyword
arguments too. Also that dict is just in order, but not sorted by
something. You could still do something like this:

d = odict()
d['Pinguin'] = 'telly'
d['Parrot'] = 'cage'
d['Mouse'] = 'Napoleon'
d.sort(key=lambda x: x[1].lower())

That of course would not sort items inserted after the sort call.

Regards,
Armin

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


python at rcn

Jun 14, 2008, 10:43 PM

Post #16 of 54 (6829 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

From: "Talin" <talin [at] acm>
> There's been a lot of controversy/confusion about ordered dicts.

I think that is why all earlier proposals all died.


> One of
> the sources of confusion is that people mean different things when they
> use the term "ordered dict": In some cases, the term is used to mean a
> dictionary that remembers the order of insertions, and in other cases it
> is used to mean a sorted dict, i.e. an associative data structure in
> which the entries are kept sorted. (And I'm not sure that those are the
> only two possibilities.)

For an insertion order dictionary, there was also a question about
how to handle duplicate keys.

Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?

[(k1,v3), (k2,v2)]
[(k2,v2), (k1,v3)]

The first maintains the original sort order and is consistent with the usual
idea that d[k]=v simply replaces the value but does not alter the hash table.
It is a bit weird though because v3 appears earlier than v2 which was
inserted earlier. It's especially weird for keys that are equal but not
identical: d[0]=v1 d[0.0]=v3. Do you want 0.0 to remain associated
with v3 or should the items list contain a pair that was not in the original
insertion list, (0, v3)?

The second one is a bit weird because a key "loses its place" whenever
the value is updated.

IIRC, previous discussions showed an interest in odicts but that
there were a lot of questions of the specific semantics of the API.
This would no doubt be compounded by attempts to emulate
dict views. Regardless, there should probably be a PEP and
alternate pure python versions should be posted on ASPN so people
can try them out.
post


Raymond

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


armin.ronacher at active-4

Jun 14, 2008, 11:07 PM

Post #17 of 54 (6823 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Raymond Hettinger <python <at> rcn.com> writes:

> For an insertion order dictionary, there was also a question about
> how to handle duplicate keys.
>
> Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?
>
> [(k1,v3), (k2,v2)]
> [(k2,v2), (k1,v3)]
All the ordered dict implementations I saw behave like this:

>>> odict([(1, 'foo'), (2, 'bar'), (1, 'baz')]).items()
[(1, 'baz'), (2, 'bar')]

And that makes sense because it's consistent with the dict interface.
But I guess that is a pretty small issue and most of the time you are
not dealing with double keys when using an ordered dict.

> IIRC, previous discussions showed an interest in odicts but that
> there were a lot of questions of the specific semantics of the API.
No doubt there. But

> This would no doubt be compounded by attempts to emulate
> dict views. Regardless, there should probably be a PEP and
> alternate pure python versions should be posted on ASPN so people
> can try them out.
That's true, but by now there are countless of ordered dict implementations
with a mostly-compatible interface and applications and libraries are
using them already.

I have an example implementation here that incorporates the ideas
from ordereddict, Django's OrderedDict and Babel's odict:

http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py


Regards,
Armin

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


cesare at pronto

Jun 14, 2008, 11:20 PM

Post #18 of 54 (6830 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

In data 15 giugno 2008 alle ore 07:43:32, Raymond Hettinger <python [at] rcn> ha scritto:

> For an insertion order dictionary, there was also a question about
> how to handle duplicate keys.
>
> Given odict([(k1,v1), (k2,v2), (k1,v3)]), what should the odict.items() return?
>
> [(k1,v3), (k2,v2)]
> [(k2,v2), (k1,v3)]
>
> The first maintains the original sort order and is consistent with the usual
> idea that d[k]=v simply replaces the value but does not alter the hash table.
> It is a bit weird though because v3 appears earlier than v2 which was
> inserted earlier. It's especially weird for keys that are equal but not
> identical: d[0]=v1 d[0.0]=v3. Do you want 0.0 to remain associated
> with v3 or should the items list contain a pair that was not in the original
> insertion list, (0, v3)?
>
> The second one is a bit weird because a key "loses its place" whenever
> the value is updated.
>
> IIRC, previous discussions showed an interest in odicts but that
> there were a lot of questions of the specific semantics of the API.
> This would no doubt be compounded by attempts to emulate
> dict views. Regardless, there should probably be a PEP and
> alternate pure python versions should be posted on ASPN so people
> can try them out.
> post
>
>
> Raymond

The same problem happens with dictionary updates:

d = {}
d[k1] = v1
d[k2] = v2
d[k1] = v3

The last instruction just replaces the existing entry, so I'm +0 for the first result.

Cesare
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


dbpokorny at gmail

Jun 15, 2008, 12:09 AM

Post #19 of 54 (6826 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

On Jun 14, 4:39 pm, Armin Ronacher <armin.ronac...@active-4.com>
wrote:
> - in XML/HTML processing it's often desired to keep the attributes of
> an tag ordered during processing. So that input ordering is the
> same as the output ordering.

Munging XML is a niche.

>
> - Form data transmitted via HTTP is usually ordered by the position
> of the input/textarea/select field in the HTML document. That
> information is currently lost in most Python web applications /
> frameworks.

If you don't like the fact that your web application framework loses
the order of its key:value pairs relative to the page, then you should
bring it up with the developers.

Ordered dicts, dicts that remember the chronological order of their
insertion, don't sound generally useful. In contrast, sorted dicts
sound appealing, but I can't think of any use cases where
sorted(mydict.keys()) fails to be effective; it seems to me the main
advantage of a sorted dict is that you don't have to remember to sort
the keys every time you want to use them.

> Additionally it would support slicing where a list of key, value tuples
> is returned and sort/reverse/index methods that work like their list
> equivalents. Index based lookup could work via odict.byindex().

Slicing tuples, lists, and strings return objects of the same type, so
slicing a sorted dict should return a sorted dict.

A sorted dict is the same data structure as a Berkeley DB table. Why
not use the term 'table' instead of 'sorteddict'?

Unless I am missing something big, the implementation of new key
insert for sorteddict looks inefficient - on average you have to move
half of your elements over one space. A B tree or B+ tree (or other
tree) would be a more efficient algorithm.

-1 for ordered dict
+1 for sorted dict

David
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


python at rcn

Jun 15, 2008, 12:12 AM

Post #20 of 54 (6821 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

From: "Cesare Di Mauro" <cesare [at] pronto>
> The same problem happens with dictionary updates:
>
> d = {}
> d[k1] = v1
> d[k2] = v2
> d[k1] = v3
>
> The last instruction just replaces the existing entry, so I'm +0 for the first result.

There's a difference. With dicts, the third insertion *replaces* the value while leaving data structure unmolested. Also, the key
doesn't update (an equal but identical key doesn't get substituted).

With an odict that preserves insertion order, you're talking about *deleting* the old entry and *appending* the new one, complete
with both the new key and new value. If that is the desired behavior, then it becomes impossible to update the value of an odict
entry while leaving its insertion order unchanged. What a bummer.

An alternative behavior is to replace the value, leaving the key in its original position. But then, you've messed-up the
expectation that v2 occurs before v3 eventhough v3 was inserted later. This is especially weird because you keep k1 which was
inserted earlier, not k3 which is equivalent but not necessarily identical.

Neither behavior is de facto, TheRightWay(tm). Each has its uses. Each has its oddities. Each will have its fans who find that
particular way to be the best and most intuitive.

One other issue arises if you choose the approach where updating a value triggers re-ordering -- the the dict view concept no longer
translates very well. With regular dicts, you can update values while iterating. Losing that would be a bummer too.

I don't favor one over the other. Am just pointing-out that the proposal is a little more complex than simply wishing for an
ordered verion of a dictionary and expecting that that wish is self-defining in a way the matches everyone's intuition, use cases,
and expectations.


Raymond

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


martin at v

Jun 15, 2008, 12:41 AM

Post #21 of 54 (6829 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

> I compared multiple ordered dicts now (including Babel, Django and the
> C-implementation I mentioned earlier) and implemented a python version
> of the ordered dict as reference implementation:
>
> http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py

I find the slicing API surprising. IMO, if you do support slicing, then
a) the start and end indices should be the same ones that you also use
in regular indexing.
b) the result should be of the same kind as the thing being sliced, i.e.
an odict.

So I would rather expect

>>> d['c':'spam']
odict.odict([('c', 'd'), ('foo', 'bar')])

The slicing operation that you provide should be spelled as
d.items()[1:3], or, if you don't want to pay the cost of creating
the full items list, then add a method such as d.slice_by_index(1,3).
What's the use case for this operation, anyway?

Regards,
Martin
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


2008a at usenet

Jun 15, 2008, 12:53 AM

Post #22 of 54 (6828 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Armin Ronacher wrote:

> That's true, but by now there are countless of ordered dict
> implementations with a mostly-compatible interface and applications and
> libraries are using them already.

Even worse, most of them are slow, i.e. show a wrong algorithmic
complexity ...

> I have an example implementation here that incorporates the ideas
> from ordereddict, Django's OrderedDict and Babel's odict:
>
> http://dev.pocoo.org/hg/sandbox/raw-file/tip/odict.py

... like your implementation. It is not too hard to get the delitem
O(log n) compared to your O(n), see here:

http://codespeak.net/svn/user/arigo/hack/pyfuse/OrderedDict.py

So many people are implementing this kind of data type but do not really
care about making as fast as it could be ... IMHO yet another reason to
ship a usable implementation with Python.

Kind regards,
Alexander

_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


ncoghlan at gmail

Jun 15, 2008, 1:03 AM

Post #23 of 54 (6822 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

Raymond Hettinger wrote:
> I don't favor one over the other. Am just pointing-out that the
> proposal is a little more complex than simply wishing for an ordered
> verion of a dictionary and expecting that that wish is self-defining in
> a way the matches everyone's intuition, use cases, and expectations.

If you have an odict with first-insertion ordering, it's fairly trivial
to convert it to a dictionary with last-insertion ordering:

class odictlastinsertion(odict):
def __setitem__(self, k, v):
self.pop(k, None)
self[k] = v

As you note, going the other way would be rather difficult, suggesting
that the version ordered by the first key insertion is the more
fundamental structure.

A PEP would definitely be needed to thrash out those kind of issues and
decisions though

Cheers,
Nick.

--
Nick Coghlan | ncoghlan [at] gmail | Brisbane, Australia
---------------------------------------------------------------
http://www.boredomandlaziness.org
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


ncoghlan at gmail

Jun 15, 2008, 1:14 AM

Post #24 of 54 (6816 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

dbpokorny [at] gmail wrote:
> -1 for ordered dict
> +1 for sorted dict

Build the ordered dict, then sort it in-place afterwards, just like a
list (alternatively, build a normal dict then feed sorted(orig.items())
to the ordered dict constructor).

The point of an ordered dict is that unlike a normal dict, the order the
keys are returned is well defined at the interface level, rather than
arbitrary and implementation-defined.

David Wolever's example of a normal dict() with an associated key list
is an excellent way of thinking about the proposed semantics.

Having a fast ordered dict in the standard library also opens up the
possibility of eventually using such a thing for keyword arguments at
some point in the future. How nice would it be to be able to just write:

t = namedtuple(a=1, b=2, c=3)

instead of:

c = namedtuple("a b c")
t = c(a=1, b=2, c=3)

Cheers,
Nick.

--
Nick Coghlan | ncoghlan [at] gmail | Brisbane, Australia
---------------------------------------------------------------
http://www.boredomandlaziness.org
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com


steve at pearwood

Jun 15, 2008, 1:38 AM

Post #25 of 54 (6810 views)
Permalink
Re: Proposal: add odict to collections [In reply to]

On Sun, 15 Jun 2008 02:59:51 pm David Wolever wrote:

> And, as far as questions about the definition of an ordered
> dictionary, is there any good reason not to simply treat the dict as
> a list? Something like (with the obvious bits left out):

Yes.

(1) If you implement the ordered dict as a list of key/value pairs, then
you get order for free, but searching is slow, and so is deletion. If
we wanted O(N) searches, we'd just use a list of tuples :)

(2) If you implement it as a hash table plus a list of keys in insertion
order, then searching the dict is fast, but deletions are slow. Also
you double (?) the amount of memory needed for the keys.


On the other hand... a tree-based implementation would require more
work, and many more decisions (what kind of tree?), would lose the O(1)
behaviour of the hash table, and may end up using just as much memory.
So I wouldn't discount your suggestion.


--
Steven
_______________________________________________
Python-Dev mailing list
Python-Dev [at] python
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/list-python-dev%40lists.gossamer-threads.com

First page Previous page 1 2 3 Next page Last page  View All Python dev RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.