Databases
StackOverflow2013
Postsdbo
POData structure for large ranges of consecutive integers?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POData structure for large ranges of consecutive integers?
    text
    copied!<p>Suppose you have a large range of consecutive integers in memory, each of which belongs to exactly one category. Two operations must be O(log n): moving a range from one category to another, and finding the category counts for a given range.</p> <p>I'm pretty sure the second operation is solved trivially given a correct implementation for the first operation.</p> <p>Each integer begins in a category, so I started with a set of balanced BSTs. Moving a subtree from one BST to another (eg, moving a range to a different category) has a runtime equivalent to merging two BSTs, which is O(n1 * n2)[<a href="https://stackoverflow.com/questions/1008513/how-to-merge-two-bsts-efficiently">1</a>].</p> <p>This is too slow (in python, and C is not an option), and I couldn't figure out a way to take advantage of my data's inherent structure to create an efficient BST merge operation.</p> <p>I'm now looking at AVL, red-black, and interval trees, binary heaps, and treaps. Comparing their properties is overwhelming. Which structure should I use?</p> <p><strong>Edit (problem clarification)</strong>: I am flexible on how I store these values and create my data structures. I am inflexible about how I receive my input, which comes from another application, and looks like the following: <code>CATEGORY(cat3, I, J)</code>. My current solution creates a tree with a node for each integer in the range. This is too slow for the size of my dataset, so I'm happy to re-architect if given a better method.</p> <p>Any given request can move any possible range of integers into any category. In other words, ranges are overlapping in the sense of <code>CATEGORY(cat1, 1, 10)</code> followed by <code>CATEGORY(cat3, 5, 15)</code>, but non-overlapping in the sense that every integer will be in exactly one category at any given time.</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