split an iteration

[Robin Becker]

This function from texlib in oedipus.sf.net is a real cpu hog and I determined 
to see if it could be optimized.

def add_active_node(self, active_nodes, node):
    """Add a node to the active node list.
    The node is added so that the list of active nodes is always
    sorted by line number, and so that the set of (position, line,
    fitness_class) tuples has no repeated values.
    """
    index = 0
    # Find the first index at which the active node's line number
    # is equal to or greater than the line for 'node'.  This gives
    # us the insertion point.
    while (index < len(active_nodes) and
           active_nodes[index].line < node.line):
        index = index + 1
    insert_index = index
    # Check if there's a node with the same line number and
    # position and fitness.  This lets us ensure that the list of
    # active nodes always has unique (line, position, fitness)
    # values.
    while (index < len(active_nodes) and
           active_nodes[index].line == node.line):
        if (active_nodes[index].fitness_class == node.fitness_class and
            active_nodes[index].position == node.position):
            # A match, so just return without adding the node
            return
        index = index + 1
    active_nodes.insert(insert_index, node)
I determined that len was being called a large number of times so did a first 
rewrite as (minus comments)

def add_active_node(self, active_nodes, node):
    index = 0
    nan = len(active_nodes)
    node_line = node.line
    node_fitness_class = node.fitness_class
    node_position = node.position
    while index < nan and active_nodes[index].line<node_line:
        index += 1
    insert_index = index
    while index<nan and active_nodes[index].line==node_line:
        if (active_nodes[index].fitness_class==node_fitness_class and
            active_nodes[index].position==node_position):
            return
        index += 1
    active_nodes.insert(insert_index, node)
which gives a good speedup even so I decided to eliminate the index += 1 in the 
first while loop which results in

def add_active_node(self, active_nodes, node):
    nan = len(active_nodes)
    node_line = node.line
    node_fitness_class = node.fitness_class
    node_position = node.position
    insert_index = nan
    for index, a in enumerate(active_nodes):
        if a.line>=node_line:
            insert_index = index
            break
    index = insert_index
    while index<nan and active_nodes[index].line==node_line:
        if (active_nodes[index].fitness_class==node_fitness_class and
            active_nodes[index].position==node_position):
            return
        index += 1
    active_nodes.insert(insert_index, node)
and this change also results in a significant speedup and is I believe is still 
equivalent. I'm not sure exactly why this is faster than the while loop, but it is.

However, it seems harder to get the same speedup for the last while loop; that 
loop is probably not such a problem so it's not terribly important.

Is there a fast way to get enumerate to operate over a slice of an iterable?
--
Robin Becker
--
http://mail.python.org/mailman/listinfo/python-list