On 12/18/2010 10:41 PM, Dmitry Groshev wrote:
On Dec 19, 9:18 am, Dmitry Groshev<lambdadmi...@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
--
http://mail.python.org/mailman/listinfo/python-list
