Computer Science question (python list is slow with my cruddy algorithm )
Mr. Neutron
nicktsocanos at charter.net
Fri Aug 23 04:39:28 EDT 2002
Hi,
I am working on a program that uses a list of lists
MyList = [ [0] * 32767 for i in range(32767) ]
My first realization is that it is incredibly slow just to create this
list. Then I have a generator function that actually builds the data in
the list with a tuple. There a few statements going on to build
values for the tuple.
I have a function that runs through a loop:
for j in range(0,32766):
for i in range(0,32766):
# calculate items
MyList[j][i] = ( tuple of values )
It is taking a very long time to generate this entire list on P4 2.0ghz
machine.. I rewrote the algorithm in C, and it runs much faster.
Now my real question is not that I should rewrite this in C, but are
there are any algorithm tricks to creating a better algorithm to
creating the list? Right now I think is is O(N^2). Is there any way
in Python to do this sort of thing getting a faster algorithm?
I would much rather understand an algorithmic trick to creating
more efficient code than just rewriting the same algorithm in
C and getting machine speed execution. I will have to look through
my books to see if there any other ways to do this.
Now I have thought of tricks to speed it up. I create N worker
threads, and each thread generates a slice of the list. This
is a novel idea but it seems a bit much just to create a simple
matrix.
The problem is though just to generate the statement
MyList = [ [0] * 32767 for i in range(32767) ]
Takes forever (well, it seems like forever).
I have thought of other ways of defining the world using a much smaller
list. Elements not in the list are assumed to be empty. Then I just have
a list of the elements that are of interest. However even a list that
1024 by 1024 is quite slow to work with.
What I'd really like to do is figure out a way to represnt a
2-dimensional world as a linear list.Then I could build a linear
algorithm that generates the world and not have to use this
list comprehensions to make lists of lists.
Thanks
More information about the Python-list
mailing list