public
Created

Binary search in non overlapping interval tree

  • Download Gist
gistfile1.cs
C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
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
*/
 
}
 
 
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.