473,320 Members | 2,145 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Re: PEP 372 -- Adding an ordered directory to collections

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 is situations where
an dict is nearly the right data structure, so keeping all operations
close to the time complexity of dicts has a purpose.

but the storage requirements are reduced to 2n from 4n.
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.

Note that computer science is full of strange data structures, so
maybe a skip list can be used here, to increase some operation
timings, and reduce other ones... :-)

Bye,
bearophile
Jun 27 '08 #1
4 2321
On Jun 18, 3:15 pm, bearophileH...@lycos.com 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;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;

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%. In any
case, a pair of lists will take up less space than a dict and a list.
Or the storage could be an array of PyDictEntrys (to cache the hash
values of the keys), an approach that is in some sense halfway between
the others.

There is one advantage of this last approach - I think the amount of
hacking on dictobject.c that would have to take place is minimal. In
fact it almost seems like you could get the desired result by setting
mp->ma_lookup to a new function (and keep most of the rest of the
methods as they are). This seems too easy though, so there might be a
catch.

David
Jun 27 '08 #2
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
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 float((m2 - m1) * 1024) / N
main(20000000)

Where memory is a small module of mine that calls a little known
program that tells how much memory is used by the current Python
process. The results for that run n=20000000 are (first two numbers
are kilobytes, the third number is byte/pair):

1876
633932
32.3612672

It means to store 20_000_000 pairs it requires about 647_000_000
bytes, Python 2.5.2, on Win.

Bye,
bearophile
Jun 27 '08 #3
be************@lycos.com 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 float((m2 - m1) * 1024) / N
main(20000000)

Where memory is a small module of mine that calls a little known
program that tells how much memory is used by the current Python
process. The results for that run n=20000000 are (first two numbers
are kilobytes, the third number is byte/pair):

1876
633932
32.3612672

It means to store 20_000_000 pairs it requires about 647_000_000
bytes, Python 2.5.2, on Win.
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.

def main(N):
keys = range(N)
m1 = memory()
print m1

d = {}
for i in keys:
d[i] = None

m2 = memory()
print m2
print float((m2 - m1) * 1024) / N
main(20000000)
--
Duncan Booth http://kupuguy.blogspot.com
Jun 27 '08 #4
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
Jun 27 '08 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: David | last post by:
Hi, I have an order form which has a field 'ProductID'. This form has a button on each record to open a new form linked by ProductID. This new form is a continuous form and obviously, only...
2
by: Rachel Suddeth | last post by:
Every time I read about these things my brain gets muddled and I can't keep them straight. I'm going to give my guesses, could someone confirm or deny? I think a collection doesn't have to be...
4
by: DotNetJunky | last post by:
I have built a control that runs an on-line help system. Depending on the category you selected via dropdownlist, it goes out and gets the child subcategories, and if there are any, adds a new...
6
by: Robert Schuldenfrei | last post by:
Dear NG, After being away from C# programming for a spell, I am trying my hand at what should be a simple task. I have been hitting my head against the wall this morning. I have a simple order...
1
by: Brian Conklin | last post by:
Hello Eneryone, I am having a problem. I have written a little app that will take a text "pipe" delimited file and place all of the values in to an Excel spreadsheet. It works great on any of my...
210
by: Christoph Zwerschke | last post by:
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...
6
by: bearophileHUGS | last post by:
I have found that in certain situations ordered dicts are useful. I use an Odict class written in Python by ROwen that I have improved and updated some for personal use. So I'm thinking about a...
2
by: Justin Fancy | last post by:
Hi everyone, I need some help. I'm placing text files into a created database using vb.Net. The problem is that, i need two seperate sql statements to add both files because they are in...
2
by: Zytan | last post by:
You can download them here: http://msdn2.microsoft.com/en-us/vstudio/aa718338.aspx This snippet seems wrong: Visual C# 2005 Code Snippets -filesystem -Search a Directory for Files Recursively ...
0
by: Ben Finney | last post by:
Armin Ronacher <armin.ronacher@active-4.comwrites: A welcome addition. Since we're not proposing a built-in type, could we choose a name that is more explicit, and consistent with the types...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.