StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>ATTEMPT 1:</strong></p> <p>Keep 2 binary trees, one for the start values and one for the end values. Have your nodes for both trees (or just the 'end') have a property referencing unique ranges by some id (the range's start value). </p> <p>Do a binary search on the 'start' tree to narrow the list to the ranges where the start is less than or equal to your search value. Do the same on the 'end' tree where the value is greater than or equal to search value. Find the intersection of the nodes from both trees, and those ranges contain your search value.</p> <p>You can find the intersection using a hash map/set for optimal performance.</p> <p><strong>ATTEMPT 2:</strong></p> <p>What if you kept a hash list for the intervals where the keys are the first however many bits that are shared by both the start and end values?</p> <p>So, if start is '11001101' and end is '11010010', the key is '110'. Each key would map to a list of ranges (start and end) that share the key.</p> <p>When searching for a value to see what ranges they are in, for example '00101111', you'd have to search the hash list for n different values or so, where n is the number of bits (32 in your case). In this case, you'd search for '00101111', '0010111', '001011', and so on. For each hit, you'd have to actually check that the search value is in the range.</p> <p>At first sight, it looks to me that on average, for every hit you get, half will be false positives, but that shouldn't matter if the number of hits are small, and the larger the keys are the less hits it should get.</p> <p>There is a slight problem for, say a start of '00101110' and end of '01100111' because the key would be '0' meaning there will be a significant number of 'false positives'. Better would be if there were 2 different keys, '001' and '01', although I'm not sure about the particular algorithm you'd need to code for this optimization. If the ranges are small enough and this problem can be solved or overlooked, then you can get very fast lookups as most keys will be relatively long and not match the searches.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload