473,245 Members | 1,725 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,245 software developers and data experts.

Optimisation Hints (dict processing and strings)

OPQ
Hi all,
I'd happy to have you share some thougts about ultimate optimisations
on those 2 topics:

(1)- adding one caractere at the end of a string (may be long)
(2)- in a dict mapping a key to a list of int, remove every entrie
where the list of int have of length < 2
So far, my attempts are
for (1):
longone=longone + char # where len(char)== 1

I known that string concatenation is time consuming, but a small test
on timeit seems to show that packing and creating an array for those 2
elements is equally time consuming
for (2):
for k in hash.keys()[:]: # Note : Their may be a lot of keys here
if len(hash[k])<2:
del hash[k]
Here again, I think the hash.keys duplication can be time *and* memory
consuming. But still better than (I suppose - no time it yet)
hash=dict([(k,v) for (k,v) in hash if len(v)>1])
I know that I can experiment further with timeit, but still would like
to hear from your experience.

Thanks !

--OPQ
Jul 18 '05 #1
8 1397
OPQ wrote:
I'd happy to have you share some thougts about ultimate optimisations
on those 2 topics:

(1)- adding one caractere at the end of a string (may be long)
longone=longone + char # where len(char)== 1


I known that string concatenation is time consuming, but a small test
on timeit seems to show that packing and creating an array for those 2
elements is equally time consuming


You've misunderstood the comments about this area.
String concatenation is *not* "time consuming".
*Repeated* concatenations *will become very time
consuming*, along an exponential curve. That's
what the discussions about O(n^2) are referring
to. A single string concatenation is definitely
going to be faster than any amount of converting
to other data structures and such.

Basically, to concatenate two strings, Python
simply adds their sizes together and allocates
a new memory area of sufficient size, then copies
the bytes from each string to the new area. Not
much overhead there, for a single concatenation.

The problem comes when you try to scale this.
At some point, the overhead of allocating and
deallocating all the intermediate strings becomes
much larger than other approaches would take.
For example, by building a list with references
to all the strings, then using join(), you save
on the intermediate steps. Join performs the
length-summation and memory allocation steps
only once, and copies each individual string into
the final area only once. Much faster, provided
the overhead of growing a list as you append()
string references is small enough. And it is,
since growing a list is not O(n^2) in Python
(though I don't recall exactly what it is).

The key with this stuff is to realize that neither
approach is inherently faster: it depends on how
much concatenation you are doing. It could be
that concatenating up to four strings is faster
than using the append/join technique, or it could
be that it's faster up to twenty strings.

When you're not talking hundreds of operations,
and when you're not talking about actual *measured*
performance problems (in other words, when we would
call it "premature optimization"), focus on the
readability of the code and on keeping it simple
and clean. Worry about the correctness of the code,
and leave optimization worries till later. (But
understand this "big O" stuff well enough to
be able to avoid the real problem areas, when
possible.)

-Peter
Jul 18 '05 #2
OPQ wrote:
for (1):
longone=longone + char # where len(char)== 1

I known that string concatenation is time consuming, but a small test
on timeit seems to show that packing and creating an array for those 2
elements is equally time consuming


- use cStringIO instead
- or append all chars to a list and do "".join (listvar)

for (2):
for k in hash.keys()[:]: # Note : Their may be a lot of keys here
if len(hash[k])<2:
del hash[k]
Here again, I think the hash.keys duplication can be time *and* memory
consuming. But still better than (I suppose - no time it yet)
hash=dict([(k,v) for (k,v) in hash if len(v)>1])


- Try if it isn't faster to iterate using items instead of iterating
over keys
- use the dict.iter* methods to prevent building a list in memory. You
shouldn't use these values directly to delete the entry as this could
break the iterator:

for key in [k for (k, v) in hash.iteritems () if len (v) < 2]:
del hash (key)

This of course builds a list of keys to delete, which could also be large.

- also: hash.keys()[:] is not necessary, hash.keys () is already a copy

Daniel
Jul 18 '05 #3

OPQ wrote:
(2)- in a dict mapping a key to a list of int, remove every entrie
where the list of int have of length < 2
So far, my attempts are
for (2):
for k in hash.keys()[:]: # Note : Their may be a lot of keys here
if len(hash[k])<2:
del hash[k]
Here again, I think the hash.keys duplication can be time *and* memory consuming. But still better than (I suppose - no time it yet)
hash=dict([(k,v) for (k,v) in hash if len(v)>1])


Firstly, don't call it "hash"; you are shadowing a built-in function --
as well as giving clues to your background :-)

Secondly, you are *triplicating* the keys. Mapping.keys() returns a
list. You can safely iterate over that to change the contents of the
mapping. Read the docs: "a.keys() a copy of a's list of keys".
Mapping.keys()[:] gives you a copy of the copy.

Cheers,
John

Jul 18 '05 #4
OPQ
#For the record, I'm not on premature optimisation anymore.
#The code is working. I just want to save hours of computing, without
relying to much on C extensions.
#Nevertheless, thansk for tips, clarifications and explanations.
>longone=longone + char # where len(char)== 1
I known that string concatenation is time consuming, but a small test
on timeit seems to show that packing and creating an array for those 2
elements is equally time consuming


- use cStringIO instead
- or append all chars to a list and do "".join (listvar)

Yes, but as Peter said using a list won't be useful for a single
operation.
And I have to compute the string at each step of the loop. I think
listvar won't be useful.
But I'm going to try cStringIO.

for (2):
for k in hash.keys()[:]: # Note : Their may be a lot of keys here
if len(hash[k])<2:
del hash[k]
- Try if it isn't faster to iterate using items instead of iterating
over keys


items are huge lists of numbers. keys are simple small strings. And
even if it is faster, how can I find the key back, in order to delete
it ?
for v in hashh.items():
if len(v)<2:
del ???????
- use the dict.iter* methods to prevent building a list in memory. You
shouldn't use these values directly to delete the entry as this could
break the iterator:

for key in [k for (k, v) in hash.iteritems () if len (v) < 2]:
del hash (key)

I gonna try, but think that would be overkill: a whole list has to be
computed !
Maybe whith genexps ...... for key in (k for (k,v) in hash.iteritems()
if len(v)<2)

This of course builds a list of keys to delete, which could also be large.

Yes. Which tell me to use genexps.
- also: hash.keys()[:] is not necessary, hash.keys () is already a copy


Yes I got that one, but too late !

Thanks !
Jul 18 '05 #5
I posted a question about string concatination just last week. There is
plenty of discussion on it, if you just search the group.

Jul 18 '05 #6
On 29 Mar 2005 23:41:15 -0800, po***@hotmail.com (OPQ) wrote:
[...]
> for k in hash.keys()[:]: # Note : Their may be a lot of keys here
> if len(hash[k])<2:
> del hash[k]
- Try if it isn't faster to iterate using items instead of iterating
over keys


items are huge lists of numbers. keys are simple small strings. And
even if it is faster, how can I find the key back, in order to delete
it ?

items() returns a list of (k,v) tuples, so you can unpack them
into the for assignment target, e.g.,

for k,v in hashh.items():
if len(v)<2:
del hassh[k]
for v in hashh.items():
if len(v)<2:
del ???????


but to avoid a big temporary items() list, perhaps (untested)

for k in [k for k,v in hashh.iteritems() if len(v)<2]:
del hassh[k]

UIAM that should build a temporary safe list
only of the keys selected for deletion.

Regards,
Bengt Richter
Jul 18 '05 #7
OPQ wrote:
- Try if it isn't faster to iterate using items instead of iterating
over keys

items are huge lists of numbers. keys are simple small strings. And
even if it is faster, how can I find the key back, in order to delete
it ?
for v in hashh.items():
if len(v)<2:
del ???????


To elaborate on the memory requirements of .keys () vs. items ():

..keys () creates a new list of n objects. The objects are additional
references to the existing keys.

..items () creates also a new list of n objects. These objects are tuples
of references, one to the key and one to the value. Only references
are used so it doesn't matter how large the value actually is. Whether
the tuples are created for the items () call or already exist depends on
the implementation of the dictionary. Trying to infer this by using
sys.getrefcount got me inconclusive results.
I gonna try, but think that would be overkill: a whole list has to be
computed !
Maybe whith genexps ...... for key in (k for (k,v) in hash.iteritems()
if len(v)<2)


Using only iterators has problems:

for k,v in hash.iteritems ():
if len (v) < 2:
del hash [k]

You are changing hash while you iterate over it, this very often breaks
the iterator.

If you are memory bound, maybe a dabase like SQLite is really the way to
go. Or you could write the keys to a remporary file in the loop and then
write a second loop that reads the keys and deletes them from hash.

Daniel
Jul 18 '05 #8
OPQ wrote:
for (2):
for k in hash.keys()[:]: # Note : Their may be a lot of keys here
if len(hash[k])<2:
del hash[k]

- use the dict.iter* methods to prevent building a list in memory. You
shouldn't use these values directly to delete the entry as this could
break the iterator:

for key in [k for (k, v) in hash.iteritems () if len (v) < 2]:
del hash (key)

I gonna try, but think that would be overkill: a whole list has to be
computed !


Yes, but it is smaller than the list returned by hash.keys(), so it should be a win over what you
were doing originally. Plus it avoids a lookup (hash[k]) which may improve the speed also.

BTW I have long assumed that iterating key, value pairs of a dict using iteritems() is faster than
iterating with keys() followed by a lookup, since the former method should be able to avoid actually
hashing the key and looking it up.

I finally wrote a test, and my assumption seems to be correct; using iteritems() is about 1/3 faster
for simple keys.

Here is a simple test:

##

d = dict((i, i) for i in range(10000))

def withItems(d):
for k,v in d.iteritems():
pass

def withKeys(d):
for k in d:
d[k]

from timeit import Timer

for fn in [withItems, withKeys]:
name = fn.__name__
timer = Timer('%s(d)' % name, 'from __main__ import d, %s' % name)
print name, timer.timeit(1000)

##

I get
withItems 0.980311184801
withKeys 1.37672944466

Kent
Jul 18 '05 #9

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

Similar topics

9
by: Robin Cull | last post by:
Imagine I have a dict looking something like this: myDict = {"key 1": , "key 2": , "key 3": , "key 4": } That is, a set of keys which have a variable length list of associated values after...
4
by: Kim Petersen | last post by:
I've worked on this table object a bit too long - and seem to have stared too long at the code. Can someone see where it goes wrong in the insertrow function? Also optimization hints and...
11
by: cjl | last post by:
Hey all: I want to convert strings (ex. '3', '32') to strings with left padded zeroes (ex. '003', '032'), so I tried this: string1 = '32' string2 = "%03s" % (string1) print string2 >32
11
by: Ville Vainio | last post by:
I need a dict (well, it would be optimal anyway) class that stores the keys as strings without coercing the case to upper or lower, but still provides fast lookup (i.e. uses hash table). >> d...
17
by: EC-AKD | last post by:
Hi All, I am new to the concept of optimising codes in C. I was wondering if C level inlining of code is any way comparable to macros. I believe that inlining is equivalent to writing macros....
6
by: Kamilche | last post by:
I have a code snippet here that prints a dict in an arbitrary order. (Certain keys first, with rest appearing in sorted order). I didn't want to subclass dict, that's error-prone, and overkill for...
15
by: Cruella DeVille | last post by:
I'm trying to implement a bookmark-url program, which accepts user input and puts the strings in a dictionary. Somehow I'm not able to iterate myDictionary of type Dict{} When I write print...
6
by: kaens | last post by:
Hey everyone, this may be a stupid question, but I noticed the following and as I'm pretty new to using xml and python, I was wondering if I could get an explanation. Let's say I write a simple...
6
by: bearophileHUGS | last post by:
When I use dictionaries I find the dict.get() method very handy, and I'd like to use it often, but I think it's quite slow. This is a small benchmark: from random import randrange from timeit...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
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: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
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...

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.