简介

memory-bound 函数能够称为内存受限函数，它是指实现给定计算问题的工夫次要取决于保留工作数据所需的内存量。和之绝对应的就是计算受限 compute-bound 的函数，在计算受限的函数中，计算所须要的计算步骤是其决定因素。

本文将会介绍一下内存受限函数和它跟内存函数的关系。

内存函数

内存函数和内存受限函数看名字如同很相似，其实他们的作用是不同的，咱们先来看下内存函数。

在学习算法中，有一个非常简单好用的算法叫做递归算法，相熟递归算法的敌人可能都晓得，递归算法尽管好用，然而有个毛病就是会反复计算递归过程中的函数，比如说递归中最经典的斐波拉赫数列：

 Recursive_Fibonacci (n)
 {if (n == 0)
         return 0
     if (n == 1)
         return 1

     return Recursive_Fibonacci (n-1) + Recursive_Fibonacci (n-2)
 }

很简略，然而咱们来思考下计算过程，F(3)=F(2)+F(1), 而 F(4)=F(3)+F(2)，在这个过程中须要计算 2 次 F(2) 的值。如果计算的 N 值够大的话，反复计算的值还会更多。

一个解决办法就是将之前计算过的后果应用内存存起来，这种办法就叫做内存函数：

 Fibonacci (n)
 {
     for i = 0 to n-1
         results[i] = -1  // -1 means undefined

     return Fibonacci_Results (results, n);
 }

 Fibonacci_Results (results, n)
 {if (results[n] != -1)  // If it has been solved before,
         return results[n]  // look it up.
     if (n == 0)
         val = 0
     else if (n == 1)
         val = 1
     else
         val = Fibonacci_Results(results, n-2) + Fibonacci_Results(results, n-1)
     results[n] = val  // Save this result for re-use.

     return val
 }

尽管间接递归的逻辑很简略，写起来也很不便，然而它的工夫复杂度会更高。

内存受限函数

内存受限函数次要用来形容一个应用 XOR 的函数，它由一系列计算组成，其中每一次计算都依赖于前一次计算。

因为这样的内存依赖关系，所以内存受限函数次要用在密码学中，能够避免明码的暴力破解工作。

上面举个内存受限函数在避免垃圾邮件中的应用。

内存受限函数的应用

应用内存受限函数来避免垃圾邮件，次要应用的是 POW 的原理，也就是说，你能够给我发垃圾邮件，然而前提是须要付出一些代价。

当然，最后的防垃圾邮件的原理是应用 CPU 受限函数。

1992 年，IBM 的钻研科学家 Cynthia Dwork 和 Moni Naor 在 CRYPTO 上发表了一篇题为《通过定价来阻止垃圾邮件》的论文，他们提出了一种利用 CPU 受限函数的性能来阻止滥用者发送垃圾邮件的可能性。

该计划的原理是：如果滥发邮件的老本很低，那么垃圾邮件就可能横行。如果可能通过以低廉的 CPU 计算的模式为发送邮件增加额定的计算成本，就能够缩小垃圾邮件。应用 CPU 受限函数，使得每发一次邮件都须要耗费肯定的 CPU 资源，从而避免在短时间内发送大量的垃圾邮件。

CPU 受限函数是一种冲破，然而也有其毛病。

因为快 CPU 的计算速度比慢 CPU 快得多。此外，高端计算机系统也有简单的流水线和其余有利于计算的优化性能。因而，领有高端零碎的垃圾邮件发送者简直不会受到这种 CPU 受限函数的影响。

从而会因为不同用户机器性能的不同，导致十分大的计算工夫差别。比方如果一个算法在高级计算机上须要几秒钟，那么在老的计算机上可能须要 1 分钟，而在性能更差点的手机上可能会须要几分钟，那么这个算法必定是无奈被手机用户承受的。

因而，研究者们关注的是如何找到一种在大多数计算机系统都以大致相同的速度运行的函数，尽管在高级计算机上速度会更快，但也只是略微快一点而已，不是几何级数的快，那么就能够在容忍范畴之内。

这种办法就是应用内存受限函数。内存受限函数是指计算工夫由拜访内存的工夫摆布的函数。内存受限函数以一种不可预测的形式拜访大内存区域的地位，从而无奈应用缓存来晋升性能。

应用内存受限而不是 CPU 受限也有其工业上的起因，近年来，尽管 CPU 的计算速度急剧增长，但在开发更快的主内存方面停顿绝对较小。所以能够预感，在将来的肯定工夫内，内存受限函数还会有越来越多的利用场景。

本文已收录于 http://www.flydean.com/memory-bound/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！