[NEWBIE] Priority Queue in Python

[David Boeren]

I'm trying to implement something like a priority queue in Python, but
it's quite slow compared to a similar implementation in Java.  I tried
running the List speed test I found on this web page
	http://www.twistedmatrix.com/~glyph/rant/python-vs-java.html

and the Java version was about 7.7 * faster, although the page author
reported only 2.4 * faster.

Anyway, I've coded the Python version in several different ways and
measured them all.  Here's the code:

def benchmark(func, times=1):
    t0=clock()
    for i in xrange(times): func()
    t1=clock()
    print "Time =", (t1-t0)

def shuffle(list):
    "Randomly shuffles a list"
    if type(list) is IntType:
        list=range(list)
    length=len(list)
    for i in xrange(length):
        pos=randrange(i, length)
        (list[i], list[pos]) = (list[pos], list[i])
    return list

def insert_priority(list, tuple, key_index):
    i=0
    key = tuple[key_index]
    try:
        while key < list[i][key_index]: i=i+1
        list.insert(i, tuple)
    except IndexError:
        list.append(tuple)

def insert_priority2(list, tuple, key_index):
    key = tuple[key_index]
    for i in list:
        if i[key_index] < key:
            list.insert(list.index(i), tuple)
            break
    else:
        list.append(tuple)

def insert_priority3(list, tuple, key_index):
    key = tuple[key_index]
    n=0
    for i in list:
        if i[key_index] < key:
            list.insert(n, tuple)
            break
        n=n+1
    else:
        list.append(tuple)

def insert_priority4(list, item):
    i=0
    try:
        while item < list[i]: i=i+1
        list.insert(i, item)
    except IndexError:
        list.append(item)

def test0():
    "benchmark(test0, 100) =  2.4259 test"
    l=[]
    for i in shuffle(1000):
        l.append((0,i))

def test1():
    "benchmark(test1, 100) = 26.6688 sec"
    l=[]
    for i in shuffle(1000):
        insert_priority(l, (0, i), 1)

def test2():
    "benchmark(test2, 100) = 31.7182 sec"
    l=[]
    for i in shuffle(1000):
        insert_priority2(l, (0, i), 1)

def test3():
    "benchmark(test3, 100) = 30.8639 sec"
    l=[]
    for i in shuffle(1000):
        insert_priority3(l, (0, i), 1)

def test4():
    "benchmark(test4, 100) = 21.6703 sec"
    l=[]
    for i in shuffle(1000):
        insert_priority4(l, i)


As you can see, I've coded the insert_priority() several different
ways.  1-3 each take a tuple or list, and sort based on the indicated
item in the sequence.  In case the extra tuple creation and lookup was
costing too much, I also coded a 4th version to which I just pass an
int to sort on.  Turns out it *IS* significant, but it's not the
biggest cost.  I also timed the creation of my random list to be
inserted (test0), and it doesn't take that much time either.

Out of curiosity, I coded a similar function in Java to test the
speed.  The code is rather ugly, I was just trying to get it working
quickly (still took a lot longer to write than Python, and this is
some of my first Python code!)  The java version (which is
functionally equivalent to test4 in that it uses ints and not tuples
or other more advanced structures) runs in about 1.87 seconds,
which makes it about 11.6 times slower than the Python version.

I'm using Python 2.0 and Java 1.3, both on an Athlon Thunderbird 900
running under Win98SE.

I'm wondering if I'm just missing something here, or should there
really be this big of a difference between the speed of Java and
Python?  I expected maybe around a 4X difference, but 12X is starting
to get uncomfortable.  Am I implementing my algorithm badly?  I freely
admit to being a total beginner in Python, so that may be the case.  I
do like the way Python takes less time and fewer lines to write, and
the code is more general.  I've got a 16-line version of
insert_priority that I'm working on that handles keys by either direct
use, sequence-position, attribute-name, or a compare-function!

Also, one specific question.  Maybe it's because I don't know the
idioms yet, but I keep wanting to have access to a loop counter
variable in my for loops.  For example:

for i in list:
    print i, "is the", list.index(i), "element"

The index() call takes too long, I wish there was like a hidden
variable so I could say it like this.  Is there?

for i in list:
    print i, "is the", __loopindex__, "element"

Or is there just a better way to do this that I don't know?

Well, thanks for putting up with the ravings of a mad Python newbie.
I love the language so far, and I'd like to make it my main language
for coding at home, I just have some doubts about the speed that are
making me a little hesitant so far.  Oh, and if anyone knows of a good
tutorial for wxWindows, let me know, ok?  :)

import java.util.*;

class tools {
    Vector v;
    int range[];

    void shuffle(int n) {
        Random randy=new Random();
        int pos, tmp;
        v=new Vector(n);

        range = new int[n];
        for (int i=0; i < n; i++) range[i]=i;
        for (int i=0; i < (n-1); i++) {
            pos=i+randy.nextInt(n-i);
            tmp=range[i];
            range[i]=range[pos];
            range[pos]=tmp;
        }
    }

    void insert_priority(int n) {
        for (int pos=0; pos < v.size(); pos++) {
            if (n > ((Integer)v.elementAt(pos)).intValue()) {
                v.add(pos, new Integer(n));
                return;
            }
        }
        v.add(new Integer(n));
    }

    void test(int n) {
        shuffle(n);
        for (int i=0; i < n; i++) insert_priority(range[i]);
    }

    public static void main(String[] args) {
        tools t=new tools();

        long t0=System.currentTimeMillis();
        for (int i=0; i<100; i++) t.test(1000);
        long t1=System.currentTimeMillis();
        System.out.println("\nTime = " + (t1-t0));
    }
}