hdqqq

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  35 随笔 :: 0 文章 :: 104 评论 :: 0 Trackbacks

这几天在写一个linux下的统计程序,主要是将一个文本文件读取后,按行进行分类统计.
用C++加 Stl实现,在windows平台下用vc编写,然后上传到linux机器上用gcc编译.

在处理上,我用了一个list<string>作为读取行的缓冲,读了一定的行数后就进行处理.
在读取文件的函数中是这样写的.

 

while (!infile.eof()) {
      memset(buf, 
0, sizeof(char)*2048);
      infile.getline(buf, 
2048);
      tt 
= buf;
      
if (tt.length()) {
        log_list.push_back(tt);
      }

      
//if the file is too big, so we do statistic per 5000 lines
      
if (log_list.size() >= 5000) {
        line_statistic(result, log_list);
        log_list.clear();
      }
}


一切ok, 但是这几天要处理的文件变地很大,有100多M,我没有多想,随便的把
      if (log_list.size() >= 5000) {
改成了
      if (log_list.size() >= 50000) {
想在50000行后再进行计算处理.不料想,在linux下运行效率居然出奇的慢.
原先统计5万行大概要20秒左右,现在居然要2分多.应该是list::size()这个函数出了问题.
我以前看过vc中的list的实现,是用一个成员变量进行记数的,在size()中就直接返回这个
值,应该不会有问题.

接着我看了gcc使用的stl的list::size()的实现,它是用
std::distance(begin(), end())
来计算的.
但是在std::distance的实现中,它按照iterator类型的不同,实现的方式也不同.
而list的iterator,是属于双向iterator,而非随机iterator,因此,在std::distance()
中使用了一个循环来计算值.也就是说在gcc的stl库中,每次调用list::size()函数,它都会从头
到尾遍历一遍.再看看我的代码,循环里面每一步size()都要遍历一遍list,难怪会变得
如此的慢.


没想到stl的不同实现还会有这种陷阱,一不留神就撞上了.

总之 gcc中list的size()是不能随便用的,list越大,size()函数花的时间越长.

posted on 2007-12-11 11:56 hdqqq 阅读(10476) 评论(19)  编辑 收藏 引用 所属分类: c/c++

评论

# re: gcc 中std::list 的size()成员函数 2007-12-11 12:44 海边沫沫
呵呵,为什么要用list?为什么不用vector?

还有,读取文件的代码写得太不C++了,像C的代码。

C++的代码,要么是
ifstream inputfile("filename);
string tmpstr;
vector<string> log_vector;
while(inputfile >> tmpstr)
{
log_vector.push_back(tmpstr);
}

要么是
ifstream inputfile("filename);
istream_iterator input_begin(inputfile);
istream_iterator input_end();
vector<string> log_vector(input_begin,input_end);  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数[未登录] 2007-12-11 13:20 hdqqq
不用vector是考虑到在大数据量的情况下,vector会进行内存的拷贝复制,所以采用了list  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-11 14:03 金庆
@海边沫沫
用istream_iterator<string>不行啊?好象是vector不能接受istream_iterator。贴个调试能过的代码让我们瞧瞧吧。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-11 14:20 岁月流冰
可以考虑使用deque。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-11 14:43
#include<iostream>
#include<vector>
#include<iterator>
#include<string>
#include<fstream>
using namespace std;
int main()
{
ifstream inputfile("q.cpp");
vector<string> vec;
string str;
while( getline(inputfile,str) )
vec.push_back(str);
copy(vec.begin(),vec.end(),ostream_iterator<string>(cout,"\n"));
return 0;
}  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-11 15:09 海边沫沫
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
std::ifstream input_file("D:\\emails100w.txt");
std::istream_iterator<std::string> input_begin(input_file);
std::istream_iterator<std::string> input_end;

std::vector<std::string> log_vector(input_begin,input_end);

//写入到另外一个文件
std::ofstream output_file("D:\\emails100w_copy.txt");
std::ostream_iterator<std::string> output_begin(output_file,"\n");
std::copy(log_vector.begin(),log_vector.end(),output_begin);
}

上面的代码是可以编译通过的,其中的D:\\emails100w.txt是一个包含一百万条记录的文本。

刚才我给出的代码通不过编译,确实是我的问题,主要是
std::istream_iterator<std::string> input_end;
这一行,最后应该没有括号。如果加上括号,编译器就不会认为这是一个iterator,就会调用vector的错误构造函数,就会出现博主所叙的错误。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-11 17:10 winsty
自己拿个变量统计?
虽然这样不太好...  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-12 11:02 金庆
@海边沫沫
可惜istream_iterator<string>是按string输入的,以空白符分隔,而不是以'\n'分隔。好像没有办法改变这个分隔符的吧?  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-13 14:21 海边沫沫
不错,是没有办法改变分隔符。
不过可以重载operator << 和自定义一个自己的string来实现这样的功能。

不过这样搞划不来,不如使用getline  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-14 13:10 lymons
bz里描述的问题是 关于list容器的size函数带来的效率的问题,而不是
怎么提高读写效率的问题,大家不要跑题啊。

而且,在读取的过程中,还要对超过固定行数之后的容器进行统计处理。

各位高手们,请仔细看bz的source的机能要求吧。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2007-12-16 20:14 TD
re: gcc 中std::list 的size()成员函数[未登录] 2007-12-11 13:20 hdqqq
不用vector是考虑到在大数据量的情况下,vector会进行内存的拷贝复制,所以采用了list 回复 更多评论

vector构造的时候指定一个大小,比如你程序中的5000之类的,就不会有内存的拷贝复制了吧  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数[未登录] 2007-12-16 21:36 hdqqq
@TD
是的,如果开始的时候指定vector是可以的,但是限定了vector的大小。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2008-01-31 21:29 abettor
真没想到,list会有这种弊端。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2008-09-19 23:12 hgyxb
list怎么会这样啊,设计的怎么搞的  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2008-12-12 16:00 bianshj
呵呵,真是太感谢了。
最近在写一个linux的服务器程序,用了list,刚开始的时候我自己处理list的元素数量,后来想stl既然这么优秀,它肯定会用成员变量来计数,使用size不回影响效率。结果用了size后果然出了很多问题。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2009-04-22 10:51 abettor
以前发现过这种情况,而且只在gcc中发现,不知gcc4有没有把这个问题修正过来。
  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数 2010-12-15 12:15 qci133
@abettor
这个不是gcc的问题,而是c++标准中确实没有规定list的size函数需要O(1)时间,反而规定了list的分割和合并需要O(1)时间。在后面一个限制之下,前面的要求是达不到的。网上有人贴过具体的分析  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数[未登录] 2011-08-29 17:14 Chipset
关std::list屁事,是你自己没有用明白。每个string的字符个数相等吗?如果不等的话,那行数有什么用?如果一定要用行数标记,那就设置一个变量啊。

list::size本来就没有规定是O(1)还是O(n),纯属依赖于实现。  回复  更多评论
  

# re: gcc 中std::list 的size()成员函数[未登录] 2016-04-25 10:01 hdqqq
@Chipset
麻烦看清楚文章再喷  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理