6
\$\begingroup\$

Just wondering if anyone can see a way to optimize this piece of code. It is a key piece of my program and needs to run as quickly as possible. The part of the code I am unsure of is the while loop for finding the nearest key -- but any assistance with optimizing the code would be appreciated.

// TODO: Move to snippets lib or create a new collection type that supports this feature
private string _getTrait(SortedList<decimal, string> thisList, decimal thisValue)
{
    // Check to see if we need to search the list.
    if (thisList == null || thisList.Count <= 0) { return null; }
    if (thisList.Count == 1) { return thisList.Values[0]; }

    // Setup the variables needed to find the closest index
    int lower = 0;
    int upper = thisList.Count - 1;
    int index = (lower + upper) / 2;

    // Find the closest index (rounded down)
    bool searching = true;
    while (searching)
    {
        int comparisonResult = Decimal.Compare(thisValue, thisList.Keys[index]);
        if (comparisonResult == 0) { return thisList.Values[index]; }
        else if (comparisonResult < 0) { upper = index - 1; }
        else { lower = index + 1; }

        index = (lower + upper) / 2;
        if (lower > upper) { searching = false; }
    }

    // Check to see if we are under or over the max values.
    if (index >= thisList.Count - 1) { return thisList.Values[thisList.Count - 1]; }
    if (index < 0) { return thisList.Values[0]; }

    // Check to see if we should have rounded up instead
    if (thisList.Keys[index + 1] - thisValue < thisValue - (thisList.Keys[index])) { index++; }

    // Return the correct/closest string
    return thisList.Values[index];
}

I am using C#, .net4.0 -- I need to use a Generic SortedList ( http://msdn.microsoft.com/en-US/library/ms132319(v=vs.100).aspx )

\$\endgroup\$
9
  • \$\begingroup\$ unrelated: I'm curious to know what a method beginning with an underscore means in your codebase. \$\endgroup\$ Commented Nov 2, 2012 at 16:35
  • 1
    \$\begingroup\$ @crdx anything with an _ in my database designates it as private. Just makes it easy to find the stuff I want when coding. \$\endgroup\$ Commented Nov 2, 2012 at 18:15
  • 4
    \$\begingroup\$ Optimization starts with profiling. Don't guess where the bottlenecks are, know it. \$\endgroup\$ Commented Nov 2, 2012 at 20:16
  • 1
    \$\begingroup\$ There's no need for "optimization" or anything of the sort in the title. I've already added the relevant tag for it. \$\endgroup\$ Commented Dec 30, 2015 at 18:19
  • 3
    \$\begingroup\$ Hi Anthony, your title should clearly state what your code does and there's no need to state optimisation and such in the question if it's just noise. @Jamal modified your question to better fit in line with our guidelines, but you've reverted the edits. When you post code on CR we are to review the whole code (and not just specific sections) on any aspect we see fit. \$\endgroup\$ Commented Dec 30, 2015 at 19:02

2 Answers 2

Reset to default
3
\$\begingroup\$

Your loop is pretty well written. The only thing that sticks out to me is your use of a constant in the while loop and manually breaking. I also prefer to use a slightly different version of CompareTo, but it doesn't make much difference:

while ( (lower<=upper))
{
    int comparisonResult = thisValue.CompareTo( thisList.Keys [index]);
    if (comparisonResult == 0) { return thisList.Values[index]; }

    if (comparisonResult < 0)
    {
        upper = index - 1;
    }
    else
    {
        lower = index + 1;
    } 
    index = (lower + upper) / 2; 
}

You might also be looking for a solution that's just easier to read or shorter. Are you familiar with LINQ? This is one possibility for how your function might look.

    private static string GetTraitRefactor (SortedList<decimal, string> thisList, decimal thisValue)
    {
        var keys = thisList.Keys;
        var nearest = thisValue -
            keys.Where(k => k <= thisValue)
            .Min(k => thisValue - k);
        return thisList[nearest];
    }
\$\endgroup\$
5
  • \$\begingroup\$ I have the constant bool in there because I need to update the index before it breaks, without the bool I think the index would miss the last update... Maybe I am wrong on that; I will try it a bit later. \$\endgroup\$ Commented Nov 2, 2012 at 23:26
  • \$\begingroup\$ Also, I know a little bit about LINQ but still learning. That looks like something that might be worth plugging in and seeing how it runs. \$\endgroup\$ Commented Nov 2, 2012 at 23:28
  • \$\begingroup\$ Marking this as the answer as it's the only one that I got -- thanks. While I didn't user any of the code provided you made me feel more confidant about my code and gave me some alternatives to work through. Thanks! \$\endgroup\$ Commented Nov 3, 2012 at 18:17
  • 2
    \$\begingroup\$ Like I mentioned, your loop is well coded and straightforward enough that there's not too much to do with it. \$\endgroup\$ Commented Nov 5, 2012 at 16:16
  • 1
    \$\begingroup\$ Linq doesn't meet the "needs to run as quickly as possible" requirement. It performs a linear search rather than binary. The linq solution can be improved, however, by using TakeWhile instead of Where. \$\endgroup\$ Commented Dec 30, 2015 at 17:14
3
\$\begingroup\$

The classic calculation to average indices in binary search is

lower + (upper - lower) / 2

That's because (lower + upper) / 2 can overflow. Of course, in the 32-bit world, this is no longer very likely to happen.

The linq soution proposed in another answer does not meet your requirement of "needs to run as quickly as possible." Linq will do a linear search rather than a binary search.

You can get rid of the searching variable (note that you assign it at the very end of the loop body, after all):

while (lower <= upper)
//...

I think there's also no point in adding or subtracting 1. I once long ago did an analysis that showed that this doesn't improve the efficiency of the algorithm. You reduce the search range by 1 on each step, but you lose that because of the division by two. I'm not certain of this, however; it was a long time ago.

You also don't need else if the if branch returns.

Therefore:

while (lower <= upper)
{
    int comparisonResult = Decimal.Compare(thisValue, thisList.Keys[index]);

    if (comparisonResult == 0) { return thisList.Values[index]; }

    if (comparisonResult < 0) { upper = index; }
    else { lower = index; }

    index = lower + (upper - lower) / 2;
}
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.