Hi all,
I'm a first-time writer here, so excuse me if I say something inappropriate
or such.
Last week, I was reviewing some Python 2.7 modules when I came across the
OrderedDict data structure. After seeing its official implementation and
also after reading through the corresponding PEP, I
Small Status update of the changes incorporated in the PEP:
- The PEP Title was fixed. Of course it's a dictionary not a
directory :-)
- A questions and answers section was added that covers some
of the questions raised here and on the original thread on
python-devel.
-
dbpoko...:
Which should be 12 bytes on a 32-bit machine. I thought the space for
growth factor for dicts was about 12% but it is really 100%.
(Please ignore the trailing .2 in my number in my last post, such
precision is silly).
My memory value comes from experiments, I have created a little
[EMAIL PROTECTED] wrote:
My memory value comes from experiments, I have created a little
program like this:
from memory import memory
def main(N):
m1 = memory()
print m1
d = {}
for i in xrange(N):
d[i] = None
m2 = memory()
print m2
print
Duncan Booth:
What do you get if you change the output to exclude the integers from
the memory calculation so you are only looking at the dictionary
elements themselves? e.g.
The results:
318512 (kbytes)
712124 (kbytes)
20.1529344 (bytes)
Bye,
bearophile
--
Martin v. L.:
However, I think the PEP (author) is misguided in assuming that
making byindex() a method of odict, you get better performance than
directly doing .items()[n] - which, as you say, you won't.
In Python 2.5 .items()[n] creates a whole list, and then takes one
item of such list.
An
Martin v. Löwis martin at v.loewis.de writes:
I think I have lost the thread here, sorry. So I explain again what I
mean. I think for this data structure it's important to keep all the
normal dict operations at the same speed. If you use a C
implementation vaguely similar to my pure
What's the purpose of having list.insert?
It's a convenience function: you don't have to write a loop to move all
items to a later index. Any reformulation of it is easy to get wrong,
and difficult to read.
One creates tons of unnecessary method calls, the other creates a full
blown list
Wow, I was completely wrong about sorted dicts and odicts.
On Jun 17, 4:21 am, [EMAIL PROTECTED] wrote:
mean. I think for this data structure it's important to keep all the
normal dict operations at the same speed. If you use a C
Why keep the normal dict operations at the same speed? There is
dbpoko...:
Why keep the normal dict operations at the same speed? There is a
substantial cost this entails.
I presume now we can create a list of possible odict usages, because I
think that despite everyone using it for different purposes, we may
find some main groups of its usage. I use odicts
On Jun 16, 1:37 am, Armin Ronacher [EMAIL PROTECTED]
wrote:
Abstract
This PEP proposes an ordered dictionary as a new data structure for
the ``collections`` module, called odict in this PEP for short. The
proposed API incorporates the experiences gained from working with
similar
On Jun 18, 3:15 pm, [EMAIL PROTECTED] wrote:
In Python 2.5 a dict(int:None) needs about 36.2 bytes/element. I am
suggesting to add 2 pointers, to create a linked list, so it probably
becomes (on 32 bit systems) about 44.2 bytes/pair.
PyDictEntry is
typedef struct {
Py_ssize_t me_hash;
On Jun 17, 12:28 am, Martin v. Löwis [EMAIL PROTECTED] wrote:
My guess is that the two main memory allocate/deallocate cases are 1)
appending a new item to the end, and 2) GC'ing the entire data
structure. I would optimize these 2 at the expense of all others.
Does that include dictionary
Martin v. L.:
http://wiki.python.org/moin/TimeComplexity
Thank you, I think that's not a list of guarantees, while a list of
how things are now in CPython.
If so, what's the advantage of using that method over d.items[n]?
I think I have lost the thread here, sorry. So I explain again what I
I think I have lost the thread here, sorry. So I explain again what I
mean. I think for this data structure it's important to keep all the
normal dict operations at the same speed. If you use a C
implementation vaguely similar to my pure python recipe you can
perform the del in O(1) too,
Well, this has become something of a rant,
Indeed - and I was only asking about .byindex(n) :-)
I don't know why that method is included in the PEP. Speculating
myself, I assume that the PEP author wants it to be O(1). As
bearophile explains, that's not possible/not a good idea.
As for
Abstract
This PEP proposes an ordered dictionary as a new data structure for
the ``collections`` module, called odict in this PEP for short. The
proposed API incorporates the experiences gained from working with
similar implementations that exist in various real-world applications
and
On Jun 16, 10:37 am, Armin Ronacher [EMAIL PROTECTED]
wrote:
Abstract
This PEP proposes an ordered dictionary as a new data structure for
the ``collections`` module, called odict in this PEP for short. The
proposed API incorporates the experiences gained from working with
similar
Armin Ronacher [EMAIL PROTECTED] writes:
This PEP proposes an ordered dictionary as a new data structure for
the ``collections`` module, called odict in this PEP for short.
A welcome addition.
Since we're not proposing a built-in type, could we choose a name that
is more explicit, and
Armin Ronacher schrieb:
Other implementations of ordered dicts in various Python projects or
standalone libraries, that inspired the API proposed here, are:
- `odict in Babel`_
- `OrderedDict in Django`_
- `The odict module`_
- `ordereddict`_ (a C implementation of the odict module)
-
Oh, very good, better late than never.
This is my pure Python version, it performs get, set and del
operations too in O(1):
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/498195
Working with C such data structure becomes much faster, because it can
use true pointers.
Then another data
-On [20080616 10:41], Armin Ronacher ([EMAIL PROTECTED]) wrote:
This PEP proposes an ordered dictionary as a new data structure for
the ``collections`` module, called odict in this PEP for short.
I fully support adding this. In my work I have had to create this datatype a
few times already.
The
This gets my +1, for what its worth.
I don't really see a good reason not to include the insert() method,
however. I don't see that it would complicate things much, if at all.
d = odict([('a', 42), ('b', 23)])
d.insert(1, ('c', 19))
d
collections.odict([('a', 42), ('c', 19), ('b', 23)])
1. With the current dict, the following code
a = { A : 1, B : 2 }
b = { B : 2, A : 1 }
a==b evaluates to True. I assume that if these were odicts, this
would evaluate to False.
2. Will odict.byindex support slicing?
3. Will odict inherit from dict?
4. The current dict API (as of Python 2.5)
internally might have simplified things for me, instead of the combined list
and dict that I have now).
-- Paul
-Original Message-
From: Shane Geiger [mailto:[EMAIL PROTECTED]
Sent: Monday, June 16, 2008 9:20 AM
To: Paul McGuire
Cc: python-list@python.org
Subject: Re: PEP 372 -- Adding
I'm very happy to see this PEP. I have needed to use ordered
dictionaries many times, and this has always felt to me like a
surprising omission from Python.
--
http://mail.python.org/mailman/listinfo/python-list
On 16 juin, 10:37, Armin Ronacher [EMAIL PROTECTED] wrote:
Abstract
This PEP proposes an ordered dictionary as a new data structure for
the ``collections`` module, called odict in this PEP for short. The
proposed API incorporates the experiences gained from working with
similar
``odict.byindex(index)``
Index-based lookup is supported by ``byindex()`` which returns
the key/value pair for an index, that is, the position of a
key in the ordered dict. 0 is the first key/value pair, -1
the last.
d.byindex(2)
Martin v. L.:
For this API, I think it's important to make some performance guarantees.
I may appreciate them for all Python collections :-)
It seems fairly difficult to make byindex O(1), and
simultaneously also make insertion/deletion better than O(n).
It may be possible to make both of
On Jun 16, 5:24 pm, Martin v. Löwis [EMAIL PROTECTED] wrote:
``odict.byindex(index)``
Index-based lookup is supported by ``byindex()`` which returns
the key/value pair for an index, that is, the position of a
key in the ordered dict. 0 is the first key/value
For this API, I think it's important to make some performance guarantees.
I may appreciate them for all Python collections :-)
See
http://wiki.python.org/moin/TimeComplexity
It seems fairly difficult to make byindex O(1), and
simultaneously also make insertion/deletion better than O(n).
My guess is that the two main memory allocate/deallocate cases are 1)
appending a new item to the end, and 2) GC'ing the entire data
structure. I would optimize these 2 at the expense of all others.
Does that include dictionary lookups?
Regards,
Martin
--
32 matches
Mail list logo
