preallocate list

[Jim]

Hi all

Is this the best way to preallocate a list of integers?
listName = range(0,length)

What about non integers?

I've just claimed in the newsgroup above that pre-allocating helps but I
might be getting confused with matlab ;)

If I have a file with a floating point number on each line, what is the
best way of reading them into a list (or other ordered structure)?

I was iterating with readline and appending to a list but it is taking ages.

Jim

[rbt]

Re: preallocate list

Jim wrote:
[color=blue]
> If I have a file with a floating point number on each line, what is the
> best way of reading them into a list (or other ordered structure)?
>
> I was iterating with readline and appending to a list but it is taking
> ages.[/color]

Perhaps you should use readlines (notice the s) instead of readline.

[Bill Mill]

Re: preallocate list

On 4/13/05, Jim <jbo@cannedham. ee.ed.ac.uk> wrote:[color=blue]
> Hi all
>
> Is this the best way to preallocate a list of integers?
> listName = range(0,length)
> [/color]

the 0 is unnecessary; range(length) does the same thing.
[color=blue]
> What about non integers?
> [/color]

arr = [myobject() for i in range(length)]
[color=blue]
> I've just claimed in the newsgroup above that pre-allocating helps but I
> might be getting confused with matlab ;)
>
> If I have a file with a floating point number on each line, what is the
> best way of reading them into a list (or other ordered structure)?
>
> I was iterating with readline and appending to a list but it is taking ages.
> [/color]

I would profile your app to see that it's your append which is taking
ages, but to preallocate a list of strings would look like:

["This is an average length string" for i in range(approx_le ngth)]

My guess is that it won't help to preallocate, but time it and let us
know. A test to back my guess:

import timeit, math

def test1():
lst = [0 for i in range(100000)]
for i in xrange(100000):
lst[i] = math.sin(i) * i

def test2():
lst = []
for i in xrange(100000):
lst.append(math .sin(i) * i)

t1 = timeit.Timer('t est1()', 'from __main__ import test1')
t2 = timeit.Timer('t est2()', 'from __main__ import test2')
print "time1: %f" % t1.timeit(100)
print "time2: %f" % t2.timeit(100)

09:09 AM ~$ python test.py
time1: 12.435000
time2: 12.385000

Peace
Bill Mill
bill.mill at gmail.com

[Jim]

Re: preallocate list

rbt wrote:[color=blue]
> Jim wrote:
>[color=green]
>> If I have a file with a floating point number on each line, what is
>> the best way of reading them into a list (or other ordered structure)?
>>
>> I was iterating with readline and appending to a list but it is taking
>> ages.[/color]
>
>
> Perhaps you should use readlines (notice the s) instead of readline.[/color]

I don't know if I thought of that, but I'm tokenizing each line before
adding to a list of lists.

for line in f:
factor = []
tokens = line.split()
for i in tokens:
factor.append(f loat(i))
factors.append( factor)

Is this nasty?

Jim

[Bill Mill]

Re: preallocate list

Just a correction:

<snip>[color=blue]
> I would profile your app to see that it's your append which is taking
> ages, but to preallocate a list of strings would look like:
>
> ["This is an average length string" for i in range(approx_le ngth)]
>
> My guess is that it won't help to preallocate, but time it and let us
> know. A test to back my guess:
>
> import timeit, math
>
> def test1():
> lst = [0 for i in range(100000)]
> for i in xrange(100000):
> lst[i] = math.sin(i) * i
>
> def test2():
> lst = []
> for i in xrange(100000):
> lst.append(math .sin(i) * i)
>
> t1 = timeit.Timer('t est1()', 'from __main__ import test1')
> t2 = timeit.Timer('t est2()', 'from __main__ import test2')
> print "time1: %f" % t1.timeit(100)
> print "time2: %f" % t2.timeit(100)
> [/color]

The results change slightly when I actually insert an integer, instead
of a float, with lst[i] = i and lst.append(i):

09:14 AM ~$ python test.py
time1: 3.352000
time2: 3.672000

The preallocated list is slightly faster in most of my tests, but I
still don't think it'll bring a large performance benefit with it
unless you're making a truly huge list.

I need to wake up before pressing "send".

Peace
Bill Mill

[Jim]

Re: preallocate list

Thanks for the suggestions. I guess I must ensure that this is my bottle
neck.
<code>
def readFactorsInto List(self,filen ame,numberLoads ):
factors = []
f = open(self.based ir + filename,'r')
line = f.readline()
tokens = line.split()
columns = len(tokens)
if int(columns) == number:
for line in f:
factor = []
tokens = line.split()
for i in tokens:
factor.append(f loat(i))
factors.append( loadFactor)
else:
for line in f:
tokens = line.split()
factors.append([float(tokens[0])] * number)
return factors
</code>

OK. I've just tried with 4 lines and the code works. With 11000 lines it
uses all CPU for at least 30 secs. There must be a better way.

Jim

[Mike C. Fletcher]

Re: preallocate list

Jim wrote:
[color=blue]
> Thanks for the suggestions. I guess I must ensure that this is my
> bottle neck.[/color]

....
[color=blue]
> for line in f:
> factor = []
> tokens = line.split()
> for i in tokens:
> factor.append(f loat(i))
> factors.append( loadFactor)
>[/color]
....

You might try:

factors = [ [float(item) for item in line.split()] for line in f ]

avoiding the extra statements for appending to the lists. Also might try:

factors = [ map(float, line.split()) for line in f ]

though it uses the out-of-favour functional form for the mapping.

Good luck,
Mike

_______________ _______________ _______________ ___
Mike C. Fletcher
Designer, VR Plumber, Coder

http://www.vrplumber.com

http://blog.vrplumber.com

[peufeu@free.fr]

Re: preallocate list


what about :

factors = [map(float, line.split()) for line in file]

should be a hell of a lot faster and nicer.
[color=blue]
> for line in f:
> factor = []
> tokens = line.split()
> for i in tokens:
> factor.append(f loat(i))
> factors.append( factor)
>
> Is this nasty?
>
> Jim[/color]

[Steven Bethard]

Re: preallocate list

Jim wrote:[color=blue]
> Thanks for the suggestions. I guess I must ensure that this is my bottle
> neck.
> <code>
> def readFactorsInto List(self,filen ame,numberLoads ):
> factors = []
> f = open(self.based ir + filename,'r')
> line = f.readline()
> tokens = line.split()
> columns = len(tokens)
> if int(columns) == number:
> for line in f:
> factor = []
> tokens = line.split()
> for i in tokens:
> factor.append(f loat(i))
> factors.append( loadFactor)
> else:
> for line in f:
> tokens = line.split()
> factors.append([float(tokens[0])] * number)
> return factors
> </code>
>
> OK. I've just tried with 4 lines and the code works. With 11000 lines it
> uses all CPU for at least 30 secs. There must be a better way.[/color]

Was your test on *just* this function? Or were you doing something with
the list produced by this function as well?

STeVe

[Jim]

Re: preallocate list

Steven Bethard wrote:[color=blue]
> Jim wrote:
>[color=green]
>> Thanks for the suggestions. I guess I must ensure that this is my
>> bottle neck.
>> <code>
>> def readFactorsInto List(self,filen ame,numberLoads ):
>> factors = []
>> f = open(self.based ir + filename,'r')
>> line = f.readline()
>> tokens = line.split()
>> columns = len(tokens)
>> if int(columns) == number:
>> for line in f:
>> factor = []
>> tokens = line.split()
>> for i in tokens:
>> factor.append(f loat(i))
>> factors.append( loadFactor)
>> else:
>> for line in f:
>> tokens = line.split()
>> factors.append([float(tokens[0])] * number)
>> return factors
>> </code>
>>
>> OK. I've just tried with 4 lines and the code works. With 11000 lines
>> it uses all CPU for at least 30 secs. There must be a better way.[/color]
>
>
> Was your test on *just* this function? Or were you doing something with
> the list produced by this function as well?
>[/color]

Just this. I had a breakpoint on the return.

I'm going to try peufeu's line of code and I'll report back.

Jim

[Jim]

Re: preallocate list

peufeu@free.fr wrote:[color=blue]
>
> what about :
>
> factors = [map(float, line.split()) for line in file]
>
> should be a hell of a lot faster and nicer.
>[color=green]
>> for line in f:
>> factor = []
>> tokens = line.split()
>> for i in tokens:
>> factor.append(f loat(i))
>> factors.append( factor)
>>
>> Is this nasty?
>>
>> Jim[/color]
>
>[/color]
Oh the relief :)

Of course, line.split() is already a list.

Couple of seconds for the 10000 line file.

Thanks.

What I really want is a Numeric array but I don't think Numeric supports
importing files.

Jim

[Jim]

Re: preallocate list

Steven Bethard wrote:[color=blue]
> Jim wrote:[/color]
...[color=blue][color=green]
>> OK. I've just tried with 4 lines and the code works. With 11000 lines
>> it uses all CPU for at least 30 secs. There must be a better way.[/color]
>
>
> Was your test on *just* this function? Or were you doing something with
> the list produced by this function as well?
>
> STeVe[/color]

Well it's fast enough now. Thanks for having a look.

Jim

[Steven Bethard]

Re: preallocate list

Jim wrote:[color=blue]
> What I really want is a Numeric array but I don't think Numeric supports
> importing files.[/color]

Hmmm... Maybe the scipy package?

I think scipy.io.read_a rray might help, but I've never used it.

STeVe

[F. Petitjean]

Re: preallocate list

Le Wed, 13 Apr 2005 16:46:53 +0100, Jim a écrit :[color=blue]
>
> What I really want is a Numeric array but I don't think Numeric supports
> importing files.[/color]
Numeric arrays can be serialized from/to files through pickles :
import Numeric as N
help(N.load)
help(N.dump)
(and it is space efficient)[color=blue]
>
> Jim[/color]

[beliavsky@aol.com]

Re: preallocate list

Jim wrote:[color=blue]
> Hi all
>
> Is this the best way to preallocate a list of integers?
> listName = range(0,length)[/color]

For serious numerical work you should use Numeric or Numarray, as
others suggested. When I do allocate lists the initial values 0:n-1 are
rarely what I want, so I use

ivec = n*[None]

so that if I use a list element before intializing it, for example

ivec[0] += 1

I get an error message

File "xxnone.py" , line 2, in ?
ivec[0] += 1
TypeError: unsupported operand type(s) for +=: 'NoneType' and 'int'

This is in the same spirit as Python's (welcome) termination of a
program when one tries to use an uninitalized scalar variable.