1

Topic: How more quickly to search for a suitable range in the list?

All greetings! There is a table with records of such structure (numerical ranges [FirstNumber. EndNumber] are not intersected): internal class Range {internal ulong FirstNumber; internal ulong EndNumber; internal string Data; | Records some hundreds thousand It is necessary to tire out it in storage (in any structure) and quickly on number to find record with a range which includes this number That advise in sense of the search algorithm? It is necessary fast, search does not go... Thanks

2

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> There is a table with records of such structure (numerical ranges [FirstNumber. EndNumber] are not intersected): D> Records some hundreds thousand D> It is necessary to tire out it in storage (in any structure) and quickly on number to find record with a range which includes this number D> That advise in sense of the search algorithm? It is necessary fast, search does not go... To Sort records by ranges and to search a method of half division.

3

Re: How more quickly to search for a suitable range in the list?

On  - the depthbalanced binary tree and slightly adapted search algorithm (that considered upper bound). Search will be for O (log n).

4

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> All greetings! D> there is a table with records of such structure (numerical ranges [FirstNumber. EndNumber] are not intersected): D> D> internal class Range D> {D> internal ulong FirstNumber; D> internal ulong EndNumber; D> internal string Data; D> | D> D> Records some hundreds thousand D> It is necessary to tire out it in storage (in any structure) and quickly on number to find record with a range which includes this number D> That advise in sense of the search algorithm? It is necessary fast, search does not go... D> Thanks Look interval tree

5

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> All greetings! D> there is a table with records of such structure (numerical ranges [FirstNumber. EndNumber] are not intersected): D> D> internal class Range D> {D> internal ulong FirstNumber; D> internal ulong EndNumber; D> internal string Data; D> | D> D> Records some hundreds thousand D> It is necessary to tire out it in storage (in any structure) and quickly on number to find record with a range which includes this number D> That advise in sense of the search algorithm? It is necessary fast, search does not go... D> at Thanks Look CompositeRange in library CodeJam. In the same place  GetIntersection should produce . I did not use, performance on such  can also not to give. But algorithms  comparing and . There are present.

6

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> All greetings! D> that advise in sense of the search algorithm? It is necessary fast, search does not go... D> Thanks In CodeJam really are a class for operation with ranges, CompositeRange, but it is left unfinished in respect of productivity, hands do not reach. But in CodeJam. Experimental there is that is necessary for you - IntervalTree. It is possible not to drag library, and it is simple  the code under your data structure. Everything that is required - that the input data has been sorted by the left boundary, then on the right. In respect of performance basically norms, but it is possible and to accelerate if to be confused, : //10k ranges Method | Mean | StdDev | Scaled | Scaled-StdDev | GcAllocations |---------------- |---------- neutral---------- neutral------- neutral-------------- neutral-------------- neutral Intersect | 38.232 us | 5.2904 us | 1.00 | 0.00 | 208 B | IntersectTree | 3.665 us | 0.2707 us | 0.097 | 0.0162 | 176 B | IntersectCostin | 9.058 us | 0.9607 us | 0.24 | 0.044 | 5.36 KB |//100k ranges Method | Mean | StdDev | Scaled | Scaled-StdDev | GcAllocations |---------------- |------------- neutral----------- neutral------- neutral-------------- neutral-------------- neutral Intersect | 3,740.194 us | 87.1295 us | 1.00 | 0.00 | 208 B | IntersectTree | 8.625 us | 0.3551 us | 0.0023 | 0.000109 | 176 B | IntersectCostin | 20.239 us | 1.7635 us | 0.0054 | 0.00048 | 11.05 KB | us - microseconds Intersect - CompositeRange <T>, there O (n) with all that it implies. IntersectTree - that IntervalTree IntersectCostin - the typical code from the Internet aka "I am not able in performance", it is taken from here: https://code.google.com/archive/p/intervaltree/ Sm on . 5-10kb on each call - well

7

Re: How more quickly to search for a suitable range in the list?

Hello, Sinix, you wrote: S> But in CodeJam. Experimental there is that is necessary for you - IntervalTree. And that it in experimental?... <<RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>

8

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> All greetings! D> there is a table with records of such structure (numerical ranges [FirstNumber. EndNumber] are not intersected): D> D> internal class Range D> {D> internal ulong FirstNumber; D> internal ulong EndNumber; D> internal string Data; D> | D> D> Records some hundreds thousand D> It is necessary to tire out it in storage (in any structure) and quickly on number to find record with a range which includes this number D> That advise in sense of the search algorithm? It is necessary fast, search does not go... D> Thanks https://msdn.microsoft.com/ru-ru/library/a1s5syxa (v=vs.110).aspx public int BinarySearch (int index, int count, T item, IComparer <T> comparer) In  compare only FirstNumber. Can write him? The method returns or an index of an element at which some == FirstNumber, or an index of the nearest element. If the second that  the nearest element of the list. P.S. It if updates are not present between searches. If updates are, then already wrote - search for B-tree implementation about which Sinix above wrote. P.P.S. On mine at first it is necessary to you would like to read Wikipedia about binary search and binary trees.

9

Re: How more quickly to search for a suitable range in the list?

Hello, AndrewVK, you wrote: S>> But in CodeJam. Experimental there is that is necessary for you - IntervalTree. AVK> And that it in experimental? , hands do not reach. During a week reaches, I hope)

10

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> All greetings! D> there is a table with records of such structure (numerical ranges [FirstNumber. EndNumber] are not intersected): D> D> internal class Range D> {D> internal ulong FirstNumber; D> internal ulong EndNumber; D> internal string Data; D> | D> D> Records some hundreds thousand D> It is necessary to tire out it in storage (in any structure) and quickly on number to find record with a range which includes this number D> That advise in sense of the search algorithm? It is necessary fast, search does not go... D> Thanks Judging by indirect signs, we search for bins. As a whole becomes as: the array fights on some tens  at which the minimum/maximum range is set. Search in two stages - at first is found necessary , then we search in it direct search.

11

Re: How more quickly to search for a suitable range in the list?

Hello, Codechanger, you wrote: a C> Judging by indirect signs, we search for bins. As a whole becomes as: the array fights on some tens  at which the minimum/maximum range is set. Search in two stages - at first is found necessary , then we search in it direct search. Well that is interval tree hand to hand. To advise similar  the decision it is possible only knowing allocation of ranges in the real task.... <<RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>

12

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> numerical ranges [FirstNumber. EndNumber] are not intersected enough SortedSet with  on EndNumber. For search GetViewBetween + FirstOrDefault.

13

Re: How more quickly to search for a suitable range in the list?

Hello, Sinix, you wrote: S> In CodeJam really there is a class for operation with ranges, CompositeRange, but it is left unfinished in respect of productivity, hands do not reach. S> but in CodeJam. Experimental there is that is necessary for you - IntervalTree. http://blogs.solidq.com/en/sqlserver/st … erval-tree Here such piece, likely, it makes sense and for a collection in operative storage to turn.

14

Re: How more quickly to search for a suitable range in the list?

Hello, AndrewVK, you wrote: AVK> Well that is interval tree hand to hand. To advise similar  the decision it is possible only knowing allocation of ranges in the real task. If it of what I think there allocation is more or less known.

15

Re: How more quickly to search for a suitable range in the list?

Hello, Codechanger, you wrote: a C> If it of what I think there allocation is more or less known. No, it not bins is ip-addresses in ulong allocation it is not known absolutely as ranges come outside

16

Re: How more quickly to search for a suitable range in the list?

Hello, artelk, you wrote: A> it is Enough SortedSet with  on EndNumber. A> For search GetViewBetween + FirstOrDefault. From here it is possible more in detail? Argument of search is the number, result - one record in which range it is number enters

17

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> it is ip-addresses in ulong And why in ulong? , two variants: 1) If ranges intersected and to change them is impossible - interval tree 2) If not intersected (intersected it is possible to normalize to such type, in algorithms considered algorithm, Kodt advised quite suitable variant with small finishings) - the amount of variants extends, a banal tabular variant with About (1) but  storages, binary search and hash tables.... <<RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>

18

Re: How more quickly to search for a suitable range in the list?

Hello, AndrewVK, you wrote: AVK> And why in ulong? Well while in ulong there still about IP6 it is necessary to think in the long term AVK> Vobshchem, two variants: AVK> 2) If not intersected (intersected it is possible to normalize to such type, in algorithms considered algorithm, Kodt advised quite suitable variant with small finishings) - the amount of variants extends, a banal tabular variant with About (1) but  storages, binary search and hash tables. Not intersected I tend binary search and  found storage yes, devours

19

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: AVK>> And why in ulong? D> well while in ulong D> there still about IP6 it is necessary to think in the long term On ipv6 ulong all the same does not suffice, there twice it is more.... <<RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>

20

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> Hello, artelk, you wrote: A>> it is Enough SortedSet with  on EndNumber. A>> For search GetViewBetween + FirstOrDefault. D> from here it is possible more in detail? D> argument of search is the number, result - one record in which range it is number enters the Example: Sorted on EndNumber (and simultaneously on FirstNumber, since not intersected) intervals: [1. 5], [7. 13], [14. 25], [30. 42] we Search for an interval which is including a point 20. intervals. GetViewBetween (new Range {EndNumber=20}, intervals. Max) == [14. 25], [30. 42] we Look only the first [14. 25]. Approaches, we return. We search for an interval which is including a point 6. intervals. GetViewBetween (new Range {EndNumber=6}, intervals. Max) == [7. 13], [14. 25], [30. 42] we Look only the first [7. 13]. Does not approach, since FirstNumber it has more 6. I.e. var intervals = new SortedSet <Range> (Comparer <Range>.Cre Create ((x, y) = x. EndNumber. CompareTo (y. EndNumber))); Range Find (int n) {if (intervals. Count == 0) return null; var range = intervals. GetViewBetween (new Range {EndNumber=n}, intervals. Max).FirstOrDefault (); return range! = null && range. FirstNumber <= n? range = null;} Wrote in the browser, recheck the test.

21

Re: How more quickly to search for a suitable range in the list?

Hello, mDmitriy, you wrote: D> [FirstNumber. EndNumber] [off-topic] Under symmetry laws: First-Last Begin-End Start-Stop etc.

22

Re: How more quickly to search for a suitable range in the list?

Hello, AndrewVK, you wrote: AVK> On ipv6 ulong all the same does not suffice, there twice it is more. Well BigInteger m. Will be