Databases
StackOverflow2013
Postsdbo
POOptimizing boolean logic tree evaluation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POOptimizing boolean logic tree evaluation
    primarykey
    data
    text
    <p>I've got a lot of true/false results saved as bits in <code>long[]</code> arrays. I do have a huge number of these (millions and millions of longs).</p> <p>For example, say I have only five results, I'd have:</p> <pre><code>+----- condition 5 is true | |+---- condition 4 is false || ||+--- condition 3 is true ||| |||+-- condition 2 is true |||| ||||+- condition 1 is false 10110 </code></pre> <p>I also do have a few trees representing statements like:</p> <pre><code>condition1 AND (condition2 OR (condition3 AND condition 4)) </code></pre> <p>The trees are very simple but very long. They basically look like this (it's an oversimplification below, just to show what I've got):</p> <pre><code>class Node { int operator(); List&lt;Node&gt; nodes; int conditionNumber(); } </code></pre> <p>Basically either the Node is a leaf and then has a condition number (matching one of the bit in the long[] arrays) or the Node is not a leaf and hence refers several subnodes.</p> <p>They're simple yet they allow to express complicated boolean expressions. It works great.</p> <p>So far so good, everything is working great. However I do have a problem: I need to evaluate a <em>LOT</em> of expressions, determining if they're true or false. Basically I need to do some brute-force computation for a problem for which there's no know better solution than brute-forcing.</p> <p>So I need to walk the tree and answer either <code>true</code> or <code>false</code> depending on the content of the tree and the content of the <code>long[]</code>.</p> <p>The method I need to optimize looks like this:</p> <pre><code>boolean solve( Node node, long[] trueorfalse ) { ... } </code></pre> <p>where on the first call the <code>node</code> is the root node and then, obviously, subnodes (being recursive, that <code>solve</code> method calls itself).</p> <p>Knowing that I'll only have a few trees (maybe up to a hundred or so) but millions and millions of <code>long[]</code> to check, what steps can I take to optimize this?</p> <p>The obvious recursive solution passes parameters (the (sub)tree and the long[], I could get rid of the <code>long[]</code> by not passing it as a parameter) and is quite slow with all the recursive calls etc. I need to check which operator is used (AND or OR or NOT etc.) and there's quite a lot of if/else or switch statements involved.</p> <p>I'm not looking for another algorithm (there aren't) so I'm not looking for going from O(x) to O(y) where y would be smaller than x.</p> <p>What I'm looking for is <em>"times x"</em> speedup: if I can write code performing 5x faster, then I'll have a 5x speedup and that's it and I'd be very happy with it.</p> <p>The only enhancement I see as of now --and I think it would be a huge <em>"times x"</em> speedup compared to what I have now-- would be to generate bytecode for every tree and have the logic for every tree hardcoded into a class. It should work well because I'll only ever have a hundred or so trees (but the trees aren't fixed: I cannot know in advance how the trees are going to look like, otherwise it would be trivial to simply hardcode manually every tree).</p> <p>Any idea besides generating bytecode for every tree?</p> <p>Now if I want to try the bytecode generation route, how should I go about it?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USSyntaxT3rr0r
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POOptimizing boolean logic tree evaluation
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POOptimizing boolean logic tree evaluation
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POOptimizing boolean logic tree evaluation
      1. This table or related slice is empty.
      1. VTUpMod
    1. COFor the curious, my Node implementation is not unlike this one: http://stackoverflow.com/questions/1830925
      singulars
      1. POOptimizing boolean logic tree evaluation
      1. USSyntaxT3rr0r
    2. COOne obvious thing is short-circuiting as soon as possible (e.g. FALSE AND anything is FALSE and TRUE OR anything is TRUE). I'm assuming you are doing that already?
      singulars
      1. POOptimizing boolean logic tree evaluation
      1. USJeff Foster
    3. CO@Jeff Foster: yup yup I'm doing it :) But there can be relatively big trees which are made of a lot of OR statements and only a few ANDs, so even using short-circuiting I'd still like to improve this. :)
      singulars
      1. POOptimizing boolean logic tree evaluation
      1. USSyntaxT3rr0r
 

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