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