奇怪的算法性能
Strange algorithm performance
对于上下文，我编写了这个算法来获取任何字符串的唯一子字符串的数量。它为字符串构建后缀树，计算它包含的节点，并将 returns 作为答案。我想解决的问题需要一个 O(n) 算法，所以这个问题只是关于这段代码的行为方式，而不是关于它的工作有多糟糕。
struct node{
char value = ' ';
vector<node*> children;
~node()
{
for (node* child: children)
{
delete child;
}
}
};
int numberOfUniqueSubstrings(string aString, node*& root)
{
root = new node();
int substrings = 0;
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
node* currentNode = root;
char indexToNext = 0;
for (int j = 0; j < currentNode->children.size(); ++j)
{
if (currentNode->children[j]->value == tmp[indexToNext])
{
currentNode = currentNode->children[j];
j = -1;
indexToNext++;
}
}
for (int j = indexToNext; j < tmp.size(); ++j)
{
node* theNewNode = new node;
theNewNode->value = tmp[j];
currentNode->children.push_back(theNewNode);
currentNode = theNewNode;
substrings++;
}
}
return substrings;
}
我决定对这个算法进行基准测试，为此我简单地循环了一个大字符串，每次迭代都取一个更大的子字符串，调用 numberOfUniqueSusbstrings 测量结束所需的时间。
我以八度为单位绘制它，这就是我得到的（x 是字符串大小，y 是以微秒为单位的时间）
我首先认为问题出在输入字符串上，但它只是我从一本书中得到的一个字母数字字符串（任何其他文本的行为都一样奇怪）。
还尝试对具有相同参数的函数的多次调用进行平均，结果几乎相同。
这是用 g++ problem.cpp -std=c++14 -O3 编译的，但似乎在 -O2 和 -O0 上做同样的事情。
编辑：
在@interjay 的回答之后，我尝试只做将函数保留为：
int numberOfUniqueSubstrings(string aString, node*& root)
{
root = new node();
int substrings = 0;
for (int i = 0; i < aString.size(); ++i)
{
node* currentNode = root;
char indexToNext = i;
for (int j = 0; j < currentNode->children.size(); ++j)
{
if (currentNode->children[j]->value == aString[indexToNext])
{
currentNode = currentNode->children[j];
j = -1;
indexToNext++;
}
}
for (int j = indexToNext; j < aString.size(); ++j)
{
node* theNewNode = new node;
theNewNode->value = aString[j];
currentNode->children.push_back(theNewNode);
currentNode = theNewNode;
substrings++;
}
}
return substrings;
}
它确实使速度更快了一点。但同样奇怪的是我绘制了这个：
x = 1000 发生了一些事情，我不知道它可能是什么。
另一个好的测量图：
我现在 运行 gprof 用于大小为 999 的字符串：
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
100.15 0.02 0.02 974 20.56 20.56 node::~node()
0.00 0.02 0.00 498688 0.00 0.00 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
0.00 0.02 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z7imprimePK4node
0.00 0.02 0.00 1 0.00 0.00 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&)
^L
Call graph
granularity: each sample hit covers 2 byte(s) for 49.93% of 0.02 seconds
index % time self children called name
54285 node::~node() [1]
0.02 0.00 974/974 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[1] 100.0 0.02 0.00 974+54285 node::~node() [1]
54285 node::~node() [1]
-----------------------------------------------
<spontaneous>
[2] 100.0 0.00 0.02 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
0.02 0.00 974/974 node::~node() [1]
0.00 0.00 1/1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
-----------------------------------------------
0.00 0.00 498688/498688 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
[10] 0.0 0.00 0.00 498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [21]
[11] 0.0 0.00 0.00 1 _GLOBAL__sub_I__Z7imprimePK4node [11]
-----------------------------------------------
0.00 0.00 1/1 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[12] 0.0 0.00 0.00 1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
0.00 0.00 498688/498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
对于大小为 1001 的字符串：
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
100.15 0.02 0.02 974 20.56 20.56 node::~node()
0.00 0.02 0.00 498688 0.00 0.00 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
0.00 0.02 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z7imprimePK4node
0.00 0.02 0.00 1 0.00 0.00 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&)
Call graph
granularity: each sample hit covers 2 byte(s) for 49.93% of 0.02 seconds
index % time self children called name
54285 node::~node() [1]
0.02 0.00 974/974 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[1] 100.0 0.02 0.00 974+54285 node::~node() [1]
54285 node::~node() [1]
-----------------------------------------------
<spontaneous>
[2] 100.0 0.00 0.02 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
0.02 0.00 974/974 node::~node() [1]
0.00 0.00 1/1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
-----------------------------------------------
0.00 0.00 498688/498688 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
[10] 0.0 0.00 0.00 498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [21]
[11] 0.0 0.00 0.00 1 _GLOBAL__sub_I__Z7imprimePK4node [11]
-----------------------------------------------
0.00 0.00 1/1 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[12] 0.0 0.00 0.00 1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
0.00 0.00 498688/498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
Index by function name
[11] _GLOBAL__sub_I__Z7imprimePK4node [1] node::~node()
[12] numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [10] void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
然而，运行分析器似乎消除了这种影响，并且两种情况下的时间几乎相同。
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
这已经使您的算法 O(n^2) 或更糟。对 substr 的调用平均创建一个 n/2 大小的子字符串，因此它需要 O(n)，而你调用它 n 次。
看来您实际上并不需要 tmp 字符串，因为您只是从中读取。相反，从原始字符串读取但相应地更改索引。
for (int j = indexToNext; j < tmp.size(); ++j) 循环可能还会给你的算法 O(n^2) 总时间（我说 "probably" 因为它取决于 indexToNext 的计算值，但是从用随机字符串测试它似乎成立）。是运行O(n)次，每次都需要O(n)次迭代。
我怀疑 malloc 多于 string 或 vector。它完全有可能以不同方式处理 < 1000 字节和 > 1000 字节。合并释放的块可能很昂贵。它可能会避免尝试合并较大的块（即通过将它们维护在池中）。但这真的只是一个猜测。你为什么不试试分析器并获得一些真实数据呢？ gprof 易于使用。
This article 在 glibc malloc 上有一些有趣的细节。如果那是您程序的幕后黑手，那么那里描述的 bin 类型之间的差异可能会起作用。事实上，块被释放到偶尔重组的 "unsorted bin" 。尖峰可能是这些重组以防止堆增长。如果该理论是正确的，那么平滑可能是将堆区域扩大到重组成本不那么高的大小的结果。
但同样，这都是猜想，可以通过 运行 探查器查看时间在 <1000 与 >1000 时的去向。
大多数人的工作假设似乎是某种神奇的数字被硬编码到库中，导致性能在 999-1000 左右的阶段 t运行sition（LSerni 除外，他制作了先见之明，可能存在 多个 个幻数）。
我将尝试系统地探讨这个假设和下面的其他一些假设（源代码在这个答案的末尾可用）。
然后我 运行 我的代码看看我是否可以在我的 Intel(R) Core(TM) i5 CPU M480，Linux 4.8.0-34 上复制你的结果-通用机器，使用 G++ 6.2.0-5ubuntu2 作为我的编译器 -O3 优化。
果然，从 999-1000 有一个神奇的下降（并且，另一个接近 1600）：
请注意，我的 t运行s-1000 数据集不像你的那么干净：这可能是因为我在我的机器的后台玩一些其他东西，而你有一个更安静的测试环境。
我的下一个问题是：这个神奇的 1000 数字在不同环境之间是否稳定？
所以我在 Intel(R) Xeon(R) CPU E5-2680 v3, Linux 2.6.32-642.6.1.el6 上尝试了 运行ning 代码.x86_64 机器，使用 G++ 4.9.2。而且，不出所料，幻数不同，出现在 975-976:
这告诉我们，如果有一个幻数，它会在不同版本之间发生变化。由于一些原因，这降低了我对幻数理论的信心。 (a) 它改变了。 (b) 1000+24 字节的开销是魔术的一个很好的候选者。 975+49 字节更少。 (c) 第一个环境在较慢的处理器上有更好的软件，但第一个环境显示我认为更差的性能：等到 1000 来加速。这似乎是一种倒退。
我尝试了不同的测试：运行使用不同的 运行dom 输入数据连接程序。这给出了这个结果：
上图中的重点是999-1000的跌幅并没有那么特别。它看起来像之前的许多下降：速度缓慢下降，然后急剧提高。还值得注意的是，之前的许多水滴都没有对齐。
这向我暗示这是一种 input-dependent 行为并且 运行 之间存在相关性。因此，我想知道如果我通过 运行domizing 它们的顺序来减少 运行 之间的相关性会发生什么。这给了：
999-1000 左右仍有事情发生：
让我们放大更多:
运行 在速度较快的计算机上使用较旧的软件得到类似的结果：
缩放：
由于 运行domizing 考虑不同长度的字符串的顺序基本上消除了 运行 之间的缓慢 build-up（上述相关性），这表明您的现象“看见”需要某种全局状态。因此，C++ string/vector 不能作为解释。因此，malloc、"the OS" 或架构限制必须是解释。
请注意，当长度顺序为 运行domized 时，代码 运行 会变得更慢而不是更快。在我看来，这与超出某种缓存大小是一致的，但信号中的噪声以及此 post 中的第一个图也表明可能存在内存碎片。因此，我决定在每次 运行 重新启动程序之前确保一个新的堆。结果如下：
现在我们看到没有更多的中断或跳跃。这表明 cache-size 不是问题，而是观察到的行为与程序的整体内存使用有关。
另一个反对缓存效果的论据如下。两台机器都有 32kB 和 256kB L1 和 L2 缓存，所以它们的缓存性能应该差不多。我的慢机器有一个 3,072kB L3 缓存。如果假设每次分配一个 4kB 页面，则 1000 个节点会分配 4,000kB，这接近缓存大小。然而，快速机器有一个 30,720kB 的 L3 高速缓存，并在 975 处显示中断。如果该现象是高速缓存的影响，那么中断（如果有的话）会在稍后出现。因此，我很确定缓存在这里不起作用。
唯一剩下的罪魁祸首是 malloc。
为什么会这样？我不确定。不过，作为程序员，我无所谓，如下。
对此可能有一个解释，但它的水平太深以至于无法改变或真正担心。我可以做一些奇特的事情来修复它，但这需要考虑它黑暗的软肋中某处发生的事情。我们使用 higher-level 语言，如 C++，专门避免弄乱这些细节，除非我们 真的 必须这样做。
我的结果表明我们没有o 在这种情况下。 (a) 最后一张图告诉我们，任何独立的 运行 代码都可能表现出 near-optimal 行为，(b) 运行domizing sequential 运行s 可以提高性能， (c) 效率损失大约为百分之一秒，这是完全可以接受的，除非您正在处理大量 数据量。
源代码如下。请注意，代码将您的版本的 char indexToNext 更改为 int indexToNext，修复了可能的整数溢出问题。测试 我们避免复制字符串实际上会导致更差的性能。
#include <string>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
struct profiler
{
std::string name;
std::chrono::high_resolution_clock::time_point p;
profiler(std::string const &n) :
name(n), p(std::chrono::high_resolution_clock::now()) { }
~profiler()
{
using dura = std::chrono::duration<double>;
auto d = std::chrono::high_resolution_clock::now() - p;
std::cout //<< name << ": "
<< std::chrono::duration_cast<dura>(d).count()
<< std::endl;
}
};
#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)
struct node {
char value = ' ';
std::vector<node*> children;
~node(){
for (node* child: children)
delete child;
}
};
int numberOfUniqueSubstrings(const std::string aString, node*& root)
{
root = new node();
int substrings = 0;
for (int i = 0; i < aString.size(); ++i)
{
node* currentNode = root;
int indexToNext = i;
for (int j = 0; j < currentNode->children.size(); ++j)
{
if (currentNode->children[j]->value == aString[indexToNext])
{
currentNode = currentNode->children[j];
j = -1;
indexToNext++;
}
}
for (int j = indexToNext; j < aString.size(); ++j)
{
node* theNewNode = new node;
theNewNode->value = aString[j];
currentNode->children.push_back(theNewNode);
currentNode = theNewNode;
substrings++;
}
}
return substrings;
}
int main(int argc, char **argv){
const int MAX_LEN = 1300;
if(argc==1){
std::cerr<<"Syntax: "<<argv[0]<<"<SEED> [LENGTH]"<<std::endl;
std::cerr<<"Seed of -1 implies all lengths should be explore and input randomized from time."<<std::endl;
std::cerr<<"Positive seed sets the seed and explores a single input of LENGTH"<<std::endl;
return -1;
}
int seed = std::stoi(argv[1]);
if(seed==-1)
srand(time(NULL));
else
srand(seed);
//Generate a random string of the appropriate length
std::string a;
for(int fill=0;fill<MAX_LEN;fill++)
a.push_back('a'+rand()%26);
//Generate a list of lengths of strings to experiment with
std::vector<int> lengths_to_try;
if(seed==-1){
for(int i=1;i<MAX_LEN;i++)
lengths_to_try.push_back(i);
} else {
lengths_to_try.push_back(std::stoi(argv[2]));
}
//Enable this line to randomly sort the strings
std::random_shuffle(lengths_to_try.begin(),lengths_to_try.end());
for(auto len: lengths_to_try){
std::string test(a.begin(),a.begin()+len);
std::cout<<len<<" ";
{
PROFILE_BLOCK("Some time");
node *n;
int c = numberOfUniqueSubstrings(test,n);
delete n;
}
}
}
substr 是一个 "constant"
OP的原始代码包括以下内容：
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
这里的substr操作在字符串长度上占用了O(n)时间。在中争论说这个O(n)操作导致OP的原始代码性能不佳。
我不同意这个评价。由于缓存和 SIMD 操作，CPUs 可以读取和复制最多 64 字节（或更多！）的块中的数据。因此，内存分配的成本可以支配复制字符串的成本。因此，对于 OP 的输入大小，substr 操作更像是一个昂贵的常数，而不是一个额外的循环。
这可以通过编译代码的测试来证明，例如g++ temp.cpp -O3 --std=c++14 -g 和配置文件，例如sudo operf ./a.out -1。生成的 time-use 配置文件如下所示：
25.24% a.out a.out [.] _ZN4nodeD2Ev #Node destruction
24.77% a.out libc-2.24.so [.] _int_malloc
13.93% a.out libc-2.24.so [.] malloc_consolidate
11.06% a.out libc-2.24.so [.] _int_free
7.39% a.out libc-2.24.so [.] malloc
5.62% a.out libc-2.24.so [.] free
3.92% a.out a.out [.] _ZNSt6vectorIP4nodeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_
2.68% a.out a.out [.]
8.07% OTHER STUFF
从中可以明显看出内存管理在 run-time.
中占主导地位
对于上下文，我编写了这个算法来获取任何字符串的唯一子字符串的数量。它为字符串构建后缀树，计算它包含的节点，并将 returns 作为答案。我想解决的问题需要一个 O(n) 算法，所以这个问题只是关于这段代码的行为方式，而不是关于它的工作有多糟糕。
struct node{
char value = ' ';
vector<node*> children;
~node()
{
for (node* child: children)
{
delete child;
}
}
};
int numberOfUniqueSubstrings(string aString, node*& root)
{
root = new node();
int substrings = 0;
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
node* currentNode = root;
char indexToNext = 0;
for (int j = 0; j < currentNode->children.size(); ++j)
{
if (currentNode->children[j]->value == tmp[indexToNext])
{
currentNode = currentNode->children[j];
j = -1;
indexToNext++;
}
}
for (int j = indexToNext; j < tmp.size(); ++j)
{
node* theNewNode = new node;
theNewNode->value = tmp[j];
currentNode->children.push_back(theNewNode);
currentNode = theNewNode;
substrings++;
}
}
return substrings;
}
我决定对这个算法进行基准测试，为此我简单地循环了一个大字符串，每次迭代都取一个更大的子字符串，调用 numberOfUniqueSusbstrings 测量结束所需的时间。
我以八度为单位绘制它，这就是我得到的（x 是字符串大小，y 是以微秒为单位的时间）
我首先认为问题出在输入字符串上，但它只是我从一本书中得到的一个字母数字字符串（任何其他文本的行为都一样奇怪）。
还尝试对具有相同参数的函数的多次调用进行平均，结果几乎相同。
这是用 g++ problem.cpp -std=c++14 -O3 编译的，但似乎在 -O2 和 -O0 上做同样的事情。
编辑： 在@interjay 的回答之后，我尝试只做将函数保留为：
int numberOfUniqueSubstrings(string aString, node*& root)
{
root = new node();
int substrings = 0;
for (int i = 0; i < aString.size(); ++i)
{
node* currentNode = root;
char indexToNext = i;
for (int j = 0; j < currentNode->children.size(); ++j)
{
if (currentNode->children[j]->value == aString[indexToNext])
{
currentNode = currentNode->children[j];
j = -1;
indexToNext++;
}
}
for (int j = indexToNext; j < aString.size(); ++j)
{
node* theNewNode = new node;
theNewNode->value = aString[j];
currentNode->children.push_back(theNewNode);
currentNode = theNewNode;
substrings++;
}
}
return substrings;
}
它确实使速度更快了一点。但同样奇怪的是我绘制了这个：
x = 1000 发生了一些事情，我不知道它可能是什么。
另一个好的测量图：
我现在 运行 gprof 用于大小为 999 的字符串：
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
100.15 0.02 0.02 974 20.56 20.56 node::~node()
0.00 0.02 0.00 498688 0.00 0.00 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
0.00 0.02 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z7imprimePK4node
0.00 0.02 0.00 1 0.00 0.00 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&)
^L
Call graph
granularity: each sample hit covers 2 byte(s) for 49.93% of 0.02 seconds
index % time self children called name
54285 node::~node() [1]
0.02 0.00 974/974 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[1] 100.0 0.02 0.00 974+54285 node::~node() [1]
54285 node::~node() [1]
-----------------------------------------------
<spontaneous>
[2] 100.0 0.00 0.02 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
0.02 0.00 974/974 node::~node() [1]
0.00 0.00 1/1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
-----------------------------------------------
0.00 0.00 498688/498688 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
[10] 0.0 0.00 0.00 498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [21]
[11] 0.0 0.00 0.00 1 _GLOBAL__sub_I__Z7imprimePK4node [11]
-----------------------------------------------
0.00 0.00 1/1 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[12] 0.0 0.00 0.00 1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
0.00 0.00 498688/498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
对于大小为 1001 的字符串：
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
100.15 0.02 0.02 974 20.56 20.56 node::~node()
0.00 0.02 0.00 498688 0.00 0.00 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
0.00 0.02 0.00 1 0.00 0.00 _GLOBAL__sub_I__Z7imprimePK4node
0.00 0.02 0.00 1 0.00 0.00 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&)
Call graph
granularity: each sample hit covers 2 byte(s) for 49.93% of 0.02 seconds
index % time self children called name
54285 node::~node() [1]
0.02 0.00 974/974 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[1] 100.0 0.02 0.00 974+54285 node::~node() [1]
54285 node::~node() [1]
-----------------------------------------------
<spontaneous>
[2] 100.0 0.00 0.02 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
0.02 0.00 974/974 node::~node() [1]
0.00 0.00 1/1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
-----------------------------------------------
0.00 0.00 498688/498688 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
[10] 0.0 0.00 0.00 498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
0.00 0.00 1/1 __libc_csu_init [21]
[11] 0.0 0.00 0.00 1 _GLOBAL__sub_I__Z7imprimePK4node [11]
-----------------------------------------------
0.00 0.00 1/1 test(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >) [2]
[12] 0.0 0.00 0.00 1 numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [12]
0.00 0.00 498688/498688 void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&) [10]
-----------------------------------------------
Index by function name
[11] _GLOBAL__sub_I__Z7imprimePK4node [1] node::~node()
[12] numberOfUniqueSubstrings(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, node*&) [10] void std::vector<node*, std::allocator<node*> >::_M_emplace_back_aux<node* const&>(node* const&)
然而，运行分析器似乎消除了这种影响，并且两种情况下的时间几乎相同。
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
这已经使您的算法 O(n^2) 或更糟。对 substr 的调用平均创建一个 n/2 大小的子字符串，因此它需要 O(n)，而你调用它 n 次。
看来您实际上并不需要 tmp 字符串，因为您只是从中读取。相反，从原始字符串读取但相应地更改索引。
for (int j = indexToNext; j < tmp.size(); ++j) 循环可能还会给你的算法 O(n^2) 总时间（我说 "probably" 因为它取决于 indexToNext 的计算值，但是从用随机字符串测试它似乎成立）。是运行O(n)次，每次都需要O(n)次迭代。
我怀疑 malloc 多于 string 或 vector。它完全有可能以不同方式处理 < 1000 字节和 > 1000 字节。合并释放的块可能很昂贵。它可能会避免尝试合并较大的块（即通过将它们维护在池中）。但这真的只是一个猜测。你为什么不试试分析器并获得一些真实数据呢？ gprof 易于使用。
This article 在 glibc malloc 上有一些有趣的细节。如果那是您程序的幕后黑手，那么那里描述的 bin 类型之间的差异可能会起作用。事实上，块被释放到偶尔重组的 "unsorted bin" 。尖峰可能是这些重组以防止堆增长。如果该理论是正确的，那么平滑可能是将堆区域扩大到重组成本不那么高的大小的结果。
但同样，这都是猜想，可以通过 运行 探查器查看时间在 <1000 与 >1000 时的去向。
大多数人的工作假设似乎是某种神奇的数字被硬编码到库中，导致性能在 999-1000 左右的阶段 t运行sition（LSerni 除外，他制作了先见之明，可能存在 多个 个幻数）。
我将尝试系统地探讨这个假设和下面的其他一些假设（源代码在这个答案的末尾可用）。
然后我 运行 我的代码看看我是否可以在我的 Intel(R) Core(TM) i5 CPU M480，Linux 4.8.0-34 上复制你的结果-通用机器，使用 G++ 6.2.0-5ubuntu2 作为我的编译器 -O3 优化。
果然，从 999-1000 有一个神奇的下降（并且，另一个接近 1600）：
请注意，我的 t运行s-1000 数据集不像你的那么干净：这可能是因为我在我的机器的后台玩一些其他东西，而你有一个更安静的测试环境。
我的下一个问题是：这个神奇的 1000 数字在不同环境之间是否稳定？
所以我在 Intel(R) Xeon(R) CPU E5-2680 v3, Linux 2.6.32-642.6.1.el6 上尝试了 运行ning 代码.x86_64 机器，使用 G++ 4.9.2。而且，不出所料，幻数不同，出现在 975-976:
这告诉我们，如果有一个幻数，它会在不同版本之间发生变化。由于一些原因，这降低了我对幻数理论的信心。 (a) 它改变了。 (b) 1000+24 字节的开销是魔术的一个很好的候选者。 975+49 字节更少。 (c) 第一个环境在较慢的处理器上有更好的软件，但第一个环境显示我认为更差的性能：等到 1000 来加速。这似乎是一种倒退。
我尝试了不同的测试：运行使用不同的 运行dom 输入数据连接程序。这给出了这个结果：
上图中的重点是999-1000的跌幅并没有那么特别。它看起来像之前的许多下降：速度缓慢下降，然后急剧提高。还值得注意的是，之前的许多水滴都没有对齐。
这向我暗示这是一种 input-dependent 行为并且 运行 之间存在相关性。因此，我想知道如果我通过 运行domizing 它们的顺序来减少 运行 之间的相关性会发生什么。这给了：
999-1000 左右仍有事情发生：
让我们放大更多:
运行 在速度较快的计算机上使用较旧的软件得到类似的结果：
缩放：
由于 运行domizing 考虑不同长度的字符串的顺序基本上消除了 运行 之间的缓慢 build-up（上述相关性），这表明您的现象“看见”需要某种全局状态。因此，C++ string/vector 不能作为解释。因此，malloc、"the OS" 或架构限制必须是解释。
请注意，当长度顺序为 运行domized 时，代码 运行 会变得更慢而不是更快。在我看来，这与超出某种缓存大小是一致的，但信号中的噪声以及此 post 中的第一个图也表明可能存在内存碎片。因此，我决定在每次 运行 重新启动程序之前确保一个新的堆。结果如下：
现在我们看到没有更多的中断或跳跃。这表明 cache-size 不是问题，而是观察到的行为与程序的整体内存使用有关。
另一个反对缓存效果的论据如下。两台机器都有 32kB 和 256kB L1 和 L2 缓存，所以它们的缓存性能应该差不多。我的慢机器有一个 3,072kB L3 缓存。如果假设每次分配一个 4kB 页面，则 1000 个节点会分配 4,000kB，这接近缓存大小。然而，快速机器有一个 30,720kB 的 L3 高速缓存，并在 975 处显示中断。如果该现象是高速缓存的影响，那么中断（如果有的话）会在稍后出现。因此，我很确定缓存在这里不起作用。
唯一剩下的罪魁祸首是 malloc。
为什么会这样？我不确定。不过，作为程序员，我无所谓，如下。
对此可能有一个解释，但它的水平太深以至于无法改变或真正担心。我可以做一些奇特的事情来修复它，但这需要考虑它黑暗的软肋中某处发生的事情。我们使用 higher-level 语言，如 C++，专门避免弄乱这些细节，除非我们 真的 必须这样做。
我的结果表明我们没有o 在这种情况下。 (a) 最后一张图告诉我们，任何独立的 运行 代码都可能表现出 near-optimal 行为，(b) 运行domizing sequential 运行s 可以提高性能， (c) 效率损失大约为百分之一秒，这是完全可以接受的，除非您正在处理大量 数据量。
源代码如下。请注意，代码将您的版本的 char indexToNext 更改为 int indexToNext，修复了可能的整数溢出问题。测试
#include <string>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
struct profiler
{
std::string name;
std::chrono::high_resolution_clock::time_point p;
profiler(std::string const &n) :
name(n), p(std::chrono::high_resolution_clock::now()) { }
~profiler()
{
using dura = std::chrono::duration<double>;
auto d = std::chrono::high_resolution_clock::now() - p;
std::cout //<< name << ": "
<< std::chrono::duration_cast<dura>(d).count()
<< std::endl;
}
};
#define PROFILE_BLOCK(pbn) profiler _pfinstance(pbn)
struct node {
char value = ' ';
std::vector<node*> children;
~node(){
for (node* child: children)
delete child;
}
};
int numberOfUniqueSubstrings(const std::string aString, node*& root)
{
root = new node();
int substrings = 0;
for (int i = 0; i < aString.size(); ++i)
{
node* currentNode = root;
int indexToNext = i;
for (int j = 0; j < currentNode->children.size(); ++j)
{
if (currentNode->children[j]->value == aString[indexToNext])
{
currentNode = currentNode->children[j];
j = -1;
indexToNext++;
}
}
for (int j = indexToNext; j < aString.size(); ++j)
{
node* theNewNode = new node;
theNewNode->value = aString[j];
currentNode->children.push_back(theNewNode);
currentNode = theNewNode;
substrings++;
}
}
return substrings;
}
int main(int argc, char **argv){
const int MAX_LEN = 1300;
if(argc==1){
std::cerr<<"Syntax: "<<argv[0]<<"<SEED> [LENGTH]"<<std::endl;
std::cerr<<"Seed of -1 implies all lengths should be explore and input randomized from time."<<std::endl;
std::cerr<<"Positive seed sets the seed and explores a single input of LENGTH"<<std::endl;
return -1;
}
int seed = std::stoi(argv[1]);
if(seed==-1)
srand(time(NULL));
else
srand(seed);
//Generate a random string of the appropriate length
std::string a;
for(int fill=0;fill<MAX_LEN;fill++)
a.push_back('a'+rand()%26);
//Generate a list of lengths of strings to experiment with
std::vector<int> lengths_to_try;
if(seed==-1){
for(int i=1;i<MAX_LEN;i++)
lengths_to_try.push_back(i);
} else {
lengths_to_try.push_back(std::stoi(argv[2]));
}
//Enable this line to randomly sort the strings
std::random_shuffle(lengths_to_try.begin(),lengths_to_try.end());
for(auto len: lengths_to_try){
std::string test(a.begin(),a.begin()+len);
std::cout<<len<<" ";
{
PROFILE_BLOCK("Some time");
node *n;
int c = numberOfUniqueSubstrings(test,n);
delete n;
}
}
}
substr 是一个 "constant"
OP的原始代码包括以下内容：
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
这里的substr操作在字符串长度上占用了O(n)时间。在O(n)操作导致OP的原始代码性能不佳。
我不同意这个评价。由于缓存和 SIMD 操作，CPUs 可以读取和复制最多 64 字节（或更多！）的块中的数据。因此，内存分配的成本可以支配复制字符串的成本。因此，对于 OP 的输入大小，substr 操作更像是一个昂贵的常数，而不是一个额外的循环。
这可以通过编译代码的测试来证明，例如g++ temp.cpp -O3 --std=c++14 -g 和配置文件，例如sudo operf ./a.out -1。生成的 time-use 配置文件如下所示：
25.24% a.out a.out [.] _ZN4nodeD2Ev #Node destruction
24.77% a.out libc-2.24.so [.] _int_malloc
13.93% a.out libc-2.24.so [.] malloc_consolidate
11.06% a.out libc-2.24.so [.] _int_free
7.39% a.out libc-2.24.so [.] malloc
5.62% a.out libc-2.24.so [.] free
3.92% a.out a.out [.] _ZNSt6vectorIP4nodeSaIS1_EE19_M_emplace_back_auxIJRKS1_EEEvDpOT_
2.68% a.out a.out [.]
8.07% OTHER STUFF
从中可以明显看出内存管理在 run-time.
中占主导地位