滥用C++容器的教训：vector和set的查找效率问题
http://www.ithao123.cn/content-5318099.html曾经写过一个文本比较的程序，其功能是先扫描两个服务器中指定的目录，按照给定的时间参数把符合条件的文件路径写入列表中，然后比较这两个服务器中分别生成的列表文件做文件备份。一开始没有考虑到文件数量会很庞大，所以按照以前的编程习惯使用两个常用的vector容器来存放两个列表中的内容，然后做比较。
http://www.ithao123.cn/content-5318099.html
曾经写过一个文本比较的程序，其功能是先扫描两个服务器中指定的目录，按照给定的时间参数把符合条件的文件路径写入列表中，然后比较这两个服务器中分别生成的列表文件做文件备份。一开始没有考虑到文件数量会很庞大，所以按照以前的编程习惯使用两个常用的vector容器来存放两个列表中的内容，然后做比较。
1 vector<string> loc_files; 2 vector<string> ser_files; 3 4 /** 5 * Reading data in list file into global container 6 */ 7 int read_list(char *lf_local, char *lf_server) 8 { 9 ifstream f; 10 char filename[PATH_LEN]; 11 12 f.open(lf_local, ios::in); 13 if(f.fail()) 14 { 15 perror("ERROR: Open local list file failed"); 16 return -1; 17 } 18 19 while(!f.eof()) 20 { 21 memset(filename, 0, sizeof(filename)); 22 f.getline(filename, sizeof(filename), 'n'); 23 if(strlen(filename)>0) 24 loc_files.push_back(string(filename)); 25 } 26 f.close(); 27 28 f.open(lf_server, ios::in); 29 if(f.fail()) 30 { 31 perror("ERROR: Open server list file failed"); 32 return -1; 33 } 34 35 while(!f.eof()) 36 { 37 memset(filename, 0, sizeof(filename)); 38 f.getline(filename, sizeof(filename), 'n'); 39 if(strlen(filename)>0) 40 ser_files.push_back(string(filename)); 41 } 42 f.close(); 43 44 return 0; 45 } 46 47 48 /** 49 * Compare the list data in container, output the not-exist one to file 50 */ 51 void do_compare(char *savename) 52 { 53 ofstream f; 54 f.open(savename, ios::out); 55 if(f.fail()) 56 { 57 perror("ERROR: Open save file failed"); 58 exit(-1); 59 } 60 61 req_count = 0; 62 for( vector<string>::iterator it=ser_files.begin(); 63 it!=ser_files.end(); it++) 64 { 65 if( find(loc_files.begin(), loc_files.end(), *it) == loc_files.end() ) 66 { 67 f<<*it<<endl; 68 req_count++; 69 } 70 } 71 72 f.close(); 73 }
如果上面的程序用于文件数量在几百之内的目录中，你可能不会发现性能有什么问题，但想象一下，如果你现在处理的是一个网站的图片服务器，里面存放的图片数量是几十万张，同时每张图片还有2～3张对应的缩略图，这样子我们在做比较时按照上面的算法来处理的话就是n*n的时间复杂度（其中n是百万级别的）……我曾试着跑这个程序，结果运行了5个小时还没得出结果就把它中止了。
解决这个问题的思路很简单——抛弃你对容器的使用偏好，弄清楚需求后重新选择一个适合的容器。因为在比较时我需要遍历容器进行查找，所以set是一个不错的选择：一是它二叉搜索树结构对元素进行存取，二是插入新元素时它可以保证不会重复。代码中修改的地方不多，但性能却有了惊人的改进：
1 set<string> loc_files; 2 set<string> ser_files; 3 4 /** 5 * Reading data in list file into global container 6 */ 7 int read_list(char *lf_local, char *lf_server) 8 { 9 ifstream f; 10 char filename[PATH_LEN]; 11 char *ptr; 12 13 f.open(lf_local, ios::in); 14 if(f.fail()) 15 { 16 perror("ERROR: Open local list file failed"); 17 return -1; 18 } 19 20 while(!f.eof()) 21 { 22 memset(filename, 0, sizeof(filename)); 23 f.getline(filename, sizeof(filename), 'n'); 24 //if(strlen(filename)>0 && (ptr=strrchr(filename, '/'))!=NULL) 25 if(strlen(filename)>0) 26 { 27 loc_files.insert(string(filename)); 28 } 29 } 30 f.close(); 31 32 f.open(lf_server, ios::in); 33 if(f.fail()) 34 { 35 perror("ERROR: Open server list file failed"); 36 return -1; 37 } 38 39 while(!f.eof()) 40 { 41 memset(filename, 0, sizeof(filename)); 42 f.getline(filename, sizeof(filename), 'n'); 43 //if(strlen(filename)>0 && (ptr=strrchr(filename, '/'))!=NULL) 44 if(strlen(filename)>0) 45 { 46 ser_files.insert(string(filename)); 47 } 48 } 49 f.close(); 50 51 return 0; 52 } 53 54 /** 55 * Compare the list data in container, output the not-exist one to file 56 */ 57 void do_compare(char *savename) 58 { 59 ofstream f; 60 f.open(savename, ios::out); 61 if(f.fail()) 62 { 63 perror("ERROR: Open save file failed"); 64 exit(-1); 65 } 66 67 req_count = 0; 68 69 set<string>::iterator itr = ser_files.begin(); 70 set<string>::iterator itr2; 71 for(; itr!=ser_files.end(); itr++) 72 { 73 if( (itr2=loc_files.find(*itr))==loc_files.end() ) 74 { 75 f<<(*itr)<<endl; 76 req_count++; 77 } 78 } 79 80 f.close(); 81 }
同样的需求，使用vector时运行不止5个小时的时间，使用set后的运行时间只有35秒，5小时和35秒啊！所以这一次我得到的经验教训就是：不要盲目地使用容器，要弄清楚各个容器的内部算法是什么，然后根据实际情况选择合适的。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
2
0- 0
已为社区贡献4条内容
所有评论(0)