From: john s. <sk...@us...> - 2011-02-12 00:57:50
|
On 12/02/2011, at 11:27 AM, Bisht, Pradeep wrote: > I need to perform range lookup on a set which has 256 entries. > There are millions of such independent 256 entries sets. > currently I'm having linked list for each such set where each > node contains begin and end of the range. Each entry in the > set is disjoint. Now I need to do a lookup of a range and > find out all the entries that overlaps with the input range and > also insert the regions which do not exist. > e.g, set = {(0, 8), (16, 24)} > lookup of (0, 32) should return entry index 0, 16 and > set = {(0, 8), (8, 8), (16, 24), (24, 8)} > I 'm thinking of evaluating JudyArray for this purpose. Is it possible > to use JudyArray to solve this problem faster than a linked list or a range tree? which > Judy variation will be most suited? And how? Thanks for the suggestions. I think Judy1 can do this easily. You can use Judy1First and Judy1Next to find all the extant entries. Since there's only 256 entries per set, it's not too hard to put all of the entries in a range in. You can find all the "holes" the same way. After you get these results you can optimise them to use ranges. If you want to use ranges directly, I think you can also do it with JudyL. This is a bit harder, but I do a similar thing with my garbage collector. You make a map: lowvalue --> high value to represent a range. Then when scanning you do this: JudyLFirst will find the NEXT key after the one you want most of the time (unless you actually hit the key). So then you use JudyLPrev to go back one key, and get the previous start/end range. Now you can check if your input start value is in that range or not: if so it's the start of the range and you have the end as the minimum of the stored end and your input end of range. Otherwise the key you previously found is the start of the range provided it is greater than your input end of range. So now you can use JudyLNext to get all the subsequent ranges until you overshoot. This is O(1). No way to do it faster. The inverse (holes between the selected ranges) is trivial. So yes, I'd say Judy is perfect for this job :) -- john skaller sk...@us... |