用于查找唯一字符串的内存有效方法

Question

我有一个如下所示的数据集:

000 100 200 300 010 020 030 001 002 003     
001 101 201 301 011 021 031 000 002 003    
002 102 202 302 012 022 032 001 000 003    
003 103 203 303 013 023 033 001 002 000    
010 110 210 310 000 020 030 011 012 013     
020 120 220 320 010 000 030 021 022 023     
030 130 230 330 010 020 000 031 032 033     
033 133 233 333 013 023 003 031 032 030     
100 000 200 300 110 120 130 101 102 103     
133 033 233 333 113 123 103 131 132 130     
200 100 000 300 210 220 230 201 202 203     
233 133 033 333 213 223 203 231 232 230     
300 100 200 000 310 320 330 301 302 303     
303 103 203 003 313 323 333 301 302 300     
313 113 213 013 303 323 333 311 312 310     
330 130 230 030 310 320 300 331 332 333    
331 131 231 031 311 321 301 330 332 333    
332 132 232 032 312 322 302 331 330 333    
333 133 233 033 313 323 303 331 332 330 

我打算做的是从中生成唯一字符串列表,产生:

000
001
002
003                      
010
011
012
013
020
021
022
023
030
031
032
033
100
101
102
103
110
113
120
123
130
131
132
133
200
201
202
203
210
213
220
223
230
231
232
233
300
301
302
303
310
311
312
313
320
321
322                      
323
330
331      
332      
333

我必须生成的代码就是这个.但它非常耗费记忆力.因为实际上字符串的长度大于36,并且文件中的行数超过3500万行.每行具有> 36*3列/条目数.有记忆效率的方法吗？

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>
using namespace std;


int main  ( int arg_count, char *arg_vec[] ) {
    if (arg_count !=2 ) {
        cerr << "expected one argument" << endl;
        return EXIT_FAILURE;      
    }

    string line;
    ifstream myfile (arg_vec[1]);


     map <string,int> Tags;    

    if (myfile.is_open())
    {
        while (getline(myfile,line) )
        {
            stringstream ss(line);    
            string Elem;


            while (ss >> Elem) {      

                Tags[Elem] = 1;           

            }


        }
        myfile.close();  
    }
    else { cout << "Unable to open file";} 


   for (map <string,int>::iterator iter = Tags.begin(); iter !=
           Tags.end();iter++) {      
       cout << (*iter).first << endl; 
   }



    return 0;
}

Answer 1

这取决于数据集的特征.在更糟糕的情况下,在所有字符串都是唯一的情况下,您将需要O(n)内存来记录您的看见集,或者需要O(n ^ 2)时间来重新扫描每个单词上的整个文件.但是,可以进行改进.

首先,如果您的数据集只包含3位整数,那么1000个bool的简单数组将比地图具有更高的内存效率.

如果你使用的是通用数据,那么另一种好的方法是对集合进行排序,因此相同字符串的副本最终会相邻,然后只需删除相邻的单词.有很好的研究算法可以对数据集进行排序,因为数据集太大而无法适应内存.当集合中的大部分单词是唯一的时,这是最有效的,因此在存储器中保持一组看到的单词非常昂贵.

顺便说一句,这可以通过shell管道轻松实现,因为GNU sort为您进行外部排序:

tr " " "\n" < testdata | LC_ALL=C sort | uniq

传递LC_ALL = C进行排序会禁用区域设置处理和多字节字符集支持,这可以显着提高速度.