True lists in python?

[John Nagle]

On 12/18/2010 10:41 PM, Dmitry Groshev wrote:
> On Dec 19, 9:18 am, Dmitry Groshev<lambdadmi... at gmail.com>  wrote:
>> Is there any way to use a true lists (with O(c) insertion/deletion and
>> O(n) search) in python? For example, to make things like reversing
>> part of the list with a constant time.
>
> I forgot to mention that I mean *fast* lists. It's trivial to do
> things like this with objects, but it will be sloooow.

     Try using objects with "slots".  If you have a large number
of small objects, and are doing many very simple operations on
them, the attribute lookup time will dominate.

     A nice example of when you might need real lists is for the
Traveling Salesman Problem.  The usual way to solve that is:

	1.  Link up all the nodes in a random order.
	2.  Pick two links at random, and cut the list into three lists.
	3.  Try all possible ways to arrange the three lists
		(there are 6*4*2/2 = 24 ways) and compute the
		path length for each.
         4.  Pick the shortest path.
	5.  Repeat steps 2-5 until no improvement is observed for
		a while.

The cut-and-reassemble steps are constant time for real lists, but
require expensive copying with arrays.

     If you're really worried about low-level performance issues,
CPython is probably the wrong tool for the job.

					John Nagle