Оптимизация алгоритма

@Aringot · Регистрация: 24.05.2016

Студворк — интернет-сервис помощи студентам

Добрый день уважаемые фоумчане.

Как-то давеча я создавал тему на форуме http://www.cyberforum.ru/cpp-b... 65826.html, в которой уважаемый L0M помог мне с алгоритмом написания нарезчика бит.

В данный момент, проведя эксперименты и тесты, я понял что работает нарезчик достаточно медленно (~ +- 32 сек на массив unsigned char на 2 000 000 000 элементов, ~ +- 76 сек на массив unsigned short на 2 000 000 000 элементов и т.д.)

Собственно я и решил после этого что-то своё написать в надежде что битовые смещения работают побыстрее битовых масок (с учетом того, что в отличии от масок битовых смещениями я смогу получать сразу перечень данных), но как-то быстрее не стало, а только медленнее.

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

Прошу помощи в этом деле, может быть я где-то был не прав при написании или что-то ещё. Мне бы секунд до 10 - 20 при любых результатах...

Вот исходники нарезчика, алгоритм которого любезно предоставил уважаемый L0M:

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
    /*!
     * \class   BitsSlice
     * \brief   Битовый нарезчик данных.
     * \details ---
     */
    template <typename SourceDataType>
    class BitsSlice
    {
    private:
        /*!
         * \enum    SourceType
         * \brief   Перечисление с внутренними флагами входящих ресурсов для чтения.
         * \details ---
         */
        enum SourceType
        {
            VECTOR   = 1, ///< STL вектор.
            PTRARRAY = 2  ///< Указатель на данные.
        };
 
        SourceDataType     SequenceComponent; ///< Элемент STL вектора/массива указателей.
        unsigned long long int  CurrentIndex; ///< Индекс текущего элемента.
        std::vector<SourceDataType>  *Vector; ///< Указатель на ресурс STL вектора.
        SourceDataType             *PtrArray; ///< Указатель на данные.
        unsigned long long int          Size; ///< Размер ресурса.
        SourceType                      Flag; ///< Флаг вида ресурса.
        unsigned long long int      SizeBits; ///< Размер типа данных в битах.
        unsigned long long int BitIndexInSeq; ///< Битовый индекс текущего элемента.
        bool                           Order; ///< Порядок бит(FALSE - слева направо, TRUE - справа налево).
 
    public:
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор по умолчанию.
         * \details Удален.
         */
        BitsSlice() = delete;
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор копирования.
         * \details Удален.
         * \param   Object - объект класса.
         */
        BitsSlice(const BitsSlice<SourceDataType> &Object) = delete;
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор заполнения объекта.
         * \details Выполняет заполнение объекта с помощью ресурса представленного вектором STL.
         * \param   VectorData - STL вектор.
         * \param   BitOrder   - порядок бит.
         */
        BitsSlice(std::vector<SourceDataType> *VectorData, bool BitOrder = false);
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор заполнения объекта.
         * \details Выполняет заполнение объекта с помощью ресурса представленного указателем на данные.
         * \param   PtrArrayData - указатель на данные.
         * \param   SizeArray    - количество данные в указателе.
         * \param   BitOrder     - порядок бит.
         */
        BitsSlice(SourceDataType *PtrArrayData, const unsigned long long int SizeArray, bool BitOrder = false);
        /*!
         * \fn      ~BitsSlice
         * \brief   Деструктор.
         * \details ---
         */
       ~BitsSlice();
        /*!
         * \fn      JumpOverBeats
         * \brief   Перепрыгнуть на N бит вперед.
         * \details ---
         * \param   NumberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        bool JumpOverBeats(unsigned long long int NumberOfBits);
        /*!
         * \fn      CutBits
         * \brief   Отрезать N бит в буффер. Данные ресурса не уничтожаются.
         * \details ---
         * \param   Buffer       - ссылка на буфер.
         * \param   NumberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        template<typename BufferDataType>
        bool CutBits(BufferDataType &Buffer, unsigned long long int NumberOfBits);
    };
 
    template <typename SourceDataType>
    BitsSlice<SourceDataType>::BitsSlice(std::vector<SourceDataType> *VectorData, bool BitOrder)
    : SequenceComponent(0),
      CurrentIndex(1),
      Vector(VectorData),
      PtrArray(nullptr),
      Size(0),
      Flag(VECTOR),
      SizeBits(sizeof(SourceDataType) * 8u),
      BitIndexInSeq(sizeof(SourceDataType) * 8u),
      Order(BitOrder),
      BitBuffer("")
    {
        this->Size = this->Vector->size();
        this->SequenceComponent = this->Vector->at(0);
    }
 
    template <typename SourceDataType>
    BitsSlice<SourceDataType>::BitsSlice(SourceDataType *PtrArrayData, const unsigned long long int SizeArray, bool BitOrder)
    : SequenceComponent(0),
      CurrentIndex(1),
      Vector(nullptr),
      PtrArray(PtrArrayData),
      Size(SizeArray),
      Flag(PTRARRAY),
      SizeBits(sizeof(SourceDataType) * 8u),
      BitIndexInSeq(sizeof(SourceDataType) * 8u),
      Order(BitOrder),
      BitBuffer("")
    {
        this->SequenceComponent = this->PtrArrayData[0];
    }
 
    template <typename SourceDataType>
    BitsSlice<SourceDataType>::~BitsSlice()
    {
        this->SequenceComponent = 0;
        this->CurrentIndex      = 0;
        this->Vector            = nullptr;
        this->PtrArray          = nullptr;
        this->Size              = 0;
        this->SizeBits          = 0;
        this->BitIndexInSeq     = 0;
        this->BitBuffer         = "";
    }
 
    template <typename SourceDataType>
    bool BitsSlice<SourceDataType>::JumpOverBeats(unsigned long long int NumberOfBits)
    {
        if (NumberOfBits == 0)
            return true;
 
        else
        if ( !(NumberOfBits ^ BitIndexInSeq) )
        {
            this->BitIndexInSeq = 0;
            return true;
        }
        if (NumberOfBits < this->BitIndexInSeq)
        {
            this->BitIndexInSeq -= NumberOfBits;
            return true;
        }
        else
        {
            while(NumberOfBits > this->BitIndexInSeq)
            {
                if (Size >= CurrentIndex + 1)
                {
                    NumberOfBits -= this->BitIndexInSeq;
                    ++this->CurrentIndex;
                    this->BitIndexInSeq = this->SizeBits;
                }
                else
                    return false;
            }
 
            this->BitIndexInSeq -= NumberOfBits;
 
            switch(this->Flag)
            {
                case VECTOR:
                {
                    SequenceComponent = this->Vector->at(this->CurrentIndex);
                    break;
                }
                case PTRARRAY:
                {
                    SequenceComponent = this->PtrArray[this->CurrentIndex];
                    break;
                }
            }
            return true;
        }
    }
 
    template<typename SourceDataType>
    template<typename BufferDataType>
    bool BitsSlice<SourceDataType>::CutBits(BufferDataType &Buffer, unsigned long long int NumberOfBits)
    {
        if ((sizeof(BufferDataType) * 8u) < NumberOfBits || NumberOfBits == 0)
            return false;
 
        Buffer = 0;
        SourceDataType Mask = 0;
 
        while (NumberOfBits--)
        {
            Buffer <<= 1;
            if (this->BitIndexInSeq == 0)
            {
                if (!(this->CurrentIndex ^ this->Size) || (this->CurrentIndex > this->Size))
                    return false;
 
                switch(Flag)
                {
                    case VECTOR:
                    {
                        SequenceComponent = this->Vector->at(this->CurrentIndex);
                        break;
                    }
                    case PTRARRAY:
                    {
                        SequenceComponent = this->PtrArray[this->CurrentIndex];
                        break;
                    }
                }
                this->CurrentIndex++;
                this->BitIndexInSeq = this->SizeBits;
            }
            if (Order)
                Mask = 1 << (SizeBits - BitIndexInSeq);
            else
                Mask = 1 << (BitIndexInSeq - 1);
            Buffer |= (SequenceComponent & Mask) ? 1 : 0;
            --BitIndexInSeq;
        }
        return true;
    }

вот нарезчик который написал уже я:

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
247
248
    template <typename SourceDataType>
    class BitsSlice
    {
    private:
        /*!
         * \enum    SourceType
         * \brief   Перечисление с внутренними флагами входящих ресурсов.
         * \details ---
         */
        enum SourceType
        {
            Vector   = 1, ///< STL вектор.
            PtrArray = 2  ///< Указатель на данные.
        };
 
        SourceDataType              _sequenceComponent; ///< Элемент STL вектора/массива указателей.
        unsigned long long int           _currentIndex; ///< Индекс текущего элемента.
        std::vector<SourceDataType>           *_vector; ///< Указатель на ресурс STL вектора.
        SourceDataType                      *_ptrArray; ///< Указатель на данные.
        unsigned long long int                   _size; ///< Размер ресурса.
        SourceType                       _flagResource; ///< Флаг вида ресурса.
        unsigned int                       _sizeOfBits; ///< Размер типа данных в битах.
        unsigned int           _bitInSequenceComponent; ///< Остаток бит на текущий раунд.
        bool                                 _bitOrder; ///< Порядок бит(FALSE - слева направо, TRUE - справа налево).
 
    public:
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор по умолчанию.
         * \details Удален.
         */
        BitsSlice() = delete;
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор копирования.
         * \details Удален.
         * \param   object - объект класса.
         */
        BitsSlice(const BitsSlice<SourceDataType> &object) = delete;
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор заполнения объекта.
         * \details Выполняет заполнение объекта с помощью ресурса представленного вектором STL.
         * \param   vectorArray - STL вектор.
         * \param   bitOrder    - порядок бит.
         */
        BitsSlice(std::vector<SourceDataType> *vectorArray, bool bitOrder = false);
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор заполнения объекта.
         * \details Выполняет заполнение объекта с помощью ресурса представленного указателем на данные.
         * \param   ptrArray     - указатель на данные.
         * \param   arraySize    - количество данные в указателе.
         * \param   bitOrder     - порядок бит.
         */
        BitsSlice(SourceDataType *ptrArray, const unsigned long long int arraySize, bool bitOrder = false);
        /*!
         * \fn      ~BitsSlice
         * \brief   Деструктор.
         * \details ---
         */
       ~BitsSlice();
        /*!
         * \fn      jumpOverBeats
         * \brief   Перепрыгнуть на N бит вперед.
         * \details ---
         * \param   numberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        bool jumpOverBeats(unsigned int numberOfBits);
        /*!
         * \fn      cutBits
         * \brief   Отрезать N бит в буффер. Данные ресурса не уничтожаются.
         * \details ---
         * \param   buffer       - ссылка на буфер.
         * \param   numberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits);
 
    private:
        /*!
         * \fn      getCurrentSequenceComponent
         * \brief   Получить элемент STL вектора/массива указателей по текущему индексу.
         * \details ---
         * \return  bool - TRUE - успешное выполнение функции.
         */
        bool getCurrentSequenceComponent();
    };
 
    template <typename SourceDataType>
    BitsSlice<SourceDataType>::BitsSlice(std::vector<SourceDataType> *vectorArray, bool bitOrder)
    : _sequenceComponent(0),
      _currentIndex(0),
      _vector(vectorArray),
      _ptrArray(nullptr),
      _size(0),
      _flagResource(Vector),
      _sizeOfBits(sizeof(SourceDataType) * 8u),
      _bitInSequenceComponent(sizeof(SourceDataType) * 8u),
      _bitOrder(bitOrder),
      _bitBuffer("")
    {
        this->_size              = this->_vector->size();
        this->_sequenceComponent = this->_vector->at(0);
    }
 
    template <typename SourceDataType>
    BitsSlice<SourceDataType>::BitsSlice(SourceDataType *ptrArray, const unsigned long long int arraySize, bool bitOrder)
    : _sequenceComponent(0),
      _currentIndex(0),
      _vector(nullptr),
      _ptrArray(ptrArray),
      _size(arraySize),
      _flagResource(PtrArray),
      _sizeOfBits(sizeof(SourceDataType) * 8u),
      _bitInSequenceComponent(sizeof(SourceDataType) * 8u),
      _bitOrder(bitOrder),
      _bitBuffer("")
    {
        this->_sequenceComponent = this->_ptrArray[0];
    }
 
    template <typename SourceDataType>
    BitsSlice<SourceDataType>::~BitsSlice()
    {
        this->_sequenceComponent      = 0;
        this->_currentIndex           = 0;
        this->_vector                 = nullptr;
        this->_ptrArray               = nullptr;
        this->_size                   = 0;
        this->_sizeOfBits             = 0;
        this->_bitInSequenceComponent = 0;
        this->_bitBuffer              = "";
    }
 
    template <typename SourceDataType>
    bool BitsSlice<SourceDataType>::jumpOverBeats(unsigned int numberOfBits)
    {
        if (numberOfBits <= this->_bitInSequenceComponent)
        {
            this->_bitInSequenceComponent -= numberOfBits;
            return true;
        }
        else
        {
            numberOfBits -= this->_bitInSequenceComponent;
 
            unsigned int сoefficient = numberOfBits / this->_sizeOfBits;
 
            numberOfBits -= сoefficient * this->_sizeOfBits;
            this->_currentIndex += сoefficient + 1;
            this->_bitInSequenceComponent = this->_sizeOfBits - numberOfBits;
 
            return this->getCurrentSequenceComponent();
        }
    }
 
    template<typename SourceDataType>
    template<typename BufferDataType>
    bool BitsSlice<SourceDataType>::cutBits(BufferDataType &buffer, unsigned int numberOfBits)
    {
        if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
            return false;
 
        unsigned int bitShiftLeft     = 0;
        unsigned int bitShiftRight    = 0;
 
        while(numberOfBits)
        {
            if (!this->_bitInSequenceComponent)
            {
                this->_bitInSequenceComponent = this->_sizeOfBits;
                ++this->_currentIndex;
            }
 
            if (!this->getCurrentSequenceComponent())
                return false;
 
            unsigned int bitCountsInRound =
                                 this->_bitInSequenceComponent <= numberOfBits
                               ? this->_bitInSequenceComponent
                               : numberOfBits;
 
            if (this->_bitOrder)
            {
                /* обратный порядок */
                bitShiftLeft  = this->_bitInSequenceComponent - bitCountsInRound;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
            }
            else
            {
                /* прямой порядок */
                bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
            }
 
            this->_sequenceComponent <<= bitShiftLeft;
            this->_sequenceComponent >>= bitShiftRight;
 
            buffer                       <<= bitCountsInRound;
            buffer                        |= this->_sequenceComponent;
            this->_bitInSequenceComponent -= bitCountsInRound;
            numberOfBits                  -= bitCountsInRound;
 
            if (this->_bitOrder && bitCountsInRound > 1)
            {
                bool flag      = bitCountsInRound % 2;
                bool flagBegin = false;
                bool flagEnd   = false;
                for (unsigned int index = 0; --bitCountsInRound; ++index)
                {
                    flagBegin = (buffer & (1 << index) ? true : false);
                    flagEnd   = (buffer & (1 << bitCountsInRound) ? true : false);
 
                    if ((flagBegin && !flagEnd) || (!flagBegin && flagEnd))
                    {
                        buffer ^= (1 << bitCountsInRound);
                        buffer ^= (1 << index);
                    }
 
                    if (!( (flag ? bitCountsInRound + 1 : bitCountsInRound) ^ (index + 1)))
                        break;
                }
            }
        }
        return true;
    }
 
    template <typename SourceDataType>
    bool BitsSlice<SourceDataType>::getCurrentSequenceComponent()
    {
        if (this->_currentIndex >= this->_size)
            return false;
 
        switch(this->_flagResource)
        {
            case Vector:
                this->_sequenceComponent = this->_vector->at(this->_currentIndex);
                break;
 
            case PtrArray:
                this->_sequenceComponent = this->_ptrArray[this->_currentIndex];
                break;
        }
        return true;
    }

замеры времени делал :

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Timer
{
private:
    using clock_t = std::chrono::high_resolution_clock;
    using second_t = std::chrono::duration<double, std::ratio<1> >;
 
    std::chrono::time_point<clock_t> m_beg;
 
public:
    Timer() : m_beg(clock_t::now())
    {
    }
 
    void reset()
    {
        m_beg = clock_t::now();
    }
 
    double elapsed() const
    {
        return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
    }
};

Заранее спасибо.

P.S.: Самое забавное что под дебагом мой нарезчик побыстрее будет (оптимизация творит чудеса...), а вот в релизе всё становится печально, результаты фиксированно в приделах 110 сек...

Добавлено через 2 часа 42 минуты
Сделал кое-какие изменения во втором нарезчике (который сам писал), а именно в функции cutBits, которая и требует оптимизации:

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
        /*!
         * \fn      cutBits
         * \brief   Отрезать N бит в буффер. Данные ресурса не уничтожаются.
         * \details ---
         * \param   buffer       - ссылка на буфер.
         * \param   numberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            unsigned int bitShiftLeft  = 0;
            unsigned int bitShiftRight = 0;
 
            while(numberOfBits)
            {
                if (!this->_bitInSequenceComponent)
                {
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                    ++this->_currentIndex;
                    if (!this->getCurrentSequenceComponent())
                        return false;
                }
 
                unsigned int bitCountsInRound =
                                     this->_bitInSequenceComponent <= numberOfBits
                                   ? this->_bitInSequenceComponent
                                   : numberOfBits;
 
                if (this->_bitOrder)
                {
                    /* обратный порядок */
                    bitShiftLeft  = this->_bitInSequenceComponent - bitCountsInRound;
                    bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                    (buffer <<= bitCountsInRound) |= (this->_sequenceComponent << bitShiftLeft) >> bitShiftRight;
                    this->_bitInSequenceComponent -= bitCountsInRound;
                    numberOfBits                  -= bitCountsInRound;
 
                    if (bitCountsInRound > 1)
                    {
                        bool flag      = bitCountsInRound % 2;
                        bool flagBegin(false);
                        bool flagEnd(false);
                        for (unsigned int index = 0; --bitCountsInRound; ++index)
                        {
                            flagBegin = buffer & (1 << index);
                            flagEnd   = buffer & (1 << bitCountsInRound);
 
                            if ((flagBegin && !flagEnd) || (!flagBegin && flagEnd))
                            {
                                buffer ^= 1 << bitCountsInRound;
                                buffer ^= 1 << index;
                            }
 
                            if (!( (flag ? bitCountsInRound + 1 : bitCountsInRound) ^ (index + 1)))
                                break;
                        }
                        /*
                        bool flag      = bitCountsInRound % 2;
                        bool flagBegin = false;
                        bool flagEnd   = false;
                        for (unsigned int index = 0; --bitCountsInRound; ++index)
                        {
                            flagBegin = buffer & (1 << index);
                            flagEnd   = buffer & (1 << bitCountsInRound);
 
                            if ((flagBegin && !flagEnd) || (!flagBegin && flagEnd))
                            {
                                buffer ^= (1 << bitCountsInRound);
                                buffer ^= (1 << index);
                            }
 
                            if (!( (flag ? bitCountsInRound + 1 : bitCountsInRound) ^ (index + 1)))
                                break;
                        }
                        */
                    }
 
                    continue;
                }
 
                /* прямой порядок */
                bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                (buffer <<= bitCountsInRound) |= (this->_sequenceComponent << bitShiftLeft) >> bitShiftRight;
                this->_bitInSequenceComponent -= bitCountsInRound;
                numberOfBits                  -= bitCountsInRound;
 
                continue;
            }
            return true;
        }

Буду рад любым предложениям по оптимизации.
Спасибо.

@oleg-m1973 · 20.03.2021, 22:18

Сообщение от Aringot

Прошу помощи в этом деле, может быть я где-то был не прав при написании или что-то ещё. Мне бы секунд до 10 - 20 при любых результатах...

Для начала - зачем ты делаешь внутри цикла switch и if по переменным, которые в этом цикле не изменяются? В частности вот это

Сообщение от Aringot

switch(Flag)
{
case VECTOR:

Это всё должно быть за циклами

@L0M · 20.03.2021, 22:32

Aringot, если уж меня не к ночи помянули, то все оптимизации начинаются с выявления "бутылочного горлышка". Что обычно делается профайлером. Это во-первых.

Во-вторых, попробуйте в вашей программе сделать всё то же самое, но без обработки. Т.е. нарезчик должен работать вхолостую: что получил, то и отдал. И посмотрите сколько это потребует времени на ваших тестовых данных. Может банально ввод-вывод тормозит?

В-третьих, конечно, пробуйте оптимизировать узкие места, найденные в п.1. Кстати, очень подозрительно, что дебаг у вас работает быстрее, чем релиз.

В-четвёртых, смотрите в сторону многопоточной обработки данных.

В-пятых, смотрите в сторону многопоточной обработки данных на GPU.

@Aringot · 20.03.2021, 22:34 **[ТС]**

Сообщение от oleg-m1973

Это всё должно быть за циклами

Тогда каким образом я получу следующий элемент, при условии, если я, допустим скормил нарезчику:

C++
1
2
std::vector<unsigned char> testMass(2000, 138);
BitsSlice<unsigned char> Slicer(&testMass);

но хочу получить:

C++
1
2
unsigned short buffer = 0x0000;
Slicer.cutBits(buffer, 12);

а, это уже больше чем

C++
1
sizeof(unsigned char) * 8u

, соответственно раундов получения будет несколько.

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

@oleg-m1973 · 20.03.2021, 22:37

Сообщение от Aringot

Тогда каким образом я получу следующий элемент, при условии, если я, допустим скормил нарезчику:

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

@Aringot · 20.03.2021, 22:48 **[ТС]**

Доброй ночи, L0M,

Сообщение от L0M

Во-вторых, попробуйте в вашей программе сделать всё то же самое, но без обработки.

Примерно таким образом тесты проводил:

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
int main()
{
    bool FILL_ORDER = false;
    std::vector<unsigned long long int> TestMass(2000000000, 1384245214124242);
    V1::BitsSlice<unsigned long long int> Slicer1(&TestMass, FILL_ORDER);
    V2::BitsSlice<unsigned long long int> Slicer2(&TestMass, FILL_ORDER);
 
    unsigned short Buffer = 0x00;
    unsigned int numberBits = 16;
    //Slicer1.JumpOverBeats(56);
    //Slicer2.jumpOverBeats(56);
    Timer t;
    t.reset();
    while(Slicer1.CutBits(Buffer, numberBits))
    {
        //std::cout << Slicer1.BufferToCStr(Buffer, numberBits) << " ";
        //Buffer = 0x00;
    }
    std::cout << std::endl << "Slicer1 = " << t.elapsed() << " sec." << std::endl;
    Buffer = 0x00;
    t.reset();
    while(Slicer2.cutBits(Buffer, numberBits))
    {
        //std::cout << Slicer2.bufferToCStr(Buffer, numberBits) << " ";
        //Buffer = 0x00;
    }
    std::cout << std::endl << "Slicer2 = " << t.elapsed() << " sec." << std::endl;
    return 0;
}

только тесты я проводил на разных типах данных:

C++
1
2
3
4
5
6
7
8
std::vector<unsigned char> TestMass(2000000000, 138);
...
std::vector<unsigned short int> TestMass(2000000000, 138);
...
std::vector<unsigned int> TestMass(2000000000, 138);
...
std::vector<unsigned long long int> TestMass(2000000000, 138);
...

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

Добавлено через 3 минуты
в своей реализации я узкое место нашёл:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
                        for (unsigned int index = 0; --bitCountsInRound; ++index)
                        {
                            flagBegin = buffer & (1 << index);
                            flagEnd   = buffer & (1 << bitCountsInRound);
 
                            if ((flagBegin && !flagEnd) || (!flagBegin && flagEnd))
                            {
                                buffer ^= 1 << bitCountsInRound;
                                buffer ^= 1 << index;
                            }
 
                            if (!( (flag ? bitCountsInRound + 1 : bitCountsInRound) ^ (index + 1)))
                                break;
                        }

этот цикл требуется чтобы инвертировать полученный кусок бит.

Добавлено через 4 минуты

Сообщение от oleg-m1973

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

Я конечно с Вами согласен, но в голову ничего не приходит, если это требует вынести что-то за цикл, разве что метки, но это уже как-то звучит не совсем хорошо.

@oleg-m1973 · 20.03.2021, 22:55

Сообщение от Aringot

Я конечно с Вами согласен, но в голову ничего не приходит, если это требует вынести что-то за цикл, разве что метки, но это уже как-то звучит не совсем хорошо.

Для этого случая дам подсказку

Сообщение от Aringot

switch(this->Flag)
{
case VECTOR:

std::array ничем не отличается от укзателя. Сделай просто

C++
1
2
3
4
5
6
   BitsSlice<SourceDataType>::BitsSlice(std::vector<SourceDataType> *VectorData, bool BitOrder)
    : SequenceComponent(0),
      CurrentIndex(1),
      Vector(VectorData),
      PtrArray(Vector.data()),
      Size(Vector.size()),

и тогда этот switch нахрен не будет нужен, как и Flag

@zayats80888 · 20.03.2021, 23:00

Сообщение от Aringot

в своей реализации я узкое место нашёл:

Там же в спецификации подсказка, что эффективно инвертировать биты в байте можно с помощью таблицы(массив uint8_t[256])

@Aringot · 20.03.2021, 23:02 **[ТС]**

oleg-m1973, вариант годный, а это, в таком случае, нивелирует необходимость держать в классе указатель на вектор, а лишь только на тип данных, ну и switch тоже выбросить можно будет, но необходимость проверки это никак не уберет, всё - таки мне необходимо убедиться что были получены все биты текущего элемента и, соответственно, получить следующий.

Добавлено через 2 минуты
zayats80888, вариант хороший, ну и для 1 байтового, ну и 2 байтового типа написать это дело можно, но чем дальше, тем страшнее.

@zayats80888 · 20.03.2021, 23:04

Сообщение от Aringot

Отрезать N бит в буффер.

А для чего? Данные уже нарезаны на блоки(например, для uint16_t это будут форматы 4444, 565, 5551 и т.д.) Вам нужно просто читать блок(стандартного размера) и распаковывать его.

@oleg-m1973 · 20.03.2021, 23:04

Сообщение от Aringot

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

Сообщение от Aringot

if (this->_bitOrder)
{
/* обратный порядок */

Это уже второй вопрос. Просто сделай два цикла - по одному для каждого из этих случаев. Чтобы не дублировать код, воспользуйся шаблонами.

@zayats80888 · 20.03.2021, 23:05

Сообщение от Aringot

ну и для 1 байтового, ну и 2 байтового типа написать это дело можно, но чем дальше, тем страшнее.

Не понял, а зачем для 2 и больше?

@Aringot · 20.03.2021, 23:10 **[ТС]**

Сообщение от zayats80888

Не понял, а зачем для 2 и больше?

Скорее я не до конца понял Вашу идею, как-то статическими таблицами не доводилось пользоваться.

@zayats80888 · 20.03.2021, 23:14

Сообщение от Aringot

Скорее я не до конца понял Вашу идею, как-то статическими таблицами не доводилось пользоваться.

Что там сложного? Просто заполняеете этот массив, где table[n] хранит инвертированный порядок бит для значения n. Нужно инвертировать 2-байтовое значение? Инвертируете биты в каждом байте с помощью таблицы и переставляете сами байты.

@L0M · 20.03.2021, 23:20

Сообщение от Aringot

Во-вторых, попробуйте в вашей программе сделать всё то же самое, но без обработки.

Сообщение от Aringot

Примерно таким образом тесты проводил:

Не, я имел ввиду, что бы CutBits() никакой обработки не делал: взял байт (или слово) из входного массива и сразу же его вернул в качестве результата. Тогда можно будет оценить по времени накладные расходы.

@Aringot · 21.03.2021, 15:56 **[ТС]**

oleg-m1973, сделал как вы и предлагали, но без шаблонов (т.к. до меня не дошло как я могу написать шаблон, который при определенных условиях строки генерирует, а при определенных нет, либо я Вас не так понял)
вот вариант с масками:

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
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned long long int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            SourceDataType mask(0);
 
            if (this->_bitOrder)
            {
                while (numberOfBits--)
                {
                    if (!this->_bitInSequenceComponent)
                    {
                        if (++this->_currentIndex >= this->_size)
                            return false;
 
                        this->_bitInSequenceComponent = this->_sizeOfBits;
                        this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
                    }
                    mask = 1ull << (this->_sizeOfBits - this->_bitInSequenceComponent);
                    buffer <<= 1;
                    buffer |= (this->_sequenceComponent & mask) ? 1 : 0;
                    --this->_bitInSequenceComponent;
                }
                return true;
            }
            while (numberOfBits--)
            {
                if (!this->_bitInSequenceComponent)
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                    this->_sequenceComponent = this->_ptrArray[this->_currentIndex];
                }
                mask = 1ull << (this->_bitInSequenceComponent - 1);
                buffer <<= 1;
                buffer |= (this->_sequenceComponent & mask) ? 1 : 0;
                --this->_bitInSequenceComponent;
            }
            return true;
        }

вот вариант со смещениями (без таблицы):

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
        /*!
         * \fn      cutBits
         * \brief   Отрезать N бит в буффер. Данные ресурса не уничтожаются.
         * \details ---
         * \param   buffer       - ссылка на буфер.
         * \param   numberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            unsigned long long int bitShiftLeft  = 0;
            unsigned long long int bitShiftRight = 0;
 
            if (this->_bitOrder)
            {
                //обратный порядок
                while(numberOfBits)
                {
                    if (!this->_bitInSequenceComponent)
                    {
                        if (++this->_currentIndex >= this->_size)
                            return false;
 
                        this->_bitInSequenceComponent = this->_sizeOfBits;
                    }
                    this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
 
                    unsigned int bitCountsInRound =
                                         this->_bitInSequenceComponent <= numberOfBits
                                       ? this->_bitInSequenceComponent
                                       : numberOfBits;
 
                    bitShiftLeft  = this->_bitInSequenceComponent - bitCountsInRound;
                    bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                    this->_sequenceComponent <<= bitShiftLeft;
                    this->_sequenceComponent >>= bitShiftRight;
 
                    buffer <<= bitCountsInRound;
                    buffer |= this->_sequenceComponent;
 
                    this->_bitInSequenceComponent -= bitCountsInRound;
                    numberOfBits                  -= bitCountsInRound;
 
                    if (bitCountsInRound > 1)
                    {
                        bool flag      = bitCountsInRound % 2;
                        bool flagBegin(false);
                        bool flagEnd(false);
                        for (unsigned int index = 0; --bitCountsInRound; ++index)
                        {
                            flagBegin = buffer & (1 << index);
                            flagEnd   = buffer & (1 << bitCountsInRound);
 
                            if ((flagBegin && !flagEnd) || (!flagBegin && flagEnd))
                            {
                                buffer ^= 1 << bitCountsInRound;
                                buffer ^= 1 << index;
                            }
 
                            if (!( (flag ? bitCountsInRound + 1 : bitCountsInRound) ^ (index + 1)))
                                break;
                        }
                    }
 
                    continue;
                }
                return true;
            }
            //прямой порядок
            while(numberOfBits)
            {
                if (!this->_bitInSequenceComponent)
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                }
                this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
 
                unsigned int bitCountsInRound =
                                     this->_bitInSequenceComponent <= numberOfBits
                                   ? this->_bitInSequenceComponent
                                   : numberOfBits;
 
                bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                this->_sequenceComponent <<= bitShiftLeft;
                this->_sequenceComponent >>= bitShiftRight;
 
                buffer <<= bitCountsInRound;
                buffer |= this->_sequenceComponent;
 
                this->_bitInSequenceComponent -= bitCountsInRound;
                numberOfBits                  -= bitCountsInRound;
 
                continue;
            }
            return true;
        }

вот вариант со смещениями и таблицей (как предложил сделать zayats80888):

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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
    template <typename SourceDataType>
    class BitsSlice
    {
    private:
        SourceDataType              _sequenceComponent; ///< Элемент STL вектора/массива указателей.
        unsigned long long int           _currentIndex; ///< Индекс текущего элемента.
        const SourceDataType                *_ptrArray; ///< Указатель на данные.
        unsigned long long int                   _size; ///< Размер ресурса.
        unsigned int                       _sizeOfBits; ///< Размер типа данных в битах.
        unsigned int           _bitInSequenceComponent; ///< Остаток бит на текущий раунд.
        bool                                 _bitOrder; ///< Порядок бит(FALSE - слева направо, TRUE - справа налево).
        std::string                         _bitBuffer; ///< Битовый буфер в виде STL строки.
 
        static const unsigned char _reverseBitTable[256];
 
    public:
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор по умолчанию.
         * \details Удален.
         */
        BitsSlice() = delete;
 
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор копирования.
         * \details Удален.
         * \param   object - объект класса.
         */
        BitsSlice(const BitsSlice<SourceDataType> &object) = delete;
 
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор заполнения объекта.
         * \details Выполняет заполнение объекта с помощью ресурса представленного вектором STL.
         * \param   vectorArray - STL вектор.
         * \param   bitOrder    - порядок бит.
         */
        BitsSlice(const std::vector<SourceDataType> &vectorArray, bool bitOrder = false)
        : _sequenceComponent(0),
          _currentIndex(0),
          _ptrArray(vectorArray.data()),
          _size(vectorArray.size()),
          _sizeOfBits(sizeof(SourceDataType) * 8u),
          _bitInSequenceComponent(sizeof(SourceDataType) * 8u),
          _bitOrder(bitOrder),
          _bitBuffer("")
        {
            this->_sequenceComponent = this->_ptrArray[0];
        }
 
        /*!
         * \fn      BitsSlice
         * \brief   Конструктор заполнения объекта.
         * \details Выполняет заполнение объекта с помощью ресурса представленного указателем на данные.
         * \param   ptrArray - указатель на данные.
         * \param   size     - количество данные в указателе.
         * \param   bitOrder - порядок бит.
         */
        BitsSlice(const SourceDataType *ptrArray, const unsigned long long int size, bool bitOrder = false)
        : _sequenceComponent(0),
          _currentIndex(0),
          _ptrArray(ptrArray),
          _size(size),
          _sizeOfBits(sizeof(SourceDataType) * 8u),
          _bitInSequenceComponent(sizeof(SourceDataType) * 8u),
          _bitOrder(bitOrder),
          _bitBuffer("")
        {
            this->_sequenceComponent = this->_ptrArray[0];
        }
 
        /*!
         * \fn      ~BitsSlice
         * \brief   Деструктор.
         * \details ---
         */
       ~BitsSlice()
        {
            this->_sequenceComponent      = 0;
            this->_currentIndex           = 0;
            this->_ptrArray               = nullptr;
            this->_size                   = 0;
            this->_sizeOfBits             = 0;
            this->_bitInSequenceComponent = 0;
            this->_bitBuffer              = "";
        }
 
        /*!
         * \fn      jumpOverBeats
         * \brief   Перепрыгнуть на N бит вперед.
         * \details ---
         * \param   numberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        bool jumpOverBeats(unsigned int numberOfBits)
        {
            if (numberOfBits <= this->_bitInSequenceComponent)
            {
                this->_bitInSequenceComponent -= numberOfBits;
                return true;
            }
            else
            {
                numberOfBits -= this->_bitInSequenceComponent;
 
                unsigned int сoefficient = numberOfBits / this->_sizeOfBits;
 
                numberOfBits -= сoefficient * this->_sizeOfBits;
                this->_currentIndex += сoefficient + 1;
                this->_bitInSequenceComponent = this->_sizeOfBits - numberOfBits;
 
                if (this->_currentIndex >= this->_size)
                    return false;
 
                this->_sequenceComponent = this->_ptrArray[this->_currentIndex];
                return true;
            }
        }
 
        /*!
         * \fn      cutBits
         * \brief   Отрезать N бит в буффер. Данные ресурса не уничтожаются.
         * \details ---
         * \param   buffer       - ссылка на буфер.
         * \param   numberOfBits - количество бит.
         * \return  bool         - TRUE - успешное выполнение функции.
         */
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            unsigned long long int bitShiftLeft  = 0;
            unsigned long long int bitShiftRight = 0;
 
            if (this->_bitOrder)
            {
                //обратный порядок
                while(numberOfBits)
                {
                    if (!this->_bitInSequenceComponent)
                    {
                        if (++this->_currentIndex >= this->_size)
                            return false;
 
                        this->_bitInSequenceComponent = this->_sizeOfBits;
                    }
                    this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
                    this->reverseBitsInByts();
 
                    unsigned int bitCountsInRound =
                                         this->_bitInSequenceComponent <= numberOfBits
                                       ? this->_bitInSequenceComponent
                                       : numberOfBits;
 
                    bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                    bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                    this->_sequenceComponent <<= bitShiftLeft;
                    this->_sequenceComponent >>= bitShiftRight;
 
                    buffer <<= bitCountsInRound;
                    buffer |= this->_sequenceComponent;
 
                    this->_bitInSequenceComponent -= bitCountsInRound;
                    numberOfBits                  -= bitCountsInRound;
 
                    continue;
                }
                return true;
            }
            //прямой порядок
            while(numberOfBits)
            {
                if (!this->_bitInSequenceComponent)
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                }
                this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
 
                unsigned int bitCountsInRound =
                                     this->_bitInSequenceComponent <= numberOfBits
                                   ? this->_bitInSequenceComponent
                                   : numberOfBits;
 
                bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                this->_sequenceComponent <<= bitShiftLeft;
                this->_sequenceComponent >>= bitShiftRight;
 
                buffer <<= bitCountsInRound;
                buffer |= this->_sequenceComponent;
 
                this->_bitInSequenceComponent -= bitCountsInRound;
                numberOfBits                  -= bitCountsInRound;
 
                continue;
            }
            return true;
        }
 
        /*!
         * \fn      bufferToSTLStr
         * \brief   Возвращает копию битового буфера в виде строки.
         * \details ---
         * \param   buffer       - буфер.
         * \param   numberOfBits - количество бит из буфера.
         * \param   bitOrder     - порядок бит.
         * \return  std::string  - буфер в виде STL строки.
         */
        template<typename BufferDataType>
        std::string bufferToSTLStr(const BufferDataType &buffer, unsigned int numberOfBits, bool bitOrder = false)
        {
            this->bufferToStr(buffer, numberOfBits, bitOrder);
            return this->_bitBuffer;
        }
 
        /*!
         * \fn      bufferToCStr
         * \brief   Возвращает битовый буфер в виде C строки.
         * \details Константный указатель на C строку станет невалидным после вызова деструктора. Рекомендация: сделать копию. make a copy.
         * \param   buffer       - ссылка на буфер.
         * \param   numberOfBits - количество бит из буфера.
         * \param   bitOrder     - порядок бит.
         * \return  const char * - буфер в виде C строки.
         */
        template<typename BufferDataType>
        const char *bufferToCStr(const BufferDataType &buffer, unsigned int numberOfBits, bool bitOrder = false)
        {
            this->bufferToStr(buffer, numberOfBits, bitOrder);
            return this->_bitBuffer.c_str();
        }
 
    private:
        /*!
         * \fn      bufferToStr
         * \brief   Записывает биты из буфера во внутренний строковый буфер.
         * \details ---
         * \param   buffer       - ссылка на буфер.
         * \param   numberOfBits - количество бит из буфера.
         * \param   bitOrder     - порядок бит.
         */
        template<typename BufferDataType>
        void bufferToStr(const BufferDataType &buffer, unsigned int numberOfBits, bool bitOrder = false);
 
        void reverseBitsInByts()
        {
            if (!(8 ^ this->_sizeOfBits))
            {
                this->_sequenceComponent = this->_reverseBitTable[this->_sequenceComponent];
                return;
            }
            unsigned char begin  = 0;
            unsigned char end    = sizeof(SourceDataType);
            unsigned char *bytes = reinterpret_cast<unsigned char *>(&this->_sequenceComponent);
            for (;;)
            {
                --end;
                bytes[begin] = this->_reverseBitTable[bytes[begin]];
                bytes[end]   = this->_reverseBitTable[bytes[end]];
                bytes[begin] ^= bytes[end];
                bytes[end]   ^= bytes[begin];
                bytes[begin] ^= bytes[end];
                ++begin;
                if (!(begin ^ end))
                    break;
            }
 
        }
    };
 
template <typename SourceDataType>
const unsigned char BitsSlice<SourceDataType>::_reverseBitTable[256] =
{
    0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
    0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
    0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
    0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
    0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
    0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
    0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
    0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
    0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
    0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
    0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
    0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
    0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
    0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
    0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
    0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
};

L0M, надеюсь Вы имели ввиду что-то вроде этого:

C++
1
2
3
4
5
6
7
8
9
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if (++this->_currentIndex >= this->_size)
                return false;
                
            buffer = this->_ptrArray[this->_currentIndex - 1];
            return true;
        }

замеры ещё не делал, как сделаю - обновлю тему.

@Aringot · 21.03.2021, 21:26 **[ТС]**

На момент тестов функции трех вариаций нарезчиков имеют следующий вид:
Нарезчик (маски):

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
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned long long int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            SourceDataType mask(0);
 
            if (this->_bitOrder)
            {
                while (numberOfBits--)
                {
                    if (!this->_bitInSequenceComponent)
                    {
                        if (++this->_currentIndex >= this->_size)
                            return false;
 
                        this->_bitInSequenceComponent = this->_sizeOfBits;
                        this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
                    }
                    mask = static_cast<SourceDataType>(1ull << (this->_sizeOfBits - this->_bitInSequenceComponent));
                    buffer <<= 1;
                    buffer |= (this->_sequenceComponent & mask) ? 1 : 0;
                    --this->_bitInSequenceComponent;
                }
                return true;
            }
            while (numberOfBits--)
            {
                if (!this->_bitInSequenceComponent)
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                    this->_sequenceComponent = this->_ptrArray[this->_currentIndex];
                }
                mask = static_cast<SourceDataType>(1ull << (this->_bitInSequenceComponent - 1ull));
                buffer <<= 1;
                buffer |= (this->_sequenceComponent & mask) ? 1 : 0;
                --this->_bitInSequenceComponent;
            }
            return true;
        }

Нарезчик (битовые сдвиги):

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
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            unsigned long long int bitShiftLeft  = 0;
            unsigned long long int bitShiftRight = 0;
 
            if (this->_bitOrder)
            {
                //обратный порядок
                while(numberOfBits)
                {
                    if (!this->_bitInSequenceComponent)
                    {
                        if (++this->_currentIndex >= this->_size)
                            return false;
 
                        this->_bitInSequenceComponent = this->_sizeOfBits;
                    }
                    this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
 
                    unsigned int bitCountsInRound =
                                         this->_bitInSequenceComponent <= numberOfBits
                                       ? this->_bitInSequenceComponent
                                       : numberOfBits;
 
                    bitShiftLeft  = this->_bitInSequenceComponent - bitCountsInRound;
                    bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                    this->_sequenceComponent <<= bitShiftLeft;
                    this->_sequenceComponent >>= bitShiftRight;
                    (buffer <<= bitCountsInRound) |= this->_sequenceComponent;
 
                    this->_bitInSequenceComponent -= bitCountsInRound;
                    numberOfBits                  -= bitCountsInRound;
 
                    if (bitCountsInRound > 1)
                    {
                        bool flag = bitCountsInRound % 2;
                        bool flagBegin(false);
                        bool flagEnd(false);
                        for (unsigned long long int index = 0; --bitCountsInRound; ++index)
                        {
                            flagBegin = buffer & (1ull << index);
                            flagEnd   = buffer & (1ull << bitCountsInRound);
 
                            if ((flagBegin && !flagEnd) || (!flagBegin && flagEnd))
                            {
                                buffer ^= 1ull << bitCountsInRound;
                                buffer ^= 1ull << index;
                            }
 
                            if (!( (flag ? bitCountsInRound + 1 : bitCountsInRound) ^ (index + 1)))
                                break;
                        }
                    }
                    continue;
                }
                return true;
            }
            //прямой порядок
            while(numberOfBits)
            {
                if (!this->_bitInSequenceComponent)
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                }
                this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
 
                unsigned int bitCountsInRound =
                                     this->_bitInSequenceComponent <= numberOfBits
                                   ? this->_bitInSequenceComponent
                                   : numberOfBits;
 
                bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                this->_sequenceComponent <<= bitShiftLeft;
                this->_sequenceComponent >>= bitShiftRight;
                (buffer <<= bitCountsInRound) |= this->_sequenceComponent;
 
                this->_bitInSequenceComponent -= bitCountsInRound;
                numberOfBits                  -= bitCountsInRound;
 
                continue;
            }
            return true;
        }

Нарезчик (битовые сдвиги + таблица):

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
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            unsigned long long int bitShiftLeft  = 0;
            unsigned long long int bitShiftRight = 0;
            SourceDataType         tempSequence  = 0;
 
            if (this->_bitOrder)
            {
                //обратный порядок
                while(numberOfBits)
                {
                    if (!this->_bitInSequenceComponent)
                    {
                        if (++this->_currentIndex >= this->_size)
                            return false;
 
                        this->_bitInSequenceComponent = this->_sizeOfBits;
                        this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
                        this->reverseBitsInByts();
                    }
                    tempSequence = this->_sequenceComponent;
 
                    unsigned int bitCountsInRound =
                                         this->_bitInSequenceComponent <= numberOfBits
                                       ? this->_bitInSequenceComponent
                                       : numberOfBits;
 
                    bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                    bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                    tempSequence <<= bitShiftLeft;
                    tempSequence >>= bitShiftRight;
                    (buffer <<= bitCountsInRound) |= tempSequence;
 
                    this->_bitInSequenceComponent -= bitCountsInRound;
                    numberOfBits                  -= bitCountsInRound;
 
                    continue;
                }
                return true;
            }
            //прямой порядок
            while(numberOfBits)
            {
                if (!this->_bitInSequenceComponent)
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                    this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
                }
                tempSequence = this->_sequenceComponent;
 
                unsigned int bitCountsInRound =
                                     this->_bitInSequenceComponent <= numberOfBits
                                   ? this->_bitInSequenceComponent
                                   : numberOfBits;
 
                bitShiftLeft  = this->_sizeOfBits - this->_bitInSequenceComponent;
                bitShiftRight = this->_sizeOfBits - bitCountsInRound;
 
                tempSequence <<= bitShiftLeft;
                tempSequence >>= bitShiftRight;
                (buffer <<= bitCountsInRound) |= tempSequence;
 
                this->_bitInSequenceComponent -= bitCountsInRound;
                numberOfBits                  -= bitCountsInRound;
 
                continue;
            }
            return true;
        }

Холостые тесты на 4 типах данных на 2 000 000 000 элементах провел на:

C++
1
2
3
4
5
6
7
8
9
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int/* numberOfBits*/)
        {
            if (++this->_currentIndex >= this->_size)
                return false;
 
            buffer = this->_ptrArray[this->_currentIndex - 1];
            return true;
        }

Результаты тестов:

C++
1
std::vector<unsigned char>

0.67143 сек.

C++
1
std::vector<unsigned short int>

0.665286 сек.

C++
1
std::vector<unsigned int>

0.698397 сек.

C++
1
std::vector<unsigned long long int>

0.646304сек.

Тесты на полноценных функция во вложениях.

@Aringot · 21.03.2021, 23:58 **[ТС]**

Будут ли какие - нибудь предложения по корректировке уже написанного или что-либо ещё ?

@L0M · 22.03.2021, 15:24

Сообщение от Aringot

Будут ли какие - нибудь предложения по корректировке уже написанного или что-либо ещё ?

Исходя из скриншотов, второй вариант - фтопку. Можно скомбинировать варианты 1 и 3: для одного бита использовать вариант 1, для всех остальных - вариант 3.

Ну и в пп. 4 и 5 в #3 я вам уже писал, куда можно двигаться дальше.

@Aringot · 22.03.2021, 15:39 **[ТС]**

Добрый день, L0M, по поводу комбинирования вариантов - наверное это не самая лучшая идея, она ведь повлечет появления ветвления уже на начальных этапах, конечно это можно протестировать, но у меня на этот счет сомнения.

Вот самый быстрый и короткий в написании вариант(не считая варианта с 1 битом, но и там разрыв не такой уж и большой):

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
        template<typename BufferDataType>
        bool cutBits(BufferDataType &buffer, unsigned int numberOfBits)
        {
            if ((sizeof(BufferDataType) * 8u) < numberOfBits || !numberOfBits)
                return false;
 
            SourceDataType         tempSequence(0);
 
            //обратный и прямой порядок бит
            while(numberOfBits)
            {
                if (!(0 ^ this->_bitInSequenceComponent))
                {
                    if (++this->_currentIndex >= this->_size)
                        return false;
 
                    this->_bitInSequenceComponent = this->_sizeOfBits;
                    this->_sequenceComponent      = this->_ptrArray[this->_currentIndex];
 
                    if (this->_bitOrder)
                        this->reverseBitsInByts();
                }
 
                tempSequence = this->_sequenceComponent;
 
                unsigned int bitCountsInRound
                                   = this->_bitInSequenceComponent <= numberOfBits
                                   ? this->_bitInSequenceComponent
                                   : numberOfBits;
 
                (buffer <<= bitCountsInRound) |=
                ((tempSequence <<= (this->_sizeOfBits - this->_bitInSequenceComponent))
                               >>= (this->_sizeOfBits - bitCountsInRound));
 
                this->_bitInSequenceComponent -= bitCountsInRound;
                numberOfBits                  -= bitCountsInRound;
            }
            return true;
        }

По поводу многопоточности - проще сказать чем сделать, лично я не вижу возможностей для распараллеливания.

Добавлено через 8 минут
Всем спасибо за подсказки.
oleg-m1973, если заглянете в эту тему, то напишите пожалуйста что Вы тогда имели ввиду говоря о шаблоне к функции? Не совсем понял о чем вы, толи про вариативный шаблон, толи ещё про что-то.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@L0M Мозгоправ 1745 / 1039 / 468 Регистрация: 01.10.2018 Сообщений: 2,138 Записей в блоге: 2
	20.03.2021, 22:32
	Aringot, если уж меня не к ночи помянули, то все оптимизации начинаются с выявления "бутылочного горлышка". Что обычно делается профайлером. Это во-первых. Во-вторых, попробуйте в вашей программе сделать всё то же самое, но без обработки. Т.е. нарезчик должен работать вхолостую: что получил, то и отдал. И посмотрите сколько это потребует времени на ваших тестовых данных. Может банально ввод-вывод тормозит? В-третьих, конечно, пробуйте оптимизировать узкие места, найденные в п.1. Кстати, очень подозрительно, что дебаг у вас работает быстрее, чем релиз. В-четвёртых, смотрите в сторону многопоточной обработки данных. В-пятых, смотрите в сторону многопоточной обработки данных на GPU. 0

@Aringot 2 / 2 / 0 Регистрация: 24.05.2016 Сообщений: 88
	20.03.2021, 23:02 [ТС]
	oleg-m1973, вариант годный, а это, в таком случае, нивелирует необходимость держать в классе указатель на вектор, а лишь только на тип данных, ну и switch тоже выбросить можно будет, но необходимость проверки это никак не уберет, всё - таки мне необходимо убедиться что были получены все биты текущего элемента и, соответственно, получить следующий. Добавлено через 2 минуты zayats80888, вариант хороший, ну и для 1 байтового, ну и 2 байтового типа написать это дело можно, но чем дальше, тем страшнее. 0

@Aringot 2 / 2 / 0 Регистрация: 24.05.2016 Сообщений: 88
	21.03.2021, 23:58 [ТС]
	Будут ли какие - нибудь предложения по корректировке уже написанного или что-либо ещё ? 0