java how to determine logical expression minimum values to evauate

169 views Asked by At

I have an expression (an example)

(value1<15 AND value2>25) OR ((value3>0 and vaue4<5) OR (value5<6 and value7>8))

The issue is value1-7 are calls to external services, which are expensive. And we need to reduce cost, so we need to make a minimum number of calls to evaluate this expression. For example if we have

(value1<15 AND value2>25)

evaluated to true, we don't need to evaluate right part, so we don't need to make useless calls to external services. How to determine in java (or may be just in math) when we need to stop, and further evaluations will not make any effect?

UPDATE

I have 5 workers that works on 5 different servers.

first worker:

    accept(expression)
    value1=calculateValue1()
    setValueToExpression(expression, 0, value1)
    enough=expression.checkIsItEnough()
    if(!enough){
      determineNextWorker(expression)
      sendToNExtWorker()
    }
    else return expression.evaluate()

The second worker

    accept(expression)
    value2=calculateValue2()
    setValueToExpression(expression, 1, value2)
    enough=expression.checkIsItEnough()
    if(!enough){
     determineNextWorker(expression)
     sendToNextWorker()
    }
    else return expression.evaluate()

.....................

As I said in comments, I clearly understand that if we can write

 evaluator.evaluate("(value1<5 and value2>6) or (value3>5 and value4>7)")

it evaluates it as all of us know, but I don't have this ability due to many reasons. I also can't make it function calls value1()<15... It's happening synchronously, one by one but even on different servers, kinda offline evaluation. Hope it's clear

3

There are 3 answers

0
Patricia Shanahan On BEST ANSWER

Consider normal short-circuit intermediate code for:

(value1<15 AND value2>25) OR ((value3>0 and value4<5) OR (value5<6 and value7>8))

if value1<15 goto value2_test else goto value3_test
value2_test:
if value2>25 goto success else goto value3_test
value3_test:
if value3>0 goto value4_test else goto value5_test
value4_test:
if value4<5 goto success else goto value5_test
value5_test:
if value5<6 goto value7_test else goto fail
value7_test:
if value7>8 goto success else goto fail

You could simplify things substantially by having a tree representation of your expression, and passing around subexpressions represented by trees rather than the whole expression.

For example, the first worker would have two subexpressions: value2>25 and (value3>0 and value4<5) OR (value5<6 and value7>8). Select the first one if the test succeeds, the second one if it fails.

The value2>25 worker would have two subexpressions: "success" and (value3>0 and value4<5) OR (value5<6 and value7>8)

I am not aware of any library to do the conversions. If it exists, it would be in the domain of compiler construction.

I would try very hard to change this to something where one worker could organize the job, and simply call on other workers to evaluate one relational condition.

======================================================================== More detail, because this seems to be the sort of answer the OP is looking for:

Terminology:

  • "term" -> A comparison or Boolean variable, such as value2>25
  • "product" -> The AND of some Boolean expressions
  • "sum" -> The OR of some Boolean expressions.

Consider only sum-of-products expressions, such as (value1<15 AND value2>25) OR ((value3>0 and value4<5) OR (value5<6 and value7>8)). This is not a very significant limitation. Many optimizations and simplifications used in digital logic design depend on converting arbitrary logical expressions to sum-of-products.

At each step, the worker for the leading term of an expression is called. Depending on the expression and the outcome of its test, it can declare success, declare failure, or calculate a new expression that must be passed to the worker for its leading term.

   if this worker's condition is true
     if more terms in current product
       remove the leading term from the current product
       pass the new expression to the worker for the next term
    else
       declare success
  else
    if there is another product
      remove the leading product from the expression
      pass the new expression to the worker for the new leading product's leading term
    else
      declare failure
9
assylias On

A standard condition will work that way (short circuit) because it will only evaluate the expressions if necessary (if the first part of an || condition is true it won't evaluate the rest):

if ((value1() < 15 && value2() > 25) || (value3() > 0 && vaue4() < 5) ...)

Note that I have replace the values by method calls - if you precalculate each value of course it won't work...

Examples:

  • if your condition value1() < 15 returns false, then value2() won't be called
  • if the first condition value1() < 15 && value2() > 25 is true, value3() and value4() won't be evaluated.

References:

See JLS #15.23 (emphasis mine):

The conditional-and operator && is like &, but evaluates its right-hand operand only if the value of its left-hand operand is true.

Similarly in JLS #15.24:

The conditional-or operator || operator is like |, but evaluates its right-hand operand only if the value of its left-hand operand is false.

4
adriann On

Conditional logic by default evaluates the least amount of conditions needed to obtain an evaluation result. This is not specific to Java. This is how things work. Also, the grouping parentheses are completely optional in your case.

Depending on your use case, you may want to push forward inside the condition the expressions that are most likely to be true. And perhaps consider caching for a certain amount of time some of the results, if applicable.