0

For a machine learning application, I need to sort lists based on a value that gets updated but is initialized to 0. The problem is that parts of the updated values initially 0 are used int he formula that's used as sort-key, one of which in the denominator, so it'd throw DivisionByZero erros on the first iteration.

Since checking for 0 will be done multiple times for each element, I want to write denominator of the formula very efficient while still maintaining a reasonable degree of readability. I came up with 4 versions so far:

import random
import datetime


def generate_value_pair():
    # in my case about 10% of the time b == 0
    return 10**6 * random.random(), \
        10**6 * random.random() * (random.random() > 0.1)


def f0(a, b):
    if b != 0:
        return a/b
    else:
        return 0


def f1(a, b):
    return (not b or (a/b)+1)-1


def f2(a, b):
    return b and a/b


def f3(a, b):
    try:
        return a/b
    except:
        return 0


def compare(func):
    n = datetime.datetime.now()
    for _ in range(10**8):
        func(*generate_value_pair())

    print(datetime.datetime.now() - n)


fs = [f0, f1, f2, f3]

# sanity check for new versions
# not using assert because of floating point precision at 2/7
for a, b in zip(list(range(10)), reversed(list(range(10)))):
    t = (a, b)
    for f in fs:
        print(float(f(*t)), end='\t')
    print()

for f in fs:
    compare(f)

The results of this test are as follows:

0:00:36.163209
0:00:38.947623
0:00:35.436445
0:00:35.450830

Unsuprisingly f2, which is the function with the least amount of operations and branches is fastest. Much to my surprise, f3 with try/except clocks in at a very close 2nd place, with the naive if/else f0 at 3rd and my initial attempt at improving the naive version f1 comes in at last place.

try/except is much faster than I thought, so I did another test where 50% of the cases b == 0:

0:00:36.998776
0:00:37.043782
0:00:35.061485
0:00:41.943822

So what's slow is the throwing of the exception and what comes after, but if your case happens rarely try/except can be pretty close to "optimal", as seen above.

My Question is: Is there any faster way to do this?

jaaq
  • 1,188
  • 11
  • 29

1 Answers1

1

Is there any faster way to do this?

Floating point formats have nasty precision loss problems; but if you want to be crafty you can abuse the precision loss problems.

Specifically; if you add the "smallest in magnitude" non-zero value to almost all floating point numbers it will do nothing due to precision loss; but if you add that same value to zero then the result will be the "smallest in magnitude" non-zero value (and become safe to use a divisor because it's technically not zero).

In other words:

def f3(a, b):
    return a/(b + math.nextafter(0.0, math.inf)

However; this will only work if the b is never a tiny negative number (e.g. if b is equal to -math.nextafter(0.0, math.inf) then you'd be turning a non-zero into a zero). If that could be a problem (if the divisor could be negative) you might be able to cheat by negating both the numerator and the divisor.

Brendan
  • 35,656
  • 2
  • 39
  • 66
  • Presumably you'd want to expand that `nextafter` manually into a numeric literal in scientific notation, otherwise interpreters like CPython will eval it every call. (And then you get to explicitly choose whether you pick the smallest *normal* number (DBL_MIN), or the smallest subnormal (`std::numeric_limits::denorm_min`). Some modern hardware has no [penalty](//stackoverflow.com/q/60969892) when adding a subnormal to a normal number, but older CPUs do take a microcode exception for that. e.g. Nehalem and earlier.) – Peter Cordes Dec 12 '20 at 02:45
  • What @PeterCordes said checks out, your proposition is 0.095 seconds slower than my f2 on 6 million runs(my machine is number crunching right now, so I did less runs, but almost 0.1 seconds slower is probably significant enough. Will run another test later today). Interesting solution though, I hadn't even thought of that! – jaaq Dec 13 '20 at 18:53
  • Also math.nextafter came in Python3.9 but I tagged Python3.6. – jaaq Dec 13 '20 at 18:53
  • @jaaq: Did you try manually using a numeric literal like `2.2250738585072013830902327173324040642192159804623318306e-308`? That should just be a constant in Python after it's parsed. ([Is DBL\_MIN the smallest positive double?](https://stackoverflow.com/q/39746861) quotes both normalized and denormal doubles values, with excessive precision, so that would let you tell whether it's slow because of calling nextafter, or slow because of denormals, or both.) – Peter Cordes Dec 13 '20 at 18:56