＋设为首页 ＋添加到收藏夹
近日做了一个类似词典检索的程序，使我对STL的效率产生了疑问。
有这样一个7万多行的文件，文件的每一行的开头是一个汉语单词，长度不确定，后面跟着这个汉语词的一些特征代码，每个代码都由是四个英文字母或数字组成。我的任务就是计算两个汉语单词的特征代码的相似程度。
因为我做的函数需要整个工程中频繁调用很多次，所以速度很重要。 于是我需要读入这个7万多行的文件，并以一种高效率的格式来存储。
最开始的时候，我用了map，用汉语单词做索引，键值是一个vector<string>。vector里面存的是这个汉语词的特征代码。而文件的读入，我用了ofstream的getline。这样做的结果是，查找效率挺高，可是读入这个文件，把特征码按空格分开，存入vector，再存入map中，这个初始化的过程竟然用了7秒的时间！这是不可容忍的！
后来我做了很多尝试，比如map中不存放vector，而存放vector指针，可是效率始终没有太大的改变。到了最后，我的最终方案是，放弃了map，选择了struct！放弃了vector<string>，选择了char*！放弃了ofstream，选择了fread！最后我自己做了折半查找！
这样做的结果是，查找效率没有降低，而初始化的时间还不到一秒钟！！！！
这个任务我完成了，可是我十分的迷惑。是不是STL提供的功能太多了，考虑的东西太多了，他的效率却降低了！但是，如果他的效率如此之低的话，我们在什么样的情况下，才应该使用它呢？
欢迎各位讨论！发言就有分！
再详细的描述一下你的过程，好么？
或者可以的话，帖出关键的代码，如何？
好像stl为了实现统一的接口是放弃了一些效率上的优势，但是这应该不影响stl本身，使用的时候选择合适的模板，一样也能达到较高的效率
是你用的有问题.它的效率很高
对，看看代码再说
可能是不断的内存重新分配造成的吧，
因为VECTOR的动态内存分配是先分配一块“足够大”的内存，而你想要的显然比缺省的要大很多，因此可能会出现不停的重新分配，COPY的问题。
好像有个初始化的vector构造可以定义一个预先分配的内存大小，可以把那个值设一下
最主要的 map<string,vector<string> > cilin_map;
需要cilin_map.reserve();
我觉得可以把所有的键值都放在一个string里面，不必采用vector。这样应该可以节省很多开销，至于把
那些单独的键值分离出来，可以在比较的时候再分离。
#include <string>
#include <map>
#include <fstream>
#include <iostream>
using namespace std;
void CCilin(const string&,map<string,string>&);
int main()
{
map<string,string> cilin_map;
cout<<"Enter FileName:";
string FileName;
cin>>FileName;
cout<<"Begin!"<<endl;
CCilin(FileName,cilin_map);
cout<<"Finish!"<<endl;
}
void CCilin(const string& Entery,map<string,string>& M)
{
ifstream input(Entery.c_str());
string Key,Value;
while(input>>Key){
getline(input,Value);
M[Key]=Value;
}
}
sgi stl
so many ctor and copy ctor , use pointer
mark
尽可能地细分函数:CCilin(const string strFileName)
将它分成小的子函数,在子函数中尽可能少用循环语句,然后inline这些函数.
二,用懒惰法加cache; 每次开始时不全部读入所有数据,当需要是才真正读入,并初始化有关数据,把读入的数据加入一个cache中,以后从这个cache中读数据.cache中的数据按使用频率管理,读入新数据时,可以根据cache的大小,需要时将使用频率低的数据移出.
三.你的这个CCilin函数还存在许多需要改进的地方.
四,实在不能满足你的要求是才考虑用C的方面实现.
请问profile这个工具如何使用？
cilin_map[ci]=code;
单单这一句就要不少开销吧。你可以考虑把vector code去掉，直接使用cilin_map[ci]代替，这样至少可以省去vector拷贝的开销。
cilin_map[ci]=code改为cilin_map[ci].swap(code)看看。这是一个常数复杂度的操作，不需要作vector的拷贝
STL 体现的是最大限度的效率优化阿，不会因为它本身造成低效率的
性能差异应该主要来自两个方面:
1. 算法[容器]不同。使用map方案，每插入一个元素，map都要都其内建的红黑树做一些调整，以维持容器的有序性；而后一方案，大约是用vector, 你是一次性的读入所有元素O(n)，再用quicksort对其排序O(nlogn)。虽然两者从复杂度来说都是O(nlogn), 但map消耗的时间肯定是vector的几倍。 这应该是问题的主要方面。
2. 前面也有人提过了，使用map/vector比你的后一实现用了更多的时间来copy construct.
现在问题的关键是，你是否选对了容器，考虑一下下面的问题:
你需要比较经常的插入、删除吗？ 如果是，vector不合适，这两个操作的复杂度都是O(n), 而对map, 他是O(logn)。如果否，那可以直接用vector, 正如你后面的方法。
用STRING可能都是太有失效率了，
用* char[]可能就可以了，
一定要用动态数组吗？
vector.reserve(70000)
第一次分配时就多分配一点内存空间吧。
学习
仔细看看STL和IOSTREAM相关的内容。我觉得合理运用标准库的一些算法和适配器应该可以减少拷贝次数。
vector的动态增长确实是个问题，因为每次增长都要将全部内容拷贝。即使不增长，也要浪费不少空间。你的特征代码都是四个字符，可以把它们存到一个string里，需要时查找。不用找子串的函数，因为你这种情况可以优化。从头开始，每次递增4个位置比较。
map有insert()吧。在初始化时不用下标语法，用insert()，可以免去在树中查找键的时间。
通过优化代码，一定可以达到你需要的效率目标。
……
如果是以查找为主要目标还要求高速初始化，map不是个很好的选择，一个有序的vector在查找速度上差不多，而初始化的时候的速度和map不可同日而语，只有在大量的插入和查找混合的时候才需要二叉树。
而且你的实现可以考虑一次把文件都读入内存，
定义一个结构struct code {char * p; int num;};
里面直接存放特征码起始的char * p和特征码总数 int num;
然后vector< pair<char *, code> > map;
一次性把文件都读入内存空间char * content[]中
每个pair.first的char *指向对应的汉字，pair.second的code中的p指相对应特征码的起始点）num是这个汉字特征码总数，取特征码的时候直接用p + (i << 2)就是第i个特征码。后面的应该不用说了吧？：P
你仔细测试一下，getline都要占1/3的时间，iostream就很慢了。
stl又也不是万能的，设计的时候必须要做很多妥协，比如string里面的东西在外部就不能改动，大量的串复制当然会大大降低性能，而且string提供得查找能力也太差。容器存储本来就是原始数据的拷贝，往容器里存储必然导致调用拷贝构造函数。另外对于复杂类型的存储，sgi的traits根本就不能发挥作用。不过stl的提供的很多算法性能还是不错的。具体问题具体分析了，并不见得要把它全部抛弃，有用的当然要用啦。
struct strcomp
{
bool operator() (const char *x, const char *y) const { return strcmp(x, y) < 0; }
};
hash_map<char *, vector<char *>, hash<const char *>, strcomp> cilin_map;
char *whole_dict;
main()
{
ifstream infile("b.txt",ios::in);
streampos pos = infile.seekg(0, ios::end).tellg();
whole_dict = (char *)malloc(pos + 1);
infile.seekg(0, ios::beg).read(whole_dict, pos);
whole_dict[pos] = \0;
vector<char *> code;
char *p, *q, *key;
for(key = NULL, p = whole_dict; q = strpbrk(p, " \n"); *q = \0, p = q + 1)
{
if (*q == )
{
if (key) code.push_back(p);
else key = p;
} else {
code.push_back(p);
cilin_map[key] = code;
code.clear();
key = NULL;
}
}
}
这个实现的代码量不比你原来的差多少。取消了所有串复制，map换成hash_map速度会快得多，容器存储指针，traits会发挥作用。速度是原来的5倍多，用你的数据大概也就花1秒左右，不过hash查找总要比你的折半查找快得多吧。
不好意思，好像不是很明白，
我做以下推测，希望tth做一些验证：
1. 你的IOStream实现效率奇低。这是很显然的，目前流行的大部分IOStream不但效率差，没有标准化，而且有bug。因此，我个人在实际项目中坚持使用C Stdio。我推测你的时间损耗有不少花在了IOStream上。
2. 应该选择hash_map容器。在SGI STL和VC7.0的STL中都已经提供了hash_map，但没有标准化，你应该使用hash_map。
3. map的entry很多，如果包括vector，开销太大。如上面兄弟所说，如果能够用string最好，省掉了大量的临时对象。
hash_map比map快将近1倍。
我觉得还是看你怎么用STL的问题。
试验时候时候不考虑效率时，首选STL，方便、快捷。但做工程时，要考虑效率时，正如myan所说，C Stdio是首选。
mark
merlinran(天行者)说的很对。
STL内置的算法效率不低，看你怎么用了！
呵呵！
从我的经验看有两个方面：
1：文件I/O操作不当，速度奇慢，最好一次尽量多的将文件内容读入内存，再处理,速度快很多，尽量用fopen\fread\fwrite\fseek操作文件，其他的函数都会或多或少有分配内存不合理的问题，如果有的函数用的是getc那你就惨了，慢死你。
2：尽量不要多次分配内存，包括需要动态分配内存的类和函数，例如string/CString, 分配内存的速度也是程序速度慢的最主要瓶颈，频繁的分配内存不但速度慢，在写服务器端程序时会增加系统的不稳定性。
最后，STL不是问题，问题是string和getline.对了，嵌套方式编程速度也会下降很多。
能不能把数据也发给偶看一下子.
zhiguang_Tang@goqo.com
能不能把数据也发给偶看一下子.
csmaxsoft@163.com
