0

In this video titled Don't fear the monad, between 05:02 and 06:05, Brian Beckman says:

Every imperative programmer goes through this phase of learning that functions can be replaced with table look-ups. Often, you do this for performance. You want to make the sin function or the cosine function, just make a table and interpolate in that table....Everybody learns this trick.

I am wondering what he means by this trick and how it improves performance. Could you please elaborate?

Does it just mean having some sort of a look up like Dictionary<TKey, Func<TInput, TReturn>>?

Water Cooler v2
  • 32,724
  • 54
  • 166
  • 336

1 Answers1

2

It means that every algorithm, given enough (potentialy infinite) memory, can store precomputed output values based on input values in an (indexed) array, and thus convert the algorithm to O(1) array lookup. It's a trick as old as computing itself, predating computers by centuries. Scientists always used tables of precomputed values to get results quickly without doing actual computation.

The Wikipedia article covering this topic is https://en.wikipedia.org/wiki/Lookup_table .

BTW, many real-life algorithms (CRC comes to mind here) do it too, especially when speed is crucial (real-time applications). Note that the amount of memory needed to store the precomputed values is directly related to expected precision and amount of input variables.

  • Ah! You mean memoization? – Water Cooler v2 Jul 17 '16 at 01:21
  • @WaterCoolerv2 nope. It's literally what BB said - https://en.wikipedia.org/wiki/Lookup_table ; memoization is essentially caching those computation results you got; table look-up is preparing a large enough set of them beforehand. –  Jul 17 '16 at 01:22
  • That is precisely what memoization is? And that would be suitable only for pure functions with no side effects or at the very least deterministic side effects. – Water Cooler v2 Jul 17 '16 at 01:28
  • 1
    @WaterCoolerv2 It really isn't memoization. In a program that uses memoization, somewhere there's code that knows how to compute the answer. In a program that just uses a lookup table, it need not contain any code to compute anything. E.g., this function does not use memoization but does use a lookup table: `function doubleSmallIntegers(x) { return [0, 2, 4, 6, 8, 10][x]; }` – user94559 Jul 17 '16 at 01:35
  • @smarx I get it now. Thank you. :-) – Water Cooler v2 Jul 17 '16 at 01:43