Эффективные методы памяти для поиска уникальных строк

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 и более 35 миллионов строки в файле. Каждая строка с> 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 булев будет намного больше памяти, чем карта.

Если вы используете общие данные, тогда другим хорошим подходом будет сортировка набора, чтобы копии одной и той же строки заканчивались рядом, а затем просто удалялись смежные слова. Существуют хорошо изученные алгоритмы для сортировки набора данных, слишком большого для размещения в памяти . Это наиболее эффективно, когда большой процент слов в наборе уникален, и, следовательно, удержание набора увиденных слов в памяти непозволительно дорого.

Кстати, это можно легко реализовать с помощью конвейера оболочки, поскольку сортировка GNU выполняет внешнюю сортировку для вас:

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

Передача LC_ALL = C для сортировки отключает обработку локали и поддержку многобайтового набора символов, что может значительно увеличить скорость.

Answer 2

O (1) память [ram]:

Если вы хотите вообще не использовать память (кроме пары временных переменных), вы можете просто прочитать по 1 записи за раз и добавить ее в выходной файл, если он еще не существует в выходном файле. Это будет медленнее по времени, так как вам придется читать по 1 записи за раз из выходного файла.

Вы можете вставить запись в выходной файл в алфавитном порядке, и тогда вы сможете увидеть, существует ли запись уже во время O (logn), с помощью бинарного поиска для каждой вставляемой записи. Для фактической вставки вам нужно заново создать файл, который является O (nlogn). Вы делаете это n раз для каждой входной строки, поэтому в целом алгоритм будет работать в O (n ^ 2logn) (который включает в себя поиск, чтобы найти вставку pos + вставку) и использовать O (1) оперативную память.

Поскольку ваш выходной файл уже находится в алфавитном порядке, хотя в будущем поиск также будет осуществляться только через O (logn) при бинарном поиске.

Вы также можете минимизировать этап воссоздания файла, оставляя избыточное пространство между записями в файле. Когда алгоритм был выполнен, вы можете создать вакуум в файле. Это привело бы к O (nlogn).

---

Другой способ уменьшить память:

Если ваши строки имеют общие префиксы, то вы можете использовать trie и, вероятно, использовать меньше памяти в целом, так как вы упомянули, что ваши строки> 36 длин.

Answer 3

Ну, std :: set может быть немного быстрее и использовать меньше памяти, чем std :: map.

Answer 4

Кажется, учитывая большое количество записей, будет существенное количество совпадений в последовательностях символов. Вы можете построить дерево, используя записи в каждой позиции каждой последовательности как узлы. Скажем, у вас есть записи 12345 и 12346, тогда первые четыре записи в последовательности перекрываются и, таким образом, могут быть сохранены в дереве с 6 узлами.

Вы можете пройтись по дереву, чтобы увидеть, содержится ли данный символ в данной позиции, если нет, то вы бы добавили его. Когда вы достигнете конца данной строки, вы просто пометите этот узел как завершающий строковый узел. Воспроизведение уникальных записей было бы вопросом глубины первого обхода дерева, когда путь от корневого узла к каждому терминатору представляет уникальную запись.

Если вы разбиваете набор данных, скажем, на X тысяч строк и агрегируете деревья, это сделало бы хорошую работу по уменьшению карты.

Вы смотрите на пространство узлов 10 ^ 36, поэтому, если данные полностью случайны, вы смотрите на большое возможное количество узлов. Если есть много совпадений и меньшее количество уникальных записей, вы, вероятно, обнаружите, что используете намного меньше

Answer 5

Вы можете посмотреть отличную библиотеку Массивы Джуди . Компактная, основанная на три, очень быстрая и эффективная структура данных, масштабируемая до больших строк. Лучше, чем любое дерево поиска. Вы можете использовать функции JudySL для своих целей. Вы можете использовать его аналогично вашей программе, но он намного быстрее и эффективнее использует память.

Answer 6

Решение, которое я бы предложил, - использовать отображенный в памяти файл для доступа к данным и сортировку по основанию для сортировки списка. Это тривиально, если строки одинаковой длины. Если строки имеют разную длину, используйте радикальную сортировку для быстрой предварительной сортировки с использованием n первых символов, затем сортируйте несортированные подсписки любым подходящим способом. С очень короткими подсписками, простая пузырьковая сортировка сделает это. В более длинных списках используйте быструю сортировку или используйте набор STL с пользовательским классом, предоставляющим оператор сравнения.

При отображении памяти и радикальной сортировке требования к памяти и производительность будут оптимальными. Все, что вам нужно, это пространство отображения (размер файла) и таблица из 32-битных значений с одним значением на строку для хранения связанного списка для сортировки по основанию.

Вы также можете сэкономить память и ускорить сортировку, используя более компактную кодировку строк. Простое кодирование будет использовать 2 бита на символ, используя значения 1,2 и 3 для трех букв и 0 для обозначения конца строки. Или более эффективно, используйте кодировку base 3, упакованную в целые числа и кодирующую длину строки впереди. Допустим, у вас есть символы c1, c2, C3, c4, при кодировании получится целое число c1 * 3 ^ 3 + c2 * 3 ^ 2 + c3 * 3 ^ 1 + c4 * 3 ^ 0. Предполагается, что вы назначаете значение от 0 до 2 каждому символу. Используя эту кодировку, вы сэкономите память и оптимизируете сортировку, если количество сортируемых строк огромно.

Answer 7

Попробуйте STXXL как внешний stl для огромных наборов данных.

Answer 8

std::set было бы лучше, но вы должны изучить хэш-наборы. Они не доступны в текущей стандартной библиотеке C ++ (хотя она должна быть в C ++ 0x), но некоторые компиляторы имеют реализации. В Visual C ++ есть stdext :: hash_set , а в boost есть кое-что для этого, см. Библиотека многоиндексных контейнеров Boost .

Answer 9

Вы могли бы просто написать сортировку на месте для этого. Вам все равно придется загружать файл в память, потому что сортировка на месте с помощью ввода-вывода не будет эффективной. Вам придется читать и писать для каждого сравнения.