473,588 Members | 2,471 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

How much slower is dict indexing vs. list indexing?

Dear Experts,

How much slower is dict indexing vs. list indexing (or indexing into a
numpy array)? I realize that looking up a value in a dict should be
constant time, but does anyone have a sense of what the overhead will
be in doing a dict lookup vs. indexing into a list? Some ad hoc tests
I've done indicate that the overhead is less than 15% (i.e., dict
lookups seem to take no more than 15% longer than indexing into a list
and there doesn't seem to be much difference in indexing into a list
vs. a numpy array).

The reason I ask is because I'm wondering how hard I should work to
compute and store an index into a list to avoid repeated hash table
lookups. From my tests, it looks like the answer is basically "don't
bother". Does anyone have information, thoughts, or comments on this?

Thanks,
-Emin

Jan 11 '07 #1
4 11597
Emin wrote:
Dear Experts,

How much slower is dict indexing vs. list indexing (or indexing into a
numpy array)? I realize that looking up a value in a dict should be
constant time, but does anyone have a sense of what the overhead will
be in doing a dict lookup vs. indexing into a list? Some ad hoc tests
I've done indicate that the overhead is less than 15% (i.e., dict
lookups seem to take no more than 15% longer than indexing into a list
and there doesn't seem to be much difference in indexing into a list
vs. a numpy array).

The reason I ask is because I'm wondering how hard I should work to
compute and store an index into a list to avoid repeated hash table
lookups. From my tests, it looks like the answer is basically "don't
bother". Does anyone have information, thoughts, or comments on this?
I think "don't bother" is a good conclusion. Tim Peters has led the
charge to (as he might put it) "optimize the snot" out of the dict
implementation. Anything you do in Python to speed up access is likely
to add more to execution time than you might save by not exercising the
C-based dict lookup code.

What technique were you thinking of to look up the cached index values
in Python, just as a matter of curiosity? Storing them in a dict? It
would be hard to think of a faster way ... ;-)

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Blog of Note: http://holdenweb.blogspot.com

Jan 11 '07 #2
On Jan 11, 5:53 pm, Steve Holden <s...@holdenweb .comwrote:
>
What technique were you thinking of to look up the cached index values
in Python, just as a matter of curiosity? Storing them in a dict? It
would be hard to think of a faster way ... ;-)
I didn't have anything fancy in mind. I was just wondering whether it
makes sense to replace a block of code like

data = {'a' : 1, 'b' :2, 'c' : 3}
for i in someLargeList:
for name in ['a','b','c']:
result.append(d ata[name])

with somthing like

data = {'a' : 1, 'b' :2, 'c' : 3}
dataValues = [data[k] for k in ['a','b','c']
for i in someLargeList:
for index in [0,1,2]:
result.append(d ataValues[index])

It sounds like it's probably not worth the effort in general, but might
be for extremely ultra-critical parts of code.

Thanks

Jan 12 '07 #3

EminIt sounds like it's probably not worth the effort in general, but
Eminmight be for extremely ultra-critical parts of code.

Even in extremely ultra-critical parts of code I doubt the loss of
readability would be worth it. If there are situations where you can really
gain by switching from a natural indexing scheme to lists, there are
probably other places in your code where you will gain just as much benefit
without the corresponding loss of readability. Indexing lists only appears
to be about twice as fast as indexing dicts:

% timeit.py -s "data = {'a' : 1, 'b' :2, 'c' : 3}" "for k in 'abc': x = data[k]"
100000 loops, best of 3: 4.61 usec per loop
% timeit.py -s "data = [1, 2, 3]" "for k in [0, 1, 2]: x = data[k]"
100000 loops, best of 3: 2.97 usec per loop

If you're worried about regaining a couple microseconds per index you
probably shouldn't be using Python.

Skip
Jan 12 '07 #4
"Emin" <em**********@g mail.comwrote in message
news:11******** *************@s 34g2000cwa.goog legroups.com...
On Jan 11, 5:53 pm, Steve Holden <s...@holdenweb .comwrote:
>>
What technique were you thinking of to look up the cached index values
in Python, just as a matter of curiosity? Storing them in a dict? It
would be hard to think of a faster way ... ;-)

I didn't have anything fancy in mind. I was just wondering whether it
makes sense to replace a block of code like

data = {'a' : 1, 'b' :2, 'c' : 3}
for i in someLargeList:
for name in ['a','b','c']:
result.append(d ata[name])

with somthing like

data = {'a' : 1, 'b' :2, 'c' : 3}
dataValues = [data[k] for k in ['a','b','c']
for i in someLargeList:
for index in [0,1,2]:
result.append(d ataValues[index])
[Your as-posted code doesn't run, you are missing a trailing ']' in your
list comprehension. ]

So what you want is this?
1. Get the values from the data dict in order of their key, ['a','b','c']
(which is not the same as getting the data.values() list, which is in
unpredictable order)
2. For every element in some larger list, append each of the elements in
order from step 1 to some other result list.

First of all, realize that:
for index in [0,1,2]:
result.append(d ataValues[index])
is the same as
result.extend(d ataValues)
assuming that dataValues has exactly 3 elements in it.

Second, why are you iterating over someLargeList? You are doing nothing
with i, and neither the data dict nor the dataValues list changes as you
iterate.

This will do the job more quickly, I should think:

data = {'a' : 1, 'b' :2, 'c' : 3}
dataValues = [data[k] for k in ['a','b','c']]
result.extend( dataValues * len(someLargeLi st) )

-- Paul
Jan 12 '07 #5

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

Similar topics

21
4305
by: Hilde Roth | last post by:
This may have been asked before but I can't find it. If I have a rectangular list of lists, say, l = ,,], is there a handy syntax for retrieving the ith item of every sublist? I know about for i in l] but I was hoping for something more like l. Hilde
1
1116
by: anony | last post by:
Hi, I'm populating a drop down list asp.net control with the following code: cmdSqlCommand.CommandText = "SELECT SUBMITTEDBYID, FIRSTNAME + ' ' + LASTNAME AS FIRSTLAST FROM xxx ORDER BY FIRSTNAME" dtrSqlDataReader = cmdSqlCommand.ExecuteReader() dropSubmittedBy.DataSource = dtrSqlDataReader
7
1135
by: hollowspook | last post by:
Hi, there a = range(100) if I want to use No 7, 11, 56,90 in a, then the only way I do is , a, a, a]. Is there any other way? Thanks in advance.
0
840
by: John Machin | last post by:
Guilherme Polo wrote: He didn't need to. He explicitly said "list" (which permits duplicates) and didn't mention a self-imposed uniqueness constraint.
3
8022
by: rewonka | last post by:
Hello, I'm trying to find the fastest way to convert an sql result into a dict or list. What i mean, for example: my sql result: contact_id, field_id, field_name, value sql_result=, , ,
0
7929
marktang
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...
0
7862
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
8228
Oralloy
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...
1
7987
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,...
0
8223
tracyyun
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...
1
5729
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5398
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
1
2372
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
1
1459
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

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.