Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 )

share|improve this question
    
unrelated: I'm curious to know what a method beginning with an underscore means in your codebase. –  crdx Nov 2 '12 at 16:35
    
This code runs extremely fast, even for big lists. I strongly doubt that this is your bottleneck. –  codesparkle Nov 2 '12 at 17:27
1  
@crdx anything with an _ in my database designates it as private. Just makes it easy to find the stuff I want when coding. –  Anthony Nichols Nov 2 '12 at 18:15
    
@codesparkle -- thanks for the insight, I still consider myself a novice when it comes to programming. The code looks messy to me and I felt there had to be better way to do it... Maybe I am lacking confidence rather than optimization. –  Anthony Nichols Nov 2 '12 at 18:18
3  
Optimization starts with profiling. Don't guess where the bottlenecks are, know it. –  ANeves Nov 2 '12 at 20:16
add comment

1 Answer

up vote 1 down vote accepted

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];
    }
share|improve this answer
    
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. –  Anthony Nichols Nov 2 '12 at 23:26
    
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. –  Anthony Nichols Nov 2 '12 at 23:28
    
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! –  Anthony Nichols Nov 3 '12 at 18:17
1  
Like I mentioned, your loop is well coded and straightforward enough that there's not too much to do with it. –  Reacher Gilt Nov 5 '12 at 16:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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