2
$\begingroup$

Short-circuit evaluation is a straight forward subject for lazy evaluation on Boolean expressions, I noted that two factors could be useful in ordering Boolean functions to improve run-time. But this is applicable in a very particular hypothesis:

  1. Knowing a percentage of positive (hence negative) result of a function. This is followed by a very illustrative example.
  2. Knowing execution run-time of the function on data (knowing size of data can be a hint).

My case is easy to understand. Here is a description:

Let's say F is a Boolean function that scores sentiment and returns -1 or 1. I've been doing some improvements to predict sentiment scores on big arrays of text, and I can calculate How much is likely a function will return 1 (probability withing a tolerated error range) lets call it P(f) = Pf (probability of being positive)

We have also an estimation of execution time since data to be analysed is measurable. lets call it T(f) = Tf We define positiveness speed as follows:

PS (f) =  Pf  / Tf

Let Lazy be a function which takes a Boolean expression, and gives the best ordering of functions for run-time based on PS scores.

Lazy (&, f1, f2, …, fn) = and_Order (f1, f2, …, fn) 

Where and_Order is an ascending order of positiveness speed.


Lazy (or, f1, f2, …, fn) = or_Order(f1, f2, …, fn) 

Where or_Order is a descending order if positiveness speed.

Obviously this is a high level optimization and not a compiler task. Is this an established study? How is this practical in cases other than sentiment analysis? Is the PS(F) even correctly representing what it should be representing?

$\endgroup$
  • 1
    $\begingroup$ Note that in the & case more complex functions are evaluated first, which is probably not the desired behavior. Perhaps a better fit would be evaluating by decreasing order in $\frac{1-P_f}{T_f}$. In any case, I don't know whether this has been studied, but this sounds interesting. $\endgroup$ – Ariel Sep 2 '17 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.