Geek Answers Handbook

Corresponding data structure for quick search between pairs of lengths

I currently (conceptually) have:

IEnumerable<Tuple<long, long, Guid>>

given a long , I need to find the "appropriate" GUID .

long pairs should never intersect, although there may be spaces between pairs, for example:

 1, 10, 366586BD-3980-4BD6-AFEB-45C19E8FC989 11, 15, 920EA34B-246B-41B0-92AF-D03E0AAA2692 20, 30, 07F9ED50-4FC7-431F-A9E6-783B87B78D0C

For each long entry, there must be exactly 0 or 1 GUID s matches.

therefore input 7 should return 366586BD-3980-4BD6-AFEB-45C19E8FC989

input 16 should return null

Update: I have about 90K pairs

How to save this memory for quick search?

thanks

+4
source share
3 answers

As long as they are kept in order, you can simply perform a binary search based on the "start of range" against the candidate. When you find the record with the highest “range start” that is less than or equal to your target number, either you found the record with the correct GUID, or you proved that you were in (because the record with the lowest range start has a lower end of the range than your aim).

You can simplify the logic a bit by making it Dictionary<long, Guid?> And just write down the starting points by adding a record with a zero value for each space. Then you just need to find the record with the highest key that is less than or equal to your target number, and return the value.

+6
source

Try it (I'm sorry, not a solution for your IEnumerable):

 public static Guid? Search(List<Tuple<long, long, Guid>> list, long input) { Tuple<long, long, Guid> item = new Tuple<long,long,Guid> { Item1 = input }; int index = list.BinarySearch(item, Comparer.Instance); if (index >= 0) // Exact match found. return list[index].Item3; index = ~index; if (index == 0) return null; item = list[index - 1]; if ((input >= item.Item1) && (input <= item.Item2)) return item.Item3; return null; } public class Comparer : IComparer<Tuple<long, long, Guid>> { static public readonly Comparer Instance = new Comparer(); private Comparer() { } public int Compare(Tuple<long,long,Guid> x, Tuple<long,long,Guid> y) { return x.Item1.CompareTo(y.Item1); } }
+2
source

B-tree is actually very good at that. In particular, B + -tree, where each branch pointer has the beginning of your range as a key. Sheet data may contain an upper bound, so you handle spaces correctly. I'm not sure if this is the best you could find anywhere, and you would need to design it yourself, but it certainly should have very good performance.

+1
source

More articles:


All Articles