C# Fastest search object which has nearest value given

Question

I try to find an object in list which has nearest value that given I wrote this :

float target = 100.0f;
int index = int.MaxValue;
float nearest = float.MaxValue;
for(int i = 0; i < objectList.Count; i++)
{
   if(Math.Abs(objectList[i].value - target) < nearest)
   {
       nearest = Math.Abs(objectList[i].value - target);
       index = i;
   }
}

//do something with objectList[index]

This actually works, but when the list is too large, It consumes quite much time to search.

I know there are probably way to do it, but I don't know what is it.

Answer 1

Sort and search times

This is where things get very difficult for developers without formal education. If your list of Objects is already sorted. You can use binary search for this. If the you first need to sort the list, you are not going to save time, since your approach takes Θ(n log(n)) time and sorting takes Θ(n log(n)) time and searching a sorted list takes Θ(log(n)) time, that would be slower than your approach.

Buf if your list is already sorted for example by using sortedList. Finding the closest item can be done with binary search in Θ(log(n)) time. (Which is incredible fast)

The big Problem: Binary search will find you one exact item, and not the closest. This means we need to roll our own implementation. Here's an example application that does this, the function public T findClosest is our binary search implementation.

Finding the closest value with binary search (Visual Studio C# Console Application)

You can use this to test, play around and learn more about recursive structures.

Copyright 2017 Eldar Kersebaum

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;


namespace FindingClosestObjectInList
{
    class exampleObject
    {
        public float value;
    }
    class Program
    {
        static void Main(string[] args)
        {
            //Generate objectList with some random value
            var objectList = new SortedList<float, exampleObject>();
            var rnd = new Random();
            for (int i = 0; i < 10000; i++)
            {
                var o = new exampleObject();
                o.value = (float)(rnd.NextDouble()); 
                //Values need to be Unique, that might be a problem for you.
                if (!objectList.Keys.Contains(o.value))
                {
                    objectList.Add(o.value, o);
                }
            }
            float target = .314f;
            var closestToTarget = objectList.Keys.FindClosest(target);
            Console.WriteLine(closestToTarget);
            Console.ReadKey();
        }
    }
    public static class ExtensionMethod
    {
        public static T FindClosest<T>(this IList<T> sortedCollection, T target) 
            where T : IComparable<T>, IConvertible
        {
            //Initialize borders for binary search
            int begin = 0;
            int end = sortedCollection.Count;
            T lastElement = target;

            while (end > begin)
            {
                int index = (begin + end) / 2;
                lastElement = sortedCollection[index];

                //Small change to binary search, to make sure we pick the closer one,
                //when we two values left.
                if (end - begin == 2)
                {
                    //Distanzes between the two values and the 
                    var a = sortedCollection[begin];
                    var b = sortedCollection[begin + 1];
                    var aDist = substractGeneric(a, target);
                    var bDist = substractGeneric(b, target);

                    return a.CompareTo(b) <= 0 ? a : b;
                }
                //Actual binary search
                if (lastElement.CompareTo(target) >= 0)
                    end = index;
                else
                    begin = index + 1;
            }
            //Normal ending of binary search.
            return lastElement;
        }
        //If your Type that doesn't support substraction, this will explode at RUNTIME.
        public static T substractGeneric<T>(T a, T b)
            where T : IConvertible  //Will make it more difficult to call this function with stupid Ts, but might still explode.
        {
            return (dynamic)a - (dynamic)b;
        }
    }
}

Answer 2

You can slightly speed up things by caching some values and inverting loop:

float target = 100.0f;
int index = -1;
float nearest = float.MaxValue;
int count = objectList.Count;
for(int i = count-1; i >= 0; i--)
{
   var diff = Math.Abs(objectList[i].value - target);
   if(diff < nearest)
   {
       nearest = diff;
       index = i;
   }
   if(nearest == 0)
       break;
}

Also, if your object list not changing too much you can Sort it and apply binary nearest search which will run in O(log(n)). There is plenty of optimisations can be done.

For example, you can put everything into sorted binary tree (RB-tree for example) and run your search on it. It will run considerably faster than plain look. Of course this will work only if you have a bunch of searches on this list.

Other way would be to split array into batches and process them simulteniously through Parallel.For. Then just process result of batches.

Answer 3

you can use linq expression like this:

 var  newList = objectList.Select(i => new { value = i, delta = Math.Abs(i - target) }).OrderByDescending(i=>i.delta);
    nearest = (newList.ToArray())[0].value;

Answer 4

Unless your list is sorted there's really no other way than examining each object. You could save the distance in a variable so you're not computing it twice.

float target = 100.0f;
int index = int.MaxValue;
float nearest = float.MaxValue;
for(int i = 0; i < objectList.Count; i++)
{
   float dist = Math.Abs(objectList[i].value - target);
   if(dist < nearest)
   {
       nearest = dist;
       index = i;
   }
}