Iterating two enumerable objects simultaneously

featured
January 09, 2017
ūüíę Originally posted here. Broken? Let me know ~

I was solving a question on Cracking the Coding Interview Edition 6 question 4.1

Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

My first attempt was a brute force approach of iterating all nodes in a graph. But then I thought about the possibility of having to deal with thousands or millions of nodes in a graph and my approach would not work.

where GetValuesUsingDfs(...)is just a graph iteration function using DFS (Depth-First Search) algorithm.

To be able to pull that off, I had to think of a way to run returned enumerators of GetValuesUsingDfs(...)¬† at the same time. Until now, I’ve been simply been using two nested for/foreach loops to accomplish such tasks. But ever since I’ve been conscious about Big O (where using two nested for/foreach would require B(N^2)), I was looking for a different way.

So the optimization technique I thought of was to iterate from both sides and if there is a common node between the two nodes, then there is a route. I can’t exactly come up with any other striking idea since I am still reading the book, but I am sure that I will be able to apply more optimizations as I read the book.

Here is the code that utilizes simultaneous iteration.

Now the function terminates as soon as a common node between the two nodes is found, which runs much faster for four of my test cases. ¬†I’ve found simultaneous iteration code from StackOverflow as usual from this question answered by¬†Eren Ers√∂nmez¬†(Answer is here; Eren also created a generic “ZipAll” function that accepts any number of IEnumerables in the answer.)

While four tests using HasRouteUsingDfs ran for 0.06 seconds, optimized version using HasRouteUsingDfs2 ran within 0.001 seconds.

Full source for above codes is available on GitHub. You’d need XUnit to run the tests.

Conclusion

It’s not possible to iterate multiple enumerators using “foreach” but can use “GetEnumerator”. I’ve been quite conscious about writing optimized code and this one just rocked since I never knew about this trick.