c++ - 查找唯一字符串的内存高效方法

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 值的简单数组将比映射更节省内存。

如果您使用的是一般数据，那么另一种好方法是对集合进行排序，这样同一字符串的拷贝最终会相邻，然后只需删除相邻的单词即可。 sorting a dataset too large to fit in memory 有经过深入研究的算法.当集合中的大部分单词都是唯一的时，这是最有效的，因此在内存中保存一组可见单词的成本非常高。

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

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

将 LC_ALL=C 传递给排序会禁用区域设置处理和多字节字符集支持，这可以显着提高此处的速度。