Recursively traverse linked list -- help!

[O Polite]

On Tue, 2002-02-19 at 15:26, Paul Rubin wrote:

> By "middle" I didn't mean the geometric middle, but the usual case of
> wanting to insert a new node after an existing node that you already
> have a handle on. 
Yeah I got that.

> 
> Yes, the lists have to be pretty large for implementing linked lists
> in Python to beat Python's built-in vectors.  But that's only because
> interpreting Python code is so abysmally slow, which is a Python
> implementation artifact.  If and when faster Python implementations
> (i.e. with real compilers) become available, the crossover point will
> probably become a lot lower.  
Sounds wonderful. Who's working on it? When is it due?

> Even as it is, though, your measurement
> only went up to 20,000 nodes; I'd be interested in the timing at a
> million nodes.

Fair enough! Actually if I pit the LinkedList against the builtin list
in the case you're talking about (where you never have to do any work to
find the insertpoint) the LinkedList will come out as a winner already
at 5000 - 10000 inserts.


-----
program


import time, random, Numeric
class LinkedList:

    def __init__(self):
        self.start = None

    def append(self, value = None):
        new = ListElement(value)
        if self.start:
            new.next = self.start
        self.start = new


    
    def insert(self, position, value):
        new = ListElement(value)
        
        if self.start:
            i = 0
            current = self.start
            while current and position > i:
                i += 1
                current = current.next
            new.next = current.next
            current.next = new
        else:
            self.start = new

        
    def pop(self):
        result = None
        if self.start:
            result = self.start.data
            self.start = self.start.next
        return result
    
    def __str__(self):
        result = ""
        current = self.start
        while current:
            result += "%s " % (str(current))
            current = current.next
        return result

class ListElement:
    def __init__(self, value = None):
        self.data = value
        self.next = None

    def __str__(self):
        return str(self.data)


def do_many_inserts(list, count1, count2):
    length = 0
    for j in range(count1):
        t1 = time.time()
        for i in range(count2):
            list.insert(length/2, i)
            length += 1
        print length, time.time() - t1
    
def do_many_pushes(list, count1, count2):
    length = 0
    for j in range(count1):
        t1 = time.time()
        for i in range(count2):
            list.append(i)
            length += 1
        print length, time.time() - t1

    
if __name__ == '__main__':

    sets = 10
    reps = 20000

    print "inserts at start of LinkedList"
    do_many_pushes(LinkedList(), sets, reps)
    print
    
##    print "inserts at start of builtin list"
##    do_many_pushes([], 10, 20000)
##    print
    
##    print "inserts in middle of LinkedList"
##    do_many_inserts(LinkedList(), 10,200)
##    print

    print "inserts in middle of builtin list"

    do_many_inserts([], sets,reps)

------------

output
inserts at start of LinkedList
20000 0.457922101021
40000 0.546599984169
60000 0.834394097328
80000 0.565314054489
100000 1.09416890144
120000 0.563593029976
140000 1.29079794884
160000 0.564273953438
180000 0.556931972504
200000 1.63955891132

inserts in middle of builtin list
20000 0.787240982056
40000 1.71993708611
60000 4.12805104256
80000 6.63266301155
100000 9.03667891026
120000 12.0142199993
140000 26.1722120047
160000 47.1146579981
180000 56.5776759386
200000 68.3339459896