什么时候花内存来计算速度是值得的？

Question

我正在开发用于处理大量数据的数据分析算法。

因此，我的目标是发展我的数学已经在这样的方式，是有可能在以后分发算法在许多机器(大数据)。

我能够开发我的算法，以这样的方式，它计算一些中间元数据和预先计算的值，它保存-元数据的实际原始数据。这可能会使存储的数据量增加相当多(实际上增加数百%)，但这也会大大减少处理时间(如果不是数千%，也会减少数百个)。

这就引出了一个问题:构建智能算法和实现来交换RAM以获得处理能力是否是一个好主意。

这反过来又打开了一个问题:什么是更昂贵的RAM或处理能力？

当然，如果不执行所有措施并进行适当的比较计算，就不可能准确地回答这一问题。

但是，开发时间(我的时间)也是有价值的;-)，所以我想在开发过程中做出好的决定。我的脑子里已经有了不同的算法，但它们还没有实现--这需要几个月(希望不是几年)--在我从事学术研究的时候，这一点也不奇怪。

我可以有根据地猜测我需要多少内存(时间是xyz)，以及花费的时间会有多少(就像大O符号中的那样)。

在所有这些介绍之后:是否有一个经验规则，当它是值得它花费RAM的计算速度？

有关硬件

的详细信息

首先，我正在开发算法。实施只是从这一点开始的，而不是我目前主要关注的问题。在设计我的算法(数学)时，我已经试着让那个必须在一天之外订购服务器的人记住了。(我不是很好吗？；-)这意味着，我不知道所有的实现细节，但我试着猜测一下我认为可能是什么情况：

• 我的算法将运行在廉价的商品服务器硬件上。CPU和GPU都是选项(实际上是在我当前的设计中将它们结合在一起)。RAM在每台机器的GB范围内。多少GB内存，这是我的问题的目标。整个数据必须在RAM中，所以如果需要的话，它就像内存中的数据库(只是没有数据库)。
• 我希望它能以一种与其他程序很好地结合的方式实现。考虑使用JVM语言(Scala，Java)，所以我想这部分会更容易，对吗？如果这个实现可以在Mesos等中运行，那就太好了，我想这应该是可能的，但我个人不知道如何做这样的事情。不过，我想到了使用Akka演员--到目前为止，这似乎适合我的算法。
• “有什么原因不能实现您的算法，然后对它们进行分析，然后决定是否值得在此点上添加缓存？”问题不只是实现阶段，而是证明我的算法在数学上是正确的时间。我的脑子里有它们，这是很好的，但这并不意味着它们是健全的。这需要大量的工作。
• 我已经用早期的原型做了一些分析，这就是为什么我想要计算这个元数据。有些函数调用相当昂贵。为了使它们更便宜，我不得不做一些市长的改变，不仅我的实现，而且我的数学算法本身。这个想法是站得住脚的，证明他是健全的时间证明仍然没有。

有关算法

的详细信息

首先：“算法”并不意味着软件的实现(我有这种感觉，有些人可能会弄错)。算法是为了得到我的数学模型而要采取的步骤的数学描述。

这是一个交易：

1. 计算成本高的部分是数值之和。这些值也需要计算，这需要很长时间。
2. 通过不计算所有这些值，而只计算一些值，忽略非常小的值(隐式地将它们设置为零)，我能够近似于1。我能够计算出哪些值是很小的，而不需要计算它们本身。这种计算比计算值更便宜，但也很昂贵。
3. 但是我开发了一个(非常聪明和复杂的)机制来达到这个速度，但是这个机制需要很多内存。

第三条机制的实施是我们正在采取的行动。它不完全是元数据，但这种机制需要消耗内存。所以，我想，这里的大多数人都不会想到“缓存”。它甚至不是真正预先计算出来的值，而是存储在彩虹表或类似的东西中。占用内存的是机制本身的元数据，因为机制具有状态。

我希望现在的情况更清楚。

大O表示法的

计算复杂度

对于上述算法(1至3.)，n为输入数据量：

1. 关于O(n*log(n))
2. 关于O(n*log(n))，但速度更快。
3. 关于O(log(n))

Answer 1

什么更贵，内存还是处理能力？

这是一个错误的二分法，有很多原因。

如果您的目标用户是普通用户，那么您的约束可能就是他已经安装在机器上的内存；您不会要求他购买更多的内存来运行您的应用程序，对吗？

如果你是你自己的听众，并且你在考虑购买一台新机器(通常需要获得更多处理器马力)而不是购买更多内存，答案应该是显而易见的:更多的RAM几乎总是更便宜。

如果您试图通过编写软件的方式来解决这个问题，最好的操作方法是以尽可能简单和合理的方式编写一个原型，然后通过测量和分析来决定优化的位置。这将使您最大限度地利用开发资源，因为它将集中于它所属的问题:在您的系统中，性能考虑因素非常重要的那一小部分代码。

如果您需要更好的灵活性，请考虑虚拟机/云计算。您可以根据需要(在处理器核心+内存基础上)配置这些配置，并混合和匹配配置，直到找到您喜欢的最佳位置。

Answer 2

简短的回答:这是你的工作，以最专业和最有效率的方式解决它。

你可以咨询其他研究人员、计算机科学家和软件开发从业者，但是没有人对你想要的系统有那么深的了解。

最好的情况是，你所做的每一个受过教育的猜测都将在大致的范围内。最糟糕的情况是，你所有的猜测都是错误的，你的一些早期选择最终都是错误的，浪费了你宝贵的时间、精力和资金。

我建议把重点放在做研究的艺术上：

• 训练自己更深入、更有逻辑地思考
• 记录你的假设和推理过程，每天
• 保存旧文档，以便您可以重新查看它们。有时你决定放弃一个想法，但后来意识到你仍然需要它们。Idea不像源代码，你不能保持你的想法干净。
• 遵循适用于计算机科学研究的任何其他最佳实践。良好的设计，良好的编写，良好的组织，文档，源代码控制，可维护等.

您将需要假设高密度、低延迟的持久性内存(如三维XPoint )将产生结果。您需要在您的研究中找到利用这一点的方法，尽管您无法访问实际的硬件。因此，在您的研究中，您需要“模拟”这种硬件的特性。

由于这样的模拟需要不一定正确的假设，所以您可能需要做出多组假设(场景)，并说明您的研究在每个场景中的影响。(有点像全球变暖的研究。)

除了无处不在的持久内存之外，您还可能不得不担心GPU、高通Centriq、Movidius Myriad、FPGA (现在在AWS上)、自定义ASIC、张量处理单元、光互连、到达(2016)、另一个技术泡沫破灭等。

Answer 3

如果我们假设您有无限数量的RAM可用，那么对于“何时值得将RAM用于计算速度”这个问题有一个简单的答案:当从内存分配、管理和检索数据所需的时间少于每次需要时(重新)计算它所需的时间时。

在这方面，有若干因素需要考虑：

• 分配/管理的成本往往具有不断增加的边际成本。换句话说，随着内存的增加，每增加一兆字节的成本就会更高。尤其是在涉及垃圾收集的情况下。
• 缓存答案的值越多地使用该值。例如，如果您只需要一个值一次，缓存它将使事情变得更慢，也会浪费内存。
• 与记录和档案管理有关的财务费用。尽管64位时代打开了内存，指出理论极限超出了目前所能设想的使用范围，但如果你超过了标准，你将支付额外的费用，所以成本一般与RAM的大小不成正比。

在我的经验中，唯一的经验法则是缓存结果在深度递归算法中非常有效，在这种算法中，‘底部’值再次被拉进来，以构建“更高”的结果。如果您能够预测哪些值是最常用的，那么您就可以通过缓存这些值来获得最大的收益。缓存所有东西，以备以后再次需要时使用，可能会损害性能。

最终，我将从没有缓存开始，然后尝试添加它们。我常用的成语是这样的模式：

def calculateFoo(bar):
  if bar in cache:
    return cache[bar]

  foo = complicatedCostlyCalculation()

  cache[bar] = foo

  return foo

很容易将其添加到后面，或者将其注释掉以查看缓存的影响。