这个函数能否进行优化？

Question

这个函数能否进行优化？

17

经过大量的剖析，我发现这个方法占据了计算时间的大部分%. 我真的看不到优化的方法，因为它是一个可怕的函数。(它是...)也许有人可以给我展示一些好的想法或建议吗？

public static double perceivedLoudness(double L_G, double L_ETQ, double a0) {
  double t1 = 1d + 1 / 4d * Math.pow(10d, 0.1d * (L_G - a0 - L_ETQ));
  double t2 = Math.pow(t1, 0.25);
  return 0.064d * Math.pow(10, 0.025 * L_ETQ) * (t2 - 1);
 }

以下是改进后的版本：

public static double perceivedLoudness(double L_G, double L_ETQ, double a0) {
  double x = L_G - a0 - L_ETQ;
  double t1 = 0.25 * Math.exp(0.230259 * x) + 1;
  double t2 = Math.sqrt(Math.sqrt(t1));
  return ltqFactors[(int)L_ETQ]  * (t2 - 1);
 }

查找ltqFactors的方式如下。ltqValues保存了来自给定ltq函数的20个点，这应该足够。

for( int i = 0; i < etqValues.length; ++i) {
  ltqFactors[(int)etqValues[i]] = 0.064d * Math.exp(etqValues[i] * 0.05756462732485114210d);
  }

编辑：经过更多的测试运行和更多的文件，我实现了 ~100% 的加速：

旧版：7000000 次调用，6.2%
新版：8000000 次调用，3.2%

到目前为止，谢谢你！

编辑2：我不知道该接受哪个答案。:( 通过一些其他的改进（主要是查找表），9000 个声音文件的处理时间从4:30分降至3:28分。

我将继续开放这个问题，看看是否有其他想法，但然后会接受一个答案。

编辑：我有点沮丧。我使用 JFace treeviewer 让用户浏览结果，但它需要比计算本身更多的时间来更新。:/

- InsertNickHere

我想知道有人是如何想出这样的函数的。那些常数看起来如此随意！ - Matt Phillips

1

@controlfreak http://ergo.ucsd.edu/~holcus/papers/JSNC2000.pdf - InsertNickHere

那个方法中没有什么应该需要长时间计算的，你确定它不是因为被多次调用而占用了大部分百分比吗？ - Fredrick Pennachi

我能建议您记录下所有的优化，并引用算法来源，这样可以让代码维护者的工作更轻松一些 ;) - Alex Spurling

@Alex 我会把这个主题链接给你。;-) 开玩笑，我会尽力好好记录文档的。 - InsertNickHere

显示剩余5条评论

9个回答

3

我猜测

double t2 = Math.sqrt(Math.sqrt(t1));

比...更快

double t2 = Math.pow(t1, 0.25);

- Landei

1

@插入：你确定它确实更快吗？ - Joachim Sauer

1

@Joachim 我不太擅长微基准测试，但如果我的结果正确的话，它会快得多。（~快速：33133194，慢速：617337165/纳秒）。我已经进行了2147483次计算，每个测试都有100个“迭代”。 - InsertNickHere

3

这个数学公式看起来似乎无法重新排序以避免任何重复计算，所以需要根据该函数的使用方式和需要多精确的结果来确定采取的方法。

最好的方法是避免对相同输入值重新计算数值。你的代码是否可以保存相同输入值的计算结果呢？如果不能，你可以为数值设置一个缓存，但请注意，双精度浮点数可能有很多值，你可能希望将其折叠到一个已知的区间（例如，从0到1折叠成从0到99的整数）。

- Thorbjørn Ravn Andersen

2

浏览你提供的论文，看起来L_ETQ和a0仅仅是声音频率(Bark)的一个函数。

因此，我们至少可以为给定的频率计算结果制作一个表格。例如，缓存以下结果：

.064 * Math.pow(10, 0.025 * L_ETQ)

按频率排序。[也可以缓存 (a0 + L_ETQ) * .1]

此外，可能有微小的影响，但我会将 1/4 转换为 0.25。

- aepryus

1

为您的程序可以处理的输入范围预先生成查找表。

再也没有比这更快的了！:)

- Fredrick Pennachi

1

缓存输出结果，针对输入参数，可能会有所帮助：

http://en.wikipedia.org/wiki/Memoization

- Dave Bish

我更关注缓存未命中的总量。如果他有非常广泛的值范围，缓存命中的概率将会极低。然而，这将减少相同值集合的进一步计算。此外，我也会担心在大缓存集中查找的成本[即使使用哈希]。 - monksy

L_G - a0 - L_ETQ 可能会有很大的变化，因为声压级是以双精度测量的，我不想失去这个。粗略地说，我可能有超过3600000个不同的值。（假设有1000种不同的压力、20个a0和20个L_ETQ值。） - InsertNickHere

1

这个还没有被提到，所以我来说一下。

你可能想考虑从浮点数运算转换为整数运算。整数运算速度要快得多。由于浮点数的加法和存储方式，图形通常使用整数运算。你需要进行转换，但我相信你会获得相当大的性能提升。唯一的问题是，你必须定义你愿意接受多少精度。

- monksy

2

你能接受在小数位数上设定一个固定的上限吗？ - monksy

0

尝试缓存一些值（我猜L_G和L_ETQ不是那么可变的，对吗？）
尝试在与体系结构相关的代码中实现，并使用JNI。

- onof

0

我会对其进行一些堆栈快照，以消除猜测。这样我就可以确定时间不会被用在其他地方，比如读取数据并将其转换为浮点数，或者打开/关闭文件。当我确定这个例程占用了大部分时间时，我相信它几乎所有的时间都花在了调用数学函数和将L_ETQ转换为整数上。可能可以使用记忆化技术来优化这些数学函数。另外，正如Alexandre所说，你也许可以通过插值完成所有操作。

事实上，您可能有多个需要优化的事情。如果这需要大约180秒，而其中50％的时间是在堆栈上运行此例程，则如果将其时间减半，则将时间减少45秒至135秒。但是，现在此例程仅在堆栈上运行45/135秒或1/3。这意味着其他一些事情正在使用另外的2/3或90秒钟，我敢打赌其中有一些事情也可以进行优化。如果您可以将它们缩短到45秒，那么总时间将减少到90秒，并且数学例程所占的百分比将再次达到50％，因此您可能可以从中挤出更多。就是这样。每次您缩小其中一部分时，其他部分的百分比会增加，因此您可以不断追求它们，直到真正尽可能地压榨它们。

- Mike Dunlavey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alexandre C. · Accepted Answer

你的函数似乎是解析函数，我建议完全用插值方法来替换它。这样，您可以将昂贵的调用 Math.Pow 函数减少到几个算术操作。

在这种情况下，最好使用有理函数逼近。您的函数可能在复平面上有极点，这通常会破坏多项式插值法的效果。

请注意，您有两个变量：L_G - a0 - L_ETQ 和 L_ETQ。插值应该只在一个变量中进行。

我会选择将 t2 近似为 L_G - a0 - L_ETQ 的函数的有理函数逼近方法。请参考《Numerical Recipes》中的实现技巧。

此外，对于最后一部分，请替换为。

Math.pow(10, 0.025 * L_ETQ);

通过

Math.exp(L_ETQ * 0.05756462732485114210d)

所以，您只需要进行一些算术运算和一个指数运算 (即 exp(L_ETQ * 0.025 * log(10))) 就可以了。

编辑: 查看 t2 作为 L_G - a0 - L_ETQ 函数的图表。

编辑: 替换

double t1 = 1d + 1 / 4d * Math.pow(10d, 0.1d * (L_G - a0 - L_ETQ)); 
double t2 = Math.pow(t1, 0.25);

通过

double x = L_G - a0 - L_ETQ;
double t1 = 0.25 * Math.exp(0.230259 * x) + 1;
double t2 = Math.sqrt(Math.sqrt(t1));

现在你应该获得更多%了。此时，进行有理逼近可能会过度工程化：你有两个exp和两个sqrt。