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 figur
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
--
http://mail.python.org/mailman/l
[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
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
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.
- Compar
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_has
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
>
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 odict
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
> 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 ob
Martin v. Löwis 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 pyt
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.
A
> 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 releas
> 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,
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
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
> 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
--
http://mail.python.org/mailman/lis
>> 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
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 fir
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
> ``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)
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
>
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
-- Adding an ordered directory to collections
Paul,
You seem to be contradicting yourself. You may have never needed an odict,
yet you seem to have implemented one on your own. Maybe you needed one but
did not realize it?
Shane
> 5. The more I think and write about this, the more struc
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 Pyth
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',
-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.
T
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 str
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)
- `StableDic
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 co
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
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
32 matches
Mail list logo
