Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>If I understand correctly, you have floating point ranges than have to be mapped to a decision. Something like this:</p> <pre><code> x &lt;= 0.0 : Decision A 0.0 &lt; x &lt;= 0.5 : Decision B 0.5 &lt; x &lt;= 0.6 : Decision C 0.6 &lt; x : Decision D </code></pre> <p>A binary tree is a pretty good way to handle that. As long as the tree is well balanced and the input values are evenly distributed across the ranges, you can expect O(log<sub>2</sub> n) comparisons, where n is the number of possible decisions.</p> <p>If the tree is not balanced, then you could be doing far more comparisons than necessary. In the worst case: O(n). So I would look at the trees and see how deep they are. If the same tree is used again and again, then the cost spent rebalancing once may be amortized over many lookups.</p> <p>If the input values are not evenly distributed (and you know that ahead of time), then you might want to special-case the order of the comparisons so that the most common cases are detected early. You can do this by manipulating the tree or by adding special cases in the code before actually checking the tree.</p> <p>If you've exhausted algorithmic improvements and you still need to optimize, you might look into a data structure with better locality than a general binary tree. For example, you could put the partition boundaries into a contiguous array and perform a binary search on it. (And, if the array isn't too long, you might even try a linear search on the array as it may be friendlier for the cache and the branch prediction.)</p> <p>Lastly, I'd consider building a coarse index that gives us a headstart into the tree (or array). For example, use a few of the most significant bits of the input value as an index and see if that can cut off the first few layers of the tree. This may help more than you might imagine, as the skipped comparisons probably have a low chance of getting correct branch predictions.</p>
    singulars
    1. This table or related slice is empty.
    1. POCould I use a faster data structure than a tree for this?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USAdrian McCarthy
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks for the answer. My next plan is to put the tree into an array, and see what kind of improvements I can get from cache locality. I like the sounds of the indexing using the most significant bits. I'll have to think about the best way of implementing that. The problems with cramming the tree into an array are 1. It's growing and 2. The eventual size will be many many gigabytes.
      singulars
      1. PO
      1. USWill Calderwood
    2. CO@Will Calderwood: If the tree is on the order of gigabytes, then I doubt cache locality will buy you much. Making sure the tree is balanced is probably the biggest win. You might also look at doing lookups in parallel on a multi-core machine (assuming the tree is static).
      singulars
      1. PO
      1. USAdrian McCarthy
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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