Skip to content

Instantly share code, notes, and snippets.

@mennankara
Created August 8, 2012 18:23
Show Gist options
  • Save mennankara/3297288 to your computer and use it in GitHub Desktop.
Save mennankara/3297288 to your computer and use it in GitHub Desktop.
Binary search in non overlapping interval tree
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace GeneralTests
{
internal class Program
{
public class RangeGroup
{
public uint RangeGroupId { get; set; }
public uint Low { get; set; }
public uint High { get; set; }
// More properties related with the range here
}
public class RangeGroupFinder
{
private static readonly List<RangeGroup> RangeGroups = new List<RangeGroup>();
static RangeGroupFinder()
{
uint prev = 1000000000 - 100;
uint id = 0;
for (uint i = 1000000000; i < uint.MaxValue; i += (uint)new Random().Next(500, 600))
{
RangeGroups.Add(new RangeGroup { RangeGroupId = id, Low = prev + 1, High = i });
prev = i;
id++;
if (id == 5000000)
{
break;
}
}
}
public static void Initialize()
{
}
public static RangeGroup Find(uint number)
{
return RangeGroups.FirstOrDefault(rg => number >= rg.Low && number <= rg.High);
}
public static RangeGroup Find2(uint number)
{
int position = RangeGroups.Count / 2;
int stepSize = position / 2;
while (true)
{
if (stepSize == 0)
{
// Couldn't find it.
return null;
}
if (RangeGroups[position].High < number)
{
// Search down.
position -= stepSize;
}
else if (RangeGroups[position].Low > number)
{
// Search up.
position += stepSize;
}
else
{
// Found it!
return RangeGroups[position];
}
stepSize /= 2;
}
}
}
private static bool CheckResult(RangeGroup rg, uint checkValue)
{
return checkValue >= rg.Low && checkValue <= rg.High;
}
private static void Main(string[] args)
{
var stopwatch = new Stopwatch();
stopwatch.Start();
RangeGroupFinder.Initialize();
Console.WriteLine("Created the sample data in {0} ms.", stopwatch.ElapsedMilliseconds);
double elapsedTicksLinq = 0;
for (var i = 0; i < 16; i++)
{
var searchValue = (uint)(i * (uint.MaxValue / 16));
Console.WriteLine("Searching for {0}", searchValue);
stopwatch.Restart();
var rg = RangeGroupFinder.Find(searchValue);
elapsedTicksLinq += stopwatch.ElapsedTicks;
if (rg != null && !CheckResult(rg, searchValue))
{
throw new Exception(string.Format("Didn't check {0} in {1}-{2} ", i, rg.Low, rg.High));
}
}
Console.WriteLine("Linq: {0} ticks.", elapsedTicksLinq);
double elapsedTicksBinarySearch = 0;
for (var i = 0; i < 16; i++)
{
var searchValue = (uint)(i * (uint.MaxValue / 16));
Console.WriteLine("Searching for {0}", searchValue);
stopwatch.Restart();
var rg = RangeGroupFinder.Find2(searchValue);
elapsedTicksBinarySearch += stopwatch.ElapsedTicks;
if (rg != null && !CheckResult(rg, searchValue))
{
throw new Exception(string.Format("Didn't check {0} in {1}-{2} ", i, rg.Low, rg.High));
}
}
Console.WriteLine("BinarySearch: {0} ticks.", elapsedTicksBinarySearch);
Console.WriteLine("BinarySearch is {0} times faster than Linq", elapsedTicksLinq / elapsedTicksBinarySearch);
/* Results:
* Created the sample data in 26255 ms.
* Searching for 0
* Searching for 268435455
* Searching for 536870910
* Searching for 805306365
* Searching for 1073741820
* Searching for 1342177275
* Searching for 1610612730
* Searching for 1879048185
* Searching for 2147483640
* Searching for 2415919095
* Searching for 2684354550
* Searching for 2952790005
* Searching for 3221225460
* Searching for 3489660915
* Searching for 3758096370
* Searching for 4026531825
* Linq: 8230662 ticks.
* Searching for 0
* Searching for 268435455
* Searching for 536870910
* Searching for 805306365
* Searching for 1073741820
* Searching for 1342177275
* Searching for 1610612730
* Searching for 1879048185
* Searching for 2147483640
* Searching for 2415919095
* Searching for 2684354550
* Searching for 2952790005
* Searching for 3221225460
* Searching for 3489660915
* Searching for 3758096370
* Searching for 4026531825
* BinarySearch: 1214 ticks.
* BinarySearch is 6779.78747940692 times faster than Linq
*/
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment