5

这是我正在处理的代码：

#include <iostream>
#include <map>

using namespace std;

static unsigned long collatzLength(unsigned long n) {
    static std::map<unsigned long,int> collatzMap;
    int mapResult = collatzMap[n];
    if (mapResult != 0) return mapResult;

    if (n == 1) {
        return 1;
    } else { 
        collatzMap[n] = 1 + collatzLength(n%2==0?n/2:3*n+1);
        return collatzMap[n];
    }
}

int main() {
    int maxIndex = 1;
    unsigned int max = 1;
    for (int i=1; i<1000000; i++) {
        //cout<<i<<endl;
        unsigned long count = collatzLength(i);
        if (count > max) {
            maxIndex = i;
            max = count;
        }
    }
    cout<<maxIndex<<endl;
    getchar();
    cout<<"Returning..."<<endl;
    return maxIndex;
}

当我编译并运行这个程序（使用 Visual Studio 2012 和 Release 构建设置）时，在程序打印“Returning...”后需要大约 10 秒（在我的计算机上）关闭

这是为什么？

注意：我知道这个程序写得不好，我可能不应该在 collat​​zLength 上使用“静态”，也不应该为该函数使用缓存，但我对如何使这段代码更好并不感兴趣，我只是有趣的是为什么要花这么多时间才能关闭。

4

5 回答 5

4

转到启动项目的项目设置，调试部分。进入_NO_DEBUG_HEAP=1部分Environment。即使在发布模式下，您也需要这样做。

于 2013-08-20T17:30:24.283 回答
2

在 Visual Studio 上销毁 astd::map非常慢，尤其是对于 Debug 版本。使用 anunordered_map代替，减速应该已经消失了。

VS 的 map 实现构建了一个用于存储数据的红黑树，这意味着您将必须分配很多树节点来存储所有数据。销毁期间的限制因素是遍历树和取消分配所有节点所需的时间。使用 aunordered_map遍历通常会容易得多，因为分配的存储桶通常更大并且不像红黑树节点那样分散（尽管您的里程可能会有所不同）。

于 2013-08-20T15:49:51.353 回答
2

关闭需要很长时间，因为collatzMapis static，所以它只会在程序退出时被释放，并且它包含大量数据，因此需要很长时间才能被释放（大小刚刚超过200万，并且由于如何map有效，对于其中的每一个，至少有一个需要释放的指针）。

也就是说，在 Dev-C++ 上，退出只需不到一秒钟。我猜 Visual Studio 做得不好。

于 2013-08-20T15:48:11.493 回答
0

我刚刚在我的机器上尝试了 VS 2012 发布版本。“返回”后关闭程序不超过2秒

于 2013-08-20T16:03:42.477 回答
-2

When running VS in Debug mode, there are a lot of error checking flags set (e.g. bounds checking, memory watching, etc.) Since you are creating a lot of data recursively in a static map, it is scanning the memory before it is released to make sure nothing was corrupted. When you switch to a Release build, it should be almost instant.

Upon further inspection, you are basically allocating almost 1 million pairs of (unsigned long, int) in the static portion of memory. This effectively means that ~8MB of data must be freed before the application can finish closing (and since map isn't required to be contiguous, it must iterate through all 1 million pairs to delete each one). Other implementations may optimize memory usage a bit by reserving chunks of space (if it reserved enough space for say, 100 pairs, it would decrease the deallocation process by 2 orders of magnitude).

All that said, asking why bad code behaves badly is like asking why you get wet when you jump in a pool.

于 2013-08-20T16:00:06.630 回答