0

在这段名为Don't fear the monad 的视频中，在05:02到06:05之间，Brian Beckman 说：

每个命令式程序员都会经历这个阶段，学习可以用查找表来替换函数。通常，您这样做是为了提高性能。你想制作sin函数或cosine 函数，只需制作一个表格并在该表格中进行插值......每个人都学会了这个技巧。

我想知道他所说的这个技巧是什么意思，以及它如何提高性能。你能详细说明一下吗？

它只是意味着有某种外观Dictionary<TKey, Func<TInput, TReturn>>吗？

4

1 回答 1

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.

于 2016-07-17T01:19:31.583 回答