预先计算大型值表

Question

我的程序中有一个数学公式,它包含两个值,介于0和1之间,并且需要做很多工作才能找到答案.

我也希望能够做反向,即我想知道什么输入值将产生一定的输出.我无法通过分析来做到这一点,因为可以从众多输入中产生相同的答案,并且公式过于复杂.

我的问题是我目前正在做这样的事情,这需要相当长的时间来计算

  for(double i = 0; i <= 1 ; i += 0.0001)
      for(double j = 0; j <= 1; j+= 0.0001)
           answer = formula(i,j); //do the math
           if( Math.abs(answer - answerWanted) < 0.001)
                //close match found

看到公式是静态的,我当然可以预先计算这些值.我认为查找值比执行许多计算要快得多.

我之前从未做过这样的事情.有谁知道使用什么数据结构/如何索引/如何存储结果？目前我唯一的想法是,我可以以某种方式对答案进行排序以减少搜索空间,或者只是在运行时初始化一个巨大的数组.如果重要,答案只能在0到2000之间.

Answer 1

基本上，您有一个 10,000 x 10,000 的double值数组。如果将其保留在内存中，它将占用大约 800Mb 的 Java 堆内存。

以下是一些可能有帮助的策略：

• 将数据保存在数据库表中。您可能可以实现亚毫秒级的访问时间（取决于数据库产品、调优、访问模式等），并且内存中的缓存可以改善情况。假设您存储了{i, j, value}三元组，则需要{i, j}为正向查找和{value}逆函数建立索引。

• 如果公式是连续且相对平滑的，您可以减少存储的数据点数量（例如，减少 1000 个到 1000 个），并使用插值法为您提供中间数据点的近似值。

• 如果公式没有局部最小值和最大值，您可以使用爬山法的变体来计算反函数。

在所有这些中，您需要考虑反函数不太可能是一对一函数。可能存在出现在多个{i, j}点的值，并且可能存在未定义函数的其他值。