1
$\begingroup$

One of my coworkers came up with a nice technique to solve a problem and I feel like it must already have a name. I just don't don't know how to figure out what it is.

It is a technique for caching easy answers for a subset of an input domain before falling back to an expensive computation. In that respect it reminds me of the semantics of a Bloom Filter or the pre-optimization idea of a Karnaugh Map.

Simple description w/ pseudocode:

// Determine whether "foo" is true with respect to the given ComplexThingy,
//   for the inputs bar and baz

boolean isFoo(ComplexThingy t, A a, B b):  
    // Let's say A and B are enums, or ints in a limited range, etc.
    return expensive_computation(t, a, b)

// Alternative implementation w/ enhanced ComplexThingy for which
//   "trivial" cases (i.e. those that can ignore all but one dimension of the
//   input space) have been precomputed and stored in a simple bit array

boolean isFoo(ComplexThingyV2 t, A a, B b):
    if t.quickPosLookup[a]
        return true
    if t.quickNegLookup[b]
        return false
    return expensive_computation(t, a, b)

Hopefully I've been able to convey that clearly. Thanks for your time!

$\endgroup$
3
  • $\begingroup$ The general approach you're describing sounds like memoization. $\endgroup$
    – usul
    Jul 16, 2016 at 23:45
  • $\begingroup$ Thanks @usul, I considered this, but I think this is different enough that just calling it memoization would be misleading. (1) it's not saving the result of the function for the exact inputs. (2) it's precomputing rather than lazy-computing. $\endgroup$
    – leoger
    Jul 17, 2016 at 0:44
  • $\begingroup$ @leoger, you have mentioned it. This is, basically, the caching mechanism. $\endgroup$
    – John L.
    Jul 4, 2019 at 16:21

1 Answer 1

2
$\begingroup$

This is related to the notion of "fast path, slow path" from computer systems. In systems, one common optimization method is: if there is a common case that can be handled fast and is common, first test whether the input falls into that case and if so solve it and return immediately; otherwise, fall back to the complex computation. For instance, the slow path might have to handle corner cases and difficult situations that arise only rarely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.