Computer Science question (python list is slow with my cruddy algorithm )

Mr. Neutron nicktsocanos at charter.net
Fri Aug 23 10:39:28 CEST 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