Locate Primitive Value in Nested Sequence Type - Iterative version is slower than equivalent recursive function

Question

I'm looking for advice on how to improve the performance and/or style of these two search functions. This is just for fun and for practice: they are already fast enough for any application I would be using them in, and they don't have to meet any specific performance criteria, but I'm interested to see how they could be made better.

The two code examples both work in all cases I've tested, but I believe there may be unnecessary overhead (especially in the second version) slowing them down. The first function is faster than the second: in my most recent benchmarking test (I included the timing procedure I used for this test in the code examples), the first took ~0.147 seconds while the second took ~0.185 seconds to perform the same 1000 searches.

---

Description of code:

These are two functions which I have written and intend to be equivalent solutions to the same problem using two different approaches. The first is a typical recursive depth-first search algorithm, and the second is the same function refactored to eliminate recursion (it is 100% iterative). Both functions take a sequence type (either list or tuple) and a primitive value (int, string etc.) as arguments, and look for the primitive value inside the sequence. If the value is found, the function returns the path taken to get to it (as a list of indices) and the depth of the item (i.e. the number of inner nested sequences it is inside). If the value does not occur anywhere in the sequence, the function returns an empty list and a depth of -1.

---

Background on this question:

Recently on Stack Overflow I asked a question about a recursive depth-first search function which was failing to return the correct path after locating the item. After receiving a great answer on that site, I now have working code for the original version of the function. Someone also asked if I'd considered using a non-recursive approach, and another user suggested taking the fixed version here for improvements, so I'm doing both and posing the question as an explicit comparison of the two different implementations.

When I rewrote the function to be entirely iterative, I was expecting it to run faster than the recursive version, as I'd heard that recursive calls are slow (in general) compared to loops. After running a benchmarking test on both functions side by side, I was surprised to see that the iterative implementation was actually significantly slower. Although I'm familiar with the concept, I'm not very experienced with actually implementing breadth-first algorithms compared to depth-first ones, so the decreased performance is probably because I'm doing something inefficiently or performing unnecessary work somewhere in the function. My best guess is that it's the part that 'retraces its steps' from the outermost sequence at depth 0 back to depth (n - 1) after exiting a nested sequence at depth n. (This is the nested for loop inside the while loop: I've made a note of it inside the code comments as well.) While I'm aware that the 'retracing' procedure could be avoided by storing references to each nested sequence as they're encountered, this doesn't seem like a worthwhile tradeoff due to the added space complexity (although this should be negligible since they would just be references, not deep copies) and decrease in readability from having yet another temporary variable at the top of the function. If I'm wrong about this I'd be glad to be corrected though.

---

Here is the recursive function:

# ITERATIVE/RECURSIVE SEQUENCE TRAVERSER

# Searches for 'item' in sequence (list or tuple) S, and returns a tuple
# containing the indices (in order of increasing depth) at which the item
# can be found, plus the depth in S at which 'item' was found.

# If the item is *not* found, returns a tuple containing an empty list and -1

# For benchmarking
import time

def traverse(S, item, indices=[]):
    # If the sequence is empty, return the 'item not found' result
    if not S:
        return ([], -1)
    
    else:
        # For each element in the sequence (breadth-first)
        for i in range(len(S)):
            # Success condition base case:  found the item!
            if S[i] == item:
                # Credit to Freddy Mcloughlan from Stack Overflow for
                # pointing out that since the depth is always 1 less than
                # the length of the final list of indices, it doesn't have
                # to be passed as another parameter to 'traverse'
                return (indices + [i], len(indices))
            
            # Recursive step (depth-first):  enter nested sequence
            # and repeat procedure from beginning
            elif type(S[i]) in (list, tuple):
                testCall = traverse(S[i], item, indices + [i])
                # Nick's solution from Stack Overflow:  only return the
                # recursive call if it is a success result, to avoid
                # 'covering up' successes with false negatives
                if testCall != ([], -1):
                    return testCall
            
        # Fail condition base case:  searched the entire length
        # and depth of the sequence and didn't find the item, so
        # return the 'item not found' result
        else:
            return ([], -1)


L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7]), 7.5], [[8, ()]], (([9], ), 10)]

startTime = time.time()

for i in range(1000):
    for j in range(21):
        traverse(L, j/2)

finishedAt = time.time()
print("Original recursive version took " + str(finishedAt - startTime) + " seconds")

And here is the iterative equivalent:

# Iterative-only version of the same function from the question

# For benchmarking
import time

def traverse(S, item):
    indices = []
    sequence = S
    depth = 0

    # By definition, if the sequence is empty, you won't find any items in it.
    # Return the 'item not found' result.
    if not S:
        return ([], -1)

    else:
        # You have to start somewhere :D
        indices.append(0)

        while depth > -1:
            # Go back up one level once the end of a nested sequence is reached.
            while indices[depth] == len(sequence):
                depth -= 1
                
                # If the depth ever gets below 0, that means that we've scanned
                # the entire length of the outermost sequence and not found the
                # item.  Return the 'failed to find item' result.
                if depth == -1:
                    return ([], -1)

                # Remove the entry corresponding to index in the innermost
                # nested sequence we just exited
                indices.pop()

                # INEFFICIENT ???
                # Reset 'sequence' using the outermost sequence S and the indices
                # computed so far, to get back to the sequence which contained
                # the previous one
                sequence = S
                for i in range(len(indices) - 1):
                    sequence = sequence[indices[i]]

                indices[depth] += 1
                # And return to the top of the outer 'while' loop to re-check
                # whether to go down another level
                continue
                
            # Success:  found the item at depth 'depth', in sequence 'sequence',
            # at index 'indices[depth]` inside that sequence.  Return 'indices'
            # and 'depth'.
            if sequence[indices[depth]] == item:
                return (indices, depth)
            
            # Recursion replacement:  enter the nested subsequence and increase the depth
            # as long as the nested subsequence is not empty.  If it is empty, treat it
            # as if it were a non-sequence type.
            elif (type(sequence[indices[depth]]) in (list, tuple)) and (sequence[indices[depth]]):
                sequence = sequence[indices[depth]]
                depth += 1
                indices.append(0)
                        
            # The item being compared is not a sequence type and isn't equal to 'item', so increment
            # the index without increasing the depth
            else:
                indices[depth] += 1
                
        # If all of S has been searched and item was not found,
        # return the 'failed to find item' result
        return ([], -1)
                            

L = [0, 1, 2, [3, (4, 5, [6, 6.25, 6.5, 6.75, 7]), 7.5], [[8, ()]], (([9], ), 10)]

startTime = time.time()

for i in range(1000):
    for j in range(21):
        traverse(L, j/2)

finishedAt = time.time()
print("Iterative version took " + str(finishedAt - startTime) + " seconds")

I would greatly appreciate any suggestions for improvements to either or both implementations (regarding performance, readability, or any other 'best practices' metric), but especially would be interested in a comparison of where the second version is getting slowed down and falling behind the first.

Answer 1

The benchmark is flawed because the iterative version is doing too much work. Iterative BFS/DFS has an elegant simplicity once your get your mind wrapped around its core idea. Your implementation, by contrast, is fairly complex and, at least for me, unintuitive. The complexity comes from managing, mutating, and resetting the state variables, especially sequence and indices, as you go from level to level. Those repeated mutations slow things down.

Classic BFS/DFS. A typical implementation, by contrast, avoids the need to worry about resetting the status variables. Instead, it uses a queue/stack to hold independent copies of the state. The queue/stack functions as a TODO list. What goes into the TODO? The arguments that you would have passed recursively (there's a reason they call it a "call stack"). You must take care not to mutate those variables. Only the queue/stack is mutated.

def traverse_iterative(S, item):
    if S:
        # Initialize the TODO list.
        stack = [(S, [])]
        while stack:
            # Get the next data to check.
            xs, indices = stack.pop()
            for i, x in enumerate(xs):
                if x == item:
                    # Success.
                    return (indices + [i], len(indices))
                elif isinstance(x, (list, tuple)):
                    # Add it to the TODO list.
                    stack.append((x, indices + [i]))
    return ([], -1)

Benchmark. That function runs generally the same speed as your recursive function on my computer (0.152 vs 0.151, using your scenario). One could fuss around with details on both functions to squeeze out some more performance (for example, the edits shown below speed up the recursive function a small bit), but I'm mostly bored by that sort of thing.

Code review stuff. Your recursive implementation is reasonable and easy to understand. Just a few suggestions. (1) Define a failed search constant rather than hardcoding it in three places. (2) Iterate directly over Python collections, rather than iterating over the collection's indexes (and if you also need indexes, use enumerate). (3) Use isinstance() to check the type. (4) Very few Python programmers use for-else, because it's not intuitive (does "else" mean that the loop was broken or not, and are there any other tricky details I need to remember?), so just do the normal thing and put the failed return statement after the loop. And even if you find the for-else structure really handy in some circumstances (I never have), the current case isn't one them, because you never break the loop.

def traverse_recursive(S, item, indices=[]):
    FAIL = ([], -1)
    if S:
        for i, x in enumerate(S):
            if x == item:
                return (indices + [i], len(indices))
            elif isinstance(x, (list, tuple)):
                result = traverse_recursive(x, item, indices + [i])
                if result != FAIL:
                    return result
    return FAIL