Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
rostman_rk
0 / 0 / 0
Регистрация: 06.04.2015
Сообщений: 7
#1

Оптимизация алгоритма Хаффмана - C++

13.04.2015, 02:32. Просмотров 769. Ответов 10
Метки нет (Все метки)

Сделал архиватор, но работает он запредельно долго ~ 30 мин на папку размером 50Mb(и это только упаковка). нужна помощь "Гуру" что бы ускорить процесс. Также принимается любая критика. Собственно первый клас есть родительским, для 2 остальных.
Вот сами исходники упаковки файла (для обработки папок есть отдельный клас):

Huffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#pragma once
#include <Vector>
#include <fstream>
#include <list>
#include <string>
using namespace std;
 
struct node{
public:
    unsigned int count = 0;
    char symbol = 0;
    node* left = NULL;
    node* right = NULL;
    node* parent = NULL;
    bool is_esc = false;
};
 
class Huffman
{
protected:
    node *treeRoot;
    ifstream *input;
    ofstream *output;
    unsigned int progress;
 
    virtual void clearTree(node* root);
    virtual void clear() = 0;
public: 
    Huffman();
    ~Huffman();
    virtual void decode(ifstream *&in, ofstream *&out) = 0;
    virtual void encode(ifstream *&in, ofstream *&out) = 0;
    unsigned int getProgress();
};

Huffman.cpp
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "Huffman.h"
 
Huffman::Huffman(){}
Huffman::~Huffman(){}
 
void Huffman::clearTree(node* root){
    if (root->left != NULL){
        clearTree(root->left);
    }
    if (root->right != NULL){
        clearTree(root->right);
    }
    delete root;
}
 
unsigned int Huffman::getProgress(){
    return progress;
}

StaticHuffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#pragma once
#include "Huffman.h"
#include <unordered_map>
using namespace std;
class StaticHuffman :public Huffman
{
private:
    unordered_map <char, unsigned int > weight;
 
    node* min(std::list<node*>& l);
    unordered_map<vector<bool>, char> createRTable();
    unordered_map<char, vector<bool>> createTable();
    void doTable(node* n, unordered_map<char, std::vector<bool>> &table, vector<bool> &v);
    void buildHuffmanTree();
    void fillTableOfWeight();
    void writeInfo();
    list<node*> createListOfNodes();
    void StaticHuffman::createHuffmanTree();
    void clear();
public:
    StaticHuffman();
    void decode(ifstream *&in, ofstream *&out);
    void encode(ifstream *&in, ofstream *&out);
 
};

StaticHuffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include "StaticHuffman.h"
 
using namespace std;
 
StaticHuffman::StaticHuffman(){}
 
    node* StaticHuffman::min(list<node*>& l){
        //search min in list of node*
        node*min = l.front();
        for each(node* i in l){
            if (i->count < min->count) min = i;
        }
        return min;
    }
 
    
 
    void StaticHuffman::doTable(node* n, unordered_map<char, vector<bool>> &table, vector<bool> &v){
        if (n->left != NULL){
            v.push_back(0);
            doTable(n->left, table, v);
        }
        if (n->right != NULL){
            v.push_back(1);
            doTable(n->right, table, v);
        }
        if (n->left == NULL && n->right == NULL){
            table[n->symbol] = v;
        }
        if (v.size() != 0) v.pop_back();
    }
 
    unordered_map<vector<bool>, char> StaticHuffman::createRTable(){
        unordered_map<char, vector<bool>> table = createTable();
        unordered_map<vector<bool>, char> rTable;
        for each (pair <char, vector<bool>>  it in table){
            rTable[it.second] = it.first;
        }
        return rTable;
    }
 
    unordered_map<char, vector<bool>> StaticHuffman::createTable(){
        vector<bool> v;
        unordered_map<char, vector<bool>> table;
        doTable(treeRoot, table, v);
        return table;
    }
 
    void StaticHuffman::fillTableOfWeight(){
        char buf;
        while (input->peek() != EOF){
            input->get(buf);
            weight[buf]++;
        }
        //begining of file
    }
 
    void StaticHuffman::writeInfo(){
        //write lenth of input file and size of weight table in output file
        input->seekg(0, ios::end);
        progress = input->tellg();
        //lenght of file
        output->write((char*)&progress, sizeof(int));
        char l = weight.size() - 1;
        //size of weight
        output->write((char*)&l, sizeof(char));
        for each (pair <char, unsigned int > i in weight){
            output->write((char*)&i.first, sizeof(char));
            output->write((char*)&i.second, sizeof(int));
        }
        input->clear();
        input->seekg(0, ios::beg);
    }
 
    list<node*> StaticHuffman::createListOfNodes(){
        //create list of nodes
        list<node*> nodes;
        for each (pair <char, unsigned int > i in weight){
            node* block = new node;
            block->symbol = i.first;
            block->count = i.second;
            nodes.push_front(block);
        }
        return nodes;
    }
 
    void StaticHuffman::createHuffmanTree(){
        list<node*> nodes = createListOfNodes();    
        weight.clear();
        //create hufman tree
        while (nodes.size() != 1){
            node * newnode = new node;
            newnode->right = min(nodes);
            newnode->right->parent = newnode;
            nodes.remove(newnode->right);
            newnode->left = min(nodes);
            newnode->left->parent = newnode;
            nodes.remove(newnode->left);
            newnode->count = newnode->right->count + newnode->left->count;
            nodes.push_front(newnode);
        }
        treeRoot = nodes.front();
    }
 
    void StaticHuffman::clear(){
        clearTree(treeRoot);
    }
 
    void StaticHuffman::encode(ifstream *&in, ofstream *&out){
        input = in;
        output = out;
        fillTableOfWeight();
        writeInfo();
        createHuffmanTree();
        unordered_map<char, std::vector<bool>> table = createTable();
        vector<bool> v;
        short count = 0;
        char buf = 0;
        char c;
        //hufman coding
        while (input->peek() != EOF){
            input->get(c);
            progress--;
            v = table[c];
            for (int i = 0; i < v.size(); i++){
                buf = (buf | v[i]);
                count++;
                if (count == 8){
                    count = 0;
                    output->write((char*)& buf, sizeof(char));
                    buf = 0;
                }
                buf <<= 1;
            }
        }
        //last free bits
        if (count){
            buf <<= 7 - count;
            output->put(buf);
        }
        clear();
    }
 
    void StaticHuffman::decode(ifstream *&in, ofstream *&out){
        input = in;
        output = out;
        input->read((char*)&progress, sizeof progress);
 
        unsigned char y;
        input->read((char*)&y, sizeof(char));
        short t = (int)y + 1;
        char buf;
        unsigned int count;
        for (int i = 0; i < t; i++){
            input->get(buf);
            input->read((char*)&count, sizeof(int));
            weight[buf] = count;
        }
 
        createHuffmanTree();
 
        unordered_map < vector<bool>, char > table = createRTable();
        int test = 0;
        vector<bool> v;
        bool foo;
        while (progress != 0){
            input->get(buf);        
            for (int i = 0; i < 8 && progress; i++){
                foo = buf & 128;
                foo ? v.push_back(1) : v.push_back(0);
                buf <<= 1;
                if (table.find(v) != table.end()){
                    output->put(table[v]);
                    progress--;
                    v.clear();
                }
            }
        }
        clear();
    }

DynamicHuffman.h
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#pragma once
#include "Huffman.h"
using namespace std;
class DynamicHuffman : public Huffman
{
private:
    vector <node* > listOfItems;
    char writeBuf = 0;
    short count = 0;
 
    void fillWriteBuf(int size, char &buf);
    void clear();
    void add(char &b); 
    list<bool> getHuffmanCode(node* item);
    int findIndexOfNode(node *n);
    void writeCodeInFile(list<bool> &v, int &size);
    list<bool> getCharCode(char c);
    void rebuildTree(node* in);
    void swapIncNodes(node* &f, node* &s);
    void swapNodes(node* &f, node* &s);
    node* find(char &s);
    void writeInfo();
    node* getChangedItem(char buf);
 
public:
    DynamicHuffman();
    void encode(ifstream *&in, ofstream *&out);
    void decode(ifstream *&in, ofstream *&out);
};

DynamicHuffman.cpp
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#include "DynamicHuffman.h"
using namespace std;
 
DynamicHuffman::DynamicHuffman(){
}
 
inline void DynamicHuffman::add(char &b){
    //write new node in tree
    node* tmpl = new node;
    node* tmpr = new node;
    //fill previous node with esc-symbol
    listOfItems.back()->is_esc = false;
    listOfItems.back()->left = tmpl;
    listOfItems.back()->right = tmpr;
    //fill sons
    tmpl->symbol = b;
    tmpl->parent = listOfItems.back();
    //fill new esc symbol
    tmpr->is_esc = true;
    tmpr->parent = listOfItems.back();
 
    listOfItems.push_back(tmpl);
    listOfItems.push_back(tmpr);
}
 
void DynamicHuffman::swapIncNodes(node* &f, node* &s){
    if (s->parent->left == s){
        swap(f, s->parent->left);
    }
    else{
        swap(f, s->parent->right);
    }
}
 
void DynamicHuffman::swapNodes(node* &f, node* &s){
    if (f->parent->left == f)
    {
        swapIncNodes(f->parent->left, s);
    }
    else{
        swapIncNodes(f->parent->right, s);
    }
}
 
node* DynamicHuffman::find(char &s){
    for (int i = 0; i < listOfItems.size(); i++){
        if (listOfItems[i]->symbol == s && listOfItems[i]->left == NULL && listOfItems[i]->right == NULL && !listOfItems[i]->is_esc){
            return listOfItems[i];
        }
    }
    return NULL;
}
 
int DynamicHuffman::findIndexOfNode(node *n){
    for (int i = listOfItems.size() - 1; i >= 0; i--){
        if (listOfItems[i] == n){
            return i;
        }
    }
}
 
 
list<bool> DynamicHuffman::getCharCode(char c){
    list<bool> res;
    char buf;
    for (int i = 0; i < 8; i++)
    {
        buf = c & 1;
        if (buf){
            res.push_front(1);
        }
        else{
            res.push_front(0);
        }
        c >>= 1;
    }
    return res;
}
 
inline void DynamicHuffman::rebuildTree(node* in){
    while (in->parent != NULL){
        int it = findIndexOfNode(in);
        int j = 0;
        while (j != it && listOfItems[it - j - 1]->count == listOfItems[it]->count){
            j++;
        }
        if (j != 0 && listOfItems[it]->parent != listOfItems[it - j]){
            swapNodes(listOfItems[it - j], listOfItems[it]);
            swap(listOfItems[it - j]->parent, listOfItems[it]->parent);
            swap(listOfItems[it - j], listOfItems[it]);
        }
        in->count++;
        in = in->parent;
    }
    in->count++;
}
 
void DynamicHuffman::writeInfo(){
    input->seekg(0, ios::end);
    progress = input->tellg();
    output->write((char*)&progress, sizeof(int));
    input->clear();
    input->seekg(0);
}
 
inline list<bool> DynamicHuffman::getHuffmanCode(node* item){
    list<bool> v;
    while (item->parent != NULL){
        if (item == item->parent->left){
            v.push_front(0);
        }
        else{
            v.push_front(1);
        }
        item = item->parent;
    }
    return v;
}
 
inline void DynamicHuffman::writeCodeInFile(list<bool> &v, int &size){
    for (int i = 0; i < size; i++){
        writeBuf = (writeBuf | v.front());
        count++;
        v.pop_front();
        if (count == 8){
            count = 0;
            output->put(writeBuf);
            writeBuf = 0;
        }
        writeBuf <<= 1;
    }
}
 
inline node* DynamicHuffman::getChangedItem(char buf){
    node *tmp = find(buf);
    list<bool> v;
    //if char is new
    if (tmp == NULL){
        tmp = listOfItems.back();
        //write in file code of esc char
        v = getHuffmanCode(tmp);
        int size = v.size();
        writeCodeInFile(v, size);
        //write code of new char
        v = getCharCode(buf);
        size = v.size();
        writeCodeInFile(v, size);
        add(buf);
        return listOfItems[listOfItems.size() - 2];
    }
    //if char isnt new
    else{
        v = getHuffmanCode(tmp);
        int size = v.size();
        writeCodeInFile(v, size);
        return tmp;
    }
}
 
void DynamicHuffman::clear(){
    listOfItems.clear();
    writeBuf = 0;
    count = 0;
    clearTree(treeRoot);
    treeRoot = NULL;
}
 
 
void DynamicHuffman::encode(ifstream *&in, ofstream *&out){
    input = in;
    output = out;
    writeInfo();
    //tree initiation
    treeRoot = new node;
    treeRoot->is_esc = true;
    char buf;
    listOfItems.push_back(treeRoot);    
    list<bool> v;
    v.clear();
    while (!input->eof()){
        progress--;
        input->read((char*)&buf, 1);
        node *in = getChangedItem(buf); 
        rebuildTree(in);
    }
    //last free bits
    if (count){
        writeBuf <<= 7 - count;
        output->put(writeBuf);
    }
    clear();
}
 
inline void DynamicHuffman::fillWriteBuf(int size, char &buf){
    for (int j = 0; j < size; j++){
        writeBuf <<= 1;
        bool foo = buf & 128;
        writeBuf = writeBuf | foo;
        buf <<= 1;
    }
}
 
void DynamicHuffman::decode(ifstream *&in, ofstream *&out){
    input = in;
    output = out;
    input->read((char*)&progress, sizeof progress);
    treeRoot = new node;
    treeRoot->is_esc = true;
    listOfItems.push_back(treeRoot);
    node *tmp = treeRoot;
    char buf;
    while (progress){
        input->read((char*)&buf, 1);
        for (int i = 0; i < 8 && progress; i++){
            if (tmp->left == NULL && tmp->right == NULL){
                //if symbol is new
                if (tmp->is_esc){
                    writeBuf = 0;
                    //read first part of new symbol from this byte
                    fillWriteBuf(8 - i, buf);
                    //read last part of new symbol from next byte
                    input->read((char*)&buf, 1);
                    fillWriteBuf(i, buf);
                    //add symbol to list and write in file
                    add(writeBuf);
                    output->put(writeBuf);
                    //rebuild tree
                    rebuildTree(listOfItems[listOfItems.size() - 2]);
                }
                //symbol is in list
                else{
                    output->put(tmp->symbol);
                    rebuildTree(tmp);
                }
                //pointer to root and dec lenght
                tmp = treeRoot;
                progress--;
            }
            //move to next bit of input char
            bool foo = buf & 128;
            tmp = foo ? tmp->right : tmp->left;
            buf <<= 1;
        }
    }
    clear();
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SatanaXIII
Супер-модератор
Эксперт С++
5589 / 2623 / 239
Регистрация: 01.11.2011
Сообщений: 6,448
Завершенные тесты: 1
13.04.2015, 11:16     Оптимизация алгоритма Хаффмана #2
Цитата Сообщение от rostman_rk Посмотреть сообщение
C++
8
9
10
11
12
13
14
15
16
struct node{
public:
    unsigned int count = 0;
    char symbol = 0;
    node* left = NULL;
    node* right = NULL;
    node* parent = NULL;
    bool is_esc = false;
};
А что за дивный компилятор у вас?
Поясните пожалуйста как у вас члены структурки инициализируются при объявлении?
NEbO
587 / 455 / 49
Регистрация: 22.01.2009
Сообщений: 1,180
Записей в блоге: 1
Завершенные тесты: 2
13.04.2015, 11:30     Оптимизация алгоритма Хаффмана #3
rostman_rk, воспользуйтесь профайлером
rostman_rk
0 / 0 / 0
Регистрация: 06.04.2015
Сообщений: 7
13.04.2015, 14:46  [ТС]     Оптимизация алгоритма Хаффмана #4
А что за дивный компилятор у вас?
Поясните пожалуйста как у вас члены структурки инициализируются при объявлении?
VS2013 проглатывает и более того работает + я их создаю динамически.

rostman_rk, воспользуйтесь профайлером
Я думаю он тут не понабиться так как вся обработка тут (где обработка каждого байта/бита):
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (input->peek() != EOF){
            input->get(c);
            progress--;
            v = table[c];
            for (int i = 0; i < v.size(); i++){
                buf = (buf | v[i]);
                count++;
                if (count == 8){
                    count = 0;
                    output->write((char*)& buf, sizeof(char));
                    buf = 0;
                }
                buf <<= 1;
            }
        }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
while (progress != 0){
            input->get(buf);        
            for (int i = 0; i < 8 && progress; i++){
                foo = buf & 128;
                foo ? v.push_back(1) : v.push_back(0);
                buf <<= 1;
                if (table.find(v) != table.end()){
                    output->put(table[v]);
                    progress--;
                    v.clear();
                }
            }
        }

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
 while (!input->eof()){
        progress--;
        input->read((char*)&buf, 1);
        node *in = getChangedItem(buf); 
        rebuildTree(in);
    }
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
while (progress){
        input->read((char*)&buf, 1);
        for (int i = 0; i < 8 && progress; i++){
            if (tmp->left == NULL && tmp->right == NULL){
                //if symbol is new
                if (tmp->is_esc){
                    writeBuf = 0;
                    //read first part of new symbol from this byte
                    fillWriteBuf(8 - i, buf);
                    //read last part of new symbol from next byte
                    input->read((char*)&buf, 1);
                    fillWriteBuf(i, buf);
                    //add symbol to list and write in file
                    add(writeBuf);
                    output->put(writeBuf);
                    //rebuild tree
                    rebuildTree(listOfItems[listOfItems.size() - 2]);
                }
                //symbol is in list
                else{
                    output->put(tmp->symbol);
                    rebuildTree(tmp);
                }
                //pointer to root and dec lenght
                tmp = treeRoot;
                progress--;
            }
            //move to next bit of input char
            bool foo = buf & 128;
            tmp = foo ? tmp->right : tmp->left;
            buf <<= 1;
        }
    }


Добавлено через 2 часа 30 минут
Цитата Сообщение от NEbO Посмотреть сообщение
rostman_rk, воспользуйтесь профайлером
а ну и да, я ж профилировал, только вот не знаю что можно оптимизировать. Вот коротко самые ресурсоемкие:
при разкодировании:

а)статическим
C++
1
2
Function Name   Total CPU (%)   Self CPU (%)    Total CPU (ms)  Self CPU (ms)   Module
 + <Module>::std.vector<bool,std::allocator<bool> >.push_back   32.77 % 0.05 %  28090   45  Coursework.exe
б) динамическим
C++
1
2
Function Name   Total CPU (%)   Self CPU (%)    Total CPU (ms)  Self CPU (ms)   Module
 + <Module>::DynamicHuffman.findIndexOfNode 14.50 % 4.98 %  12430   4271    Coursework.exe
при кодировании:
а) динимический:
C++
1
2
3
4
Function Name   Total CPU (%)   Self CPU (%)    Total CPU (ms)  Self CPU (ms)   Module
 + <Module>::DynamicHuffman.rebuildTree 14.62 % 0.10 %  12533   86  Coursework.exe
Function Name   Total CPU (%)   Self CPU (%)    Total CPU (ms)  Self CPU (ms)   Module
 + <Module>::DynamicHuffman.getChangedItem  14.27 % 0.03 %  12232   28  Coursework.exe
б)статическим
C++
1
2
Function Name   Total CPU (%)   Self CPU (%)    Total CPU (ms)  Self CPU (ms)   Module
 - <Module>::StaticHuffman.encode   3.63 %  0.08 %  3112    65  Coursework.exe
retmas
Жарю без масла
859 / 741 / 164
Регистрация: 13.01.2012
Сообщений: 1,694
13.04.2015, 17:35     Оптимизация алгоритма Хаффмана #5
Цитата Сообщение от SatanaXIII Посмотреть сообщение
Поясните пожалуйста как у вас члены структурки инициализируются при объявлении?
с++11 позволяет

Добавлено через 5 минут
Цитата Сообщение от rostman_rk Посмотреть сообщение
C++
1
+ <Module>::std.vector<bool,std::allocator<bool> >.push_back 32.77 % 0.05 % 28090 45 Coursework.exe
вектор плохо подходит для частой вставки. профайлер намекает
rostman_rk
0 / 0 / 0
Регистрация: 06.04.2015
Сообщений: 7
13.04.2015, 20:08  [ТС]     Оптимизация алгоритма Хаффмана #6
Цитата Сообщение от retmas Посмотреть сообщение
вектор плохо подходит для частой вставки. профайлер намекает
Судя по тестам прочитанным в инете он самый быстрый для вставки в конец из всех "гибких" контейнеров, если я не прав, можете предложить альтернативу?
Цитата Сообщение от Википедия
Добавление-удаление элемента в конец vector занимает амортизированное O(1) время
gazlan
3130 / 1905 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
13.04.2015, 21:11     Оптимизация алгоритма Хаффмана #7
Цитата Сообщение от rostman_rk Посмотреть сообщение
альтернативу?
Priority Queues and the STL
rostman_rk
0 / 0 / 0
Регистрация: 06.04.2015
Сообщений: 7
13.04.2015, 22:07  [ТС]     Оптимизация алгоритма Хаффмана #8
Цитата Сообщение от gazlan Посмотреть сообщение
Priority Queues and the STL
я знаком с контейнерами STL, и мне "кажется" очередь с приоритетом не подойдёт в данном случаи.
Под альтернативой я имел введу что-то быстрей вектора. Может я что-то не знаю про скорость других контейнеров
Dmitriy_M
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,350
Записей в блоге: 11
15.04.2015, 23:09     Оптимизация алгоритма Хаффмана #9
Цитата Сообщение от rostman_rk Посмотреть сообщение
Судя по тестам прочитанным в инете он самый быстрый для вставки в конец из всех "гибких" контейнеров, если я не прав, можете предложить альтернативу?
А std::vector<bool> это вообще не контейнер(Скотт Мейерс, Эффективное использование STL)
rostman_rk
0 / 0 / 0
Регистрация: 06.04.2015
Сообщений: 7
18.04.2015, 18:42  [ТС]     Оптимизация алгоритма Хаффмана #10
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
А std::vector<bool> это вообще не контейнер(Скотт Мейерс, Эффективное использование STL)
Собственно псевдо-контейнер (Скотт Мейерс, Эффективное использование STL) не знает что он не контейнер, а то, что он работает, так что бы занимало меньше места, не меняет сути при его использовании. И то, что его не рекомендуют использовать я знаю, но поверьте на слово, аллокация для deque занимает намного больше времени (проверено), а bitset не подходят по причине отсутствия гибкости в размере (неоднозначно тогда код символа задаётся). Я попросил совета, а в ответ получаю, замечания по поводу терминологии. Если я уж спросил, это не значит, что у меня нету идей и я сразу пошел писать на форум, не прочитав нечего перед этим, а значит, что я не нашел ответа, после долгих поисков и попыток.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2015, 20:02     Оптимизация алгоритма Хаффмана
Еще ссылки по теме:

Кодирование алгоритма Хаффмана C++
C++ Ошибка “vector<bool> erase iterator outside range” при работе алгоритма Хаффмана
Оптимизация алгоритма C++
C++ Реализация алгоритма Хаффмана с использованием классов
C++ Оптимизация расшифровки файла | алгоритм хаффмана

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Dmitriy_M
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,350
Записей в блоге: 11
18.04.2015, 20:02     Оптимизация алгоритма Хаффмана #11
Цитата Сообщение от rostman_rk Посмотреть сообщение
так что бы занимало меньше места, не меняет сути при его использовании
Именно из-за того что он сделан, что бы занимать меньше места, он медленно работает.

Цитата Сообщение от rostman_rk Посмотреть сообщение
аллокация для deque занимает намного больше времени
Поэтому берут std::vector<char> и заранее резервируют необходимое количество байт памяти, можно уложится в 8Kb памяти.
Yandex
Объявления
18.04.2015, 20:02     Оптимизация алгоритма Хаффмана
Ответ Создать тему
Опции темы

Текущее время: 05:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru