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
tuple) and a primitive value (
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, ()]], ((, ), 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, ()]], ((, ), 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.