相关疑难解决方法(0)

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

我编写了一个天真的测试平台来测量三种阶乘实现的性能:基于循环,非尾递归和尾递归.

令我惊讶的是,最差的性能是循环的(«while»预计效率更高,所以我提供了两者) ,其成本几乎是尾部递归替代的两倍.

答案:修复循环实现,避免使用BigInt的*=运算符,因为其内部«循环»变得如预期的那样快

我遇到的另一个"woodoo"行为是StackOverflow异常,在非尾递归实现的情况下,对于相同的输入没有抛出异常.我可以通过逐步调用具有越来越大的值的函数来规避StackOverlow ...我感到很疯狂:) 答案:JVM需要在启动期间收敛,然后行为是连贯的和系统的

这是代码:

final object Factorial {
  type Out = BigInt

  def calculateByRecursion(n: Int): Out = {
    require(n>0, "n must be positive")

    n match {
      case _ if n == 1 => return 1
      case _ => return n * calculateByRecursion(n-1)
    }
  }

  def calculateByForLoop(n: Int): Out = {
    require(n>0, "n must be positive")

    var accumulator: Out = 1
    for (i <- 1 to n)
      accumulator = i * accumulator
    accumulator
  }

  def calculateByWhileLoop(n: …