2
\$\begingroup\$

How would you refactor this method to make it more performant?

If you have refactored the code you need to prove the performance gain in numbers to get the solution :)

public static T Find<T>(
    this IEnumerable<T> source,
    Func<T, IEnumerable<T>> childrenSelector,
    Predicate<T> condition)
{
    T t = default(T);
    foreach (T item in source)
    {
        if (condition(item))
        {
            return item;
        }

        t = childrenSelector(item).Find<T>(childrenSelector, condition);

        if (!Equals(t, default(T)))
        {
            return t;
        }
    }
    return t;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ How can one "prove the performance gain in numbers" if you do not give us a concrete example? Also: stackoverflow.com/tags/performance/info Good question states performance goals that need to be achieved as well as other restrictions. Trying to optimize something without measuring is not "performance" question or work, but most likely personal entertainment - expect question without goals/measurements to be treated as such. \$\endgroup\$ – ANeves Feb 29 '12 at 14:09
  • \$\begingroup\$ use the method with a closed generic type and search a 100000 object tree for a certain item`s property value. Do the same with your optimization on the method then rerun the test. Compare both results and show them here. Thats about the numbers. :) \$\endgroup\$ – Pascal Feb 29 '12 at 22:39
4
\$\begingroup\$

Do you really have a performance issue?

Optimizing a recursive function is usually done by performing tail call optimization, but this is not possible here since you have multiple branchs to explore at each function call.

I would thus not try to make the code faster, but the algorithm faster. If searching in a tree actually slows your code, that means you need to change the way it works so that you know which branch to explore at each function call and having O(log n) complexity instead of O(n). There are tons of trees which have nice properties likes this: B-trees, red-black trees, splay trees and so on. You can also consider using a hash table.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Not a real performance issue. But when I want to replace concrete methods to use a generic version my colleagues will ask about the speed ;P Thanks for the B-Tree search tip. I think the road ends here. \$\endgroup\$ – Pascal Feb 29 '12 at 22:48
  • \$\begingroup\$ I'd like to mention that a binary search tree is easy to implement, and you should go that way first if you have an issue with your tree. Other data structures avoid certain pitfalls of binary search trees, but they're not that common. \$\endgroup\$ – Quentin Pradet Mar 1 '12 at 8:01
  • \$\begingroup\$ Is a B-Tree the same as a msdn.microsoft.com/en-us/library/ms379573(v=vs.80).aspx (Binary Search tree) ? \$\endgroup\$ – Pascal Mar 1 '12 at 9:40
  • \$\begingroup\$ Nope, a a B-Tree is more complicated and is used in databses such as a CouchDB. \$\endgroup\$ – Quentin Pradet Mar 1 '12 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.