Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h2>Try exploiting ternany numbering</h2> <p>For terminology I am calling "value" your set valuation function and "target" your target function which is max of sum of values over every binary partition.</p> <p>Every splitting of a binary number B into two disjoint parts, L and R, can be represented by a ternary number C, where</p> <pre><code>B = L | R (bitwise OR) L ^ R = 0 (bitwise XOR) C[i] = 0 means B[i] = 0 and L[i] = R[i] = 0 C[i] = 1 means B[i] = 1 and L[i] = 1 C[i] = 2 means B[i] = 2 and R[i] = 1 </code></pre> <p>Then "simply" enumerate numbers from 1 to 3**n in ternary: eg (n=3): 000, 001, 002, 010, 011, 012, 020, ... </p> <p>OK, actually, <em>efficiently</em> counting in ternary is not completely trivial when all you have at hand is binary. But bear with me, I will explain that bit after going over the high level algo ... </p> <p>So you count in ternary in order, and given a ternary number C, you obtain L and R - how? I'll explain that below too, trust me :)</p> <p>Given L and R you can now look up your valuation at L and R and update the target at B: target[B] = max(val[L], val[R]).</p> <p>OK that's the high-level algo. I can't prove it on such short notice but it does seem like it has very good cache locality properties. In other words value[L] and value[R] will tend to stay in a small number of cache lines at a time. Also I think the best bet for parallelizing is to split <code>i</code> into values modulo 3, or values modulo 9, etc.</p> <p><strong>efficient ternary counting in binary</strong></p> <p>How can we count in ternary efficiently? Try the following: Count in base 4, and skip some.</p> <p>In other words a ternary digit will be represented by two bits, and we will disallow the combination <code>11</code>.</p> <pre><code> repr | value 0 0 | 0 0 1 | 1 1 0 | 2 1 1 | *undefined* </code></pre> <p>Now, how do we efficiently know when to skip ? Well, the pattern of increments is easy enough to figure out: </p> <p>1 1 2 1 1 2 1 1 6 1 1 2 1 1 2 1 1 6 1 1 2 1 1 2 1 1 <strong>22</strong> 1 1 2 ... </p> <p>My suggestion would be to precaclulate a large chunk of size a power of 3 (eg 3 ** 7 = 2187) and compute the nth power of 3 on the fly once in a while [hint : it's related to cubes of n ..].</p> <p>So you start with 00.00.00. You add 1 that's 00.00.01. You add 1 that's 00.00.10. Now you have to add 2 in order to skip the 11 combination, that leaves you with 00.01.00. Etc.</p> <p><strong>how to obtain L and R from C</strong></p> <p>Now C in our quaternary representation of ternary is actually simply L and R interleaved. To get L and R back efficiently, you can check the answer to <a href="https://stackoverflow.com/questions/4909263/how-to-efficiently-de-interleave-bits-inverse-morton">this S/O question</a> or apply other bit twiddling hacks.</p> <p><strong>afterthought</strong></p> <p>All in all, I'm not sure whether we've really been using base 3 or base 4. Oh well ... </p> <p>Have fun, and good luck!</p>
    singulars
    1. This table or related slice is empty.
    1. POBottom up set generation and ordering
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USspam_eggs
    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. VTBountyClose
    1. COBy the way in case you ever need efficient modulo 3 for this you can use the fact that 2 mod 3 == -1 mod 3, so the recipe is: de-interleave your input number into even and odd bits, and subtract the bit population counts
      singulars
      1. PO
      1. USspam_eggs
 

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