8

以下问题是否有众所周知的解决方案？

  • 你有很多字符串的向量

  • 你很高兴地用几十万个字符串填充它，而且速度很快

  • 您以任意方式操纵字符串；生活很好。

  • 你已经完成了向量；vector 超出了范围，现在你必须去拿些咖啡然后坐下来，而每个字符串都被一个接一个地破坏。

编辑：问题解决了！

我刚刚在同一台计算机上的 Linux 上运行了下面的代码，这很好，这让我找到了解决方案。结果证明是我的系统造成的——这是我很久以前自己造成的，但我已经忘记了。
解决问题后，时间显着减少，甚至比使用 GCC 更好！

虽然这是一个很好的谜题，所以我不会发布答案，而是做其他事情：
我现在不允许在这个问题上悬赏，但如果你认为你知道原因，请试一试。如果它是正确的，我会接受它并给你一个不错的赏金。（如果我忘记给你赏金，请提醒我！）
如果没有人知道，那么我会在一段时间后自己发布。

示例代码：

我曾经和任何人一样持怀疑态度，但现在我想人们确实有理由认为他们的 STL 很慢！
这在我的笔记本电脑上花了 3.95 秒：（洗牌很关键）

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>

int main()
{
    using namespace std;
    srand((unsigned)time(NULL));
    clock_t start;
    {
        vector<string> v(400000);
        for (size_t i = 0; i < v.size(); i++)
        {
            v[i].resize(16 + rand() % 32);  // some variation
        }

        // shuffle
        for (size_t i = 0; i < (size_t)pow((double)v.size(), 1.15); i++)
        {
            size_t j = rand() * (RAND_MAX + 1) + rand();
            swap(v[i % v.size()], v[j % v.size()]);
        }
        
        printf("Going out of scope...\n"); fflush(stdout);
        start = clock();
    }
    clock_t end = clock();
    printf("%u ms\n", (end - start) * 1000 / CLOCKS_PER_SEC);
    return 0;
}

在我看来，这个程序在内部使用了一些 O(n 2 ) 算法，无论是在 Visual C++ 中还是在 Windows 中。不知道发生了什么，但很有趣……

4

3 回答 3

8

将自定义分配器与解除分配一起使用。

于 2012-07-18T01:08:47.343 回答
5

好吧，既然没人知道...

这是因为我的系统中打开了堆尾检查。一旦我删除它，代码很快就完成了。

于 2012-07-27T07:05:09.363 回答
0

为什么不动态创建向量本身，以便可以使用引用计数智能指针对其进行管理。然后，您可以确保最后一次引用它的线程不是 UI 线程，因此当 UI 线程超出范围时，它不是执行处理的线程。

您甚至可以操纵执行处理的线程的优先级，使其较低并且不会严重影响其余线程 - 它会确保 UI 线程被安排在较低优先级线程的前面。

注意：我从未尝试过，但我不明白为什么它不起作用 - 但花时间在上面，风险自负！:)

于 2012-07-18T01:40:20.870 回答