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 4 2375
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
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 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
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
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 displays the
records associated with that ProductID.
Basically this is part of a Product Packing Pick System. From my
products table, each product has a set default amount of items which
|
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 ordered. But you do have to be able
to use foreach(), and it will hit every object in the collection once. But
could be in one order one time, and in another order the next, even if
nothing is done by the programmer to change anything in the...
|
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 dropdownlist to the screen
for selection. This continues until there are no children, and then it
checks for a help article list based on that last selection and displays
actual articles for display.
Adding the controls and getting everything...
|
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 entry application. The code below gets
line items from a SQL Server database and returns them to a datagrid by way
of a DataTable called lineTable. As long as I am just displaying columns in
the SQL database everything works well. I now want...
|
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 XP Pro machines. When I install the
app on a Win2K Pro machine, I get the following error message:
************** Exception Text **************
System.Runtime.InteropServices.COMException (0x80020008): Bad variable type.
at...
| |
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 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...
|
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 possible C version of Odict (maybe fit for the
collections module).
On a 32 bit Win Python 2.5 requires about:
28.2 bytes/element for set(int)
36.2 bytes/element for dict(int:None)
|
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 different loops. My output comes out to
be as Follows:
TABLE
----------------------------------------------------
|
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
I don't believe DirSearch will return any results for files in the
root directory originally passed to it. Am I right? Here's the code:
|
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 in 'collections'
already. I'd prefer one of the following:
collections.ordereddict
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |