奇怪的算法性能
mjg*_*ndo 20 c++ string algorithm performance suffix-tree
对于上下文,我编写了这个算法来获取任何字符串的唯一子串的数量.它为计算其包含的节点的字符串构建后缀树,并将其作为答案返回.我想要解决的问题需要一个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&)
然而,似乎运行探查器会消除效果,并且两种情况下的时间几乎相同.
Ric*_*ard 11
大多数人的工作假设似乎是某些神奇的数字被硬编码到库中,导致999-1000左右的性能发生相变(LSerni除外,它使得有先见之明的观察结果可能存在多个幻数).
我将尝试系统地探讨这个以及下面的一些其他假设(源代码可在本答案结尾处获得).
然后我运行我的代码,看看我是否可以在我的英特尔(R)Core(TM)i5 CPU M480,Linux 4.8.0-34通用机器上复制您的结果,使用G ++ 6.2.0-5ubuntu2作为我的编译器进行-O3优化.
果然,从999-1000(以及1600附近的另一个)有一个神奇的下降:
请注意,我的trans-1000数据集并不像你的那样干净:这可能是因为我在机器的后台玩了一些其他的东西,而你有一个更安静的测试环境.
我的下一个问题是:这个神奇的1000号码在环境之间是否稳定？
所以我尝试使用G ++ 4.9.2在Intel(R)Xeon(R)CPU E5-2680 v3,Linux 2.6.32-642.6.1.el6.x86_64机器上运行代码.而且,毫不奇怪,神奇的数字是不同的,发生在975-976:
这告诉我们,如果有一个幻数,它会在不同版本之间发生变化.由于一些原因,这降低了我对幻数理论的信心.(a)它改变了.(b)1000 + 24字节的开销是魔术的一个很好的候选者.975 + 49字节不那么重要.(c)第一个环境在较慢的处理器上有更好的软件,但第一个环境显示了我认为性能更差的东西:等到1000以加快速度.这似乎是一种回归.
我尝试了另一种测试:使用不同的随机输入数据运行程序.这给出了这个结果:
上图中的重点是999-1000下降并不是那么特别.它看起来像之前的许多下降:速度缓慢下降,然后急剧改善.同样值得注意的是,之前的许多下降都没有对齐.
这告诉我,这是一个依赖于输入的行为,并且运行之间存在相关性.因此,我想知道如果我通过随机化他们的顺序来减少运行之间的相关性会发生什么.这给了:
999-1000左右仍然发生了一些事情:
让我们放大更是:
使用旧版软件在速度更快的计算机上运行此操作会产生类似的结果:
缩放:
由于随机化考虑了不同长度的字符串的顺序基本上消除了运行之间的缓慢积累(上述相关性),这表明您所看到的现象需要某种全局状态.因此,C++字符串/向量不能解释.因此,malloc,"OS"或架构约束必须是解释.
请注意,当长度的顺序随机化时,代码运行速度较慢而不是更快.在我看来,这与超出某种高速缓存大小是一致的,但信号中的噪声加上本文中的第一个图也表明可能存在内存碎片.因此,我决定在每次运行之前重新启动程序以确保新堆.结果如下:
现在我们看到没有更多的休息或跳跃.这表明缓存大小不是问题,而是观察到的行为与程序的整体内存使用量有关.
反对缓存效果的另一个论点如下.两台机器都有32kB和256kB L1和L2缓存,因此它们的缓存性能应该相似.我的慢速机器有一个3,072kB的L3缓存.如果假设每个分配4kB页面,则1000个节点分配4,000kB,这接近于高速缓存大小.然而,这台快速机器有一个30,720kB的三级缓存,在975处有一个突破.如果这种现象是一种缓存效果,你可能会期待稍后的突破.因此,我很确定缓存在这里不起作用.
唯一剩下的罪魁祸首是malloc.
为什么会这样？我不确定.但是,作为程序员,我不在乎,如下.
可能有一个解释,但它的水平太深,无法改变或真正担心.我可以做一些异国情调来修复它,但这需要考虑在其黑暗的下腹部某处发生了什么.我们使用像C++这样的高级语言来避免弄乱这些细节,除非我们真的必须这样做.
我的结果说我们不必在这种情况下.(a)最后一个图表告诉我们,任何独立的代码运行都可能表现出接近最优的行为,(b)随机化顺序运行可以提高性能水平,(c)效率损失大约为百分之一一秒钟,除非您处理大量数据,否则完全可以接受.
源代码如下.请注意,代码会将您的版本更改char indexToNext为int indexToNext,从而修复可能的整数溢出问题.测试interjay的建议,我们避免制作字符串的副本实际上导致更差的性能.
#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 是一个"常数"
OP的原始代码包括以下内容:
for (int i = 0; i < aString.size(); ++i)
{
string tmp = aString.substr(i, aString.size());
substr这里的操作需要O(n)时间在字符串的长度.在下面的答案中,有人认为这种O(n)操作会导致OP原始代码的性能不佳.
我不同意这种评估.由于缓存和SIMD操作,CPU可以以最多64字节(或更多!)的块来读取和复制数据.因此,内存分配的成本可以支配复制字符串的成本.因此,对于OP的输入大小,substr操作更像是一个昂贵的常量,而不是一个额外的循环.
这可以通过使用例如编译代码来进行测试来证明,例如g++ temp.cpp -O3 --std=c++14 -g和sudo operf ./a.out -1.生成的时间使用配置文件如下所示:
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
很明显,内存管理在运行时占主导地位.
int*_*jay 10
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)总时间(我说"可能",因为它依赖于计算值indexToNext,但是从随机字符串测试它似乎是成立的).它运行O(n)次,每次将进行O(n)次迭代.
- 你应该添加一个关于`std :: string_view`的部分,这将允许他操作子字符串而不需要复制. (5认同)
| 归档时间： |
|
| 查看次数： |
1225 次 |
| 最近记录： |