Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.53/43: Рейтинг темы: голосов - 43, средняя оценка - 4.53
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84

Битстаффинг

03.08.2011, 19:51. Показов 9023. Ответов 21
Метки нет (Все метки)

Всем привет. Есть такой термин - Битстаффинг. Это бит-ориетированная процедура по вставке "0" после 5-ти последовательных "1". Сейчас моя реализация вполне себе работает. Принимает вектор битов, вставляет нули в нужном месте и возвращает вектор битов. Каждый бит занимает один байт. Кто нибудь знает как это можно ускорить? Можно даже добавлять "0" в существующем векторе, но операция "vector.insert", мне кажется будет полным убийством скорости работы. У кого какие варианты есть по оптимизации?

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
#include <iostream>
#include <stdio.h>
#include <vector>
 
class Zero_Insert {
 
private: unsigned short counter;
 
public: ~Zero_Insert(void){};
 
public: Zero_Insert(void)
        {
            Reset();
        };
 
public: void Reset(void)
        {
            counter=0;
        }
 
public: void Zeros_Insertion(vector <unsigned char> & InputVector, vector <unsigned char> & OutputVector)
        {
            
                        OutputVector.reserve(InputVector.size());
 
            for(int j = 0; j < InputVector.size(); j++)
            {
                if( InputVector[j] == 1 )
                {
                    counter++;
                }
                else
                {
                    counter=0;
                }
                OutputVector.push_back(InputVector[j]);
                if(counter==5){
                    OutputVector.push_back(0);
                    counter = 0;
                }
 
            }
        }
};
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
03.08.2011, 19:51
Ответы с готовыми решениями:

C\C++ Битстаффинг (Bitstuffing)
Добрый день, уважаемые господа и дамы. Стоит задача реализовать битстаффинг, забитстаффить инфу на одном компе, передать на другой,...

[Verilog] Битстаффинг и дестаффинг
Попытался я сымитировать битстаффинг (предупреждение появления последовательностей из 5 нулей или единиц) и возврат к исходным сигналам. ...


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

Или воспользуйтесь поиском по форуму:
21
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
04.08.2011, 23:03
Цитата Сообщение от snayperAlfa Посмотреть сообщение
bitset будет медленнее
Обоснуйте, пожалуйста. Если мы заговорили о векторе, значит автоматически подразумеваем, что удобство важнее скорости. Если же важна эффективность, тогда надо пользоваться массивами из целочисленных и битовыми операциями. Либо делать вставку на ассемблере, но тут зависит от прямоты рук.
0
2 / 2 / 1
Регистрация: 13.08.2008
Сообщений: 84
04.08.2011, 23:37  [ТС]
Важна скорость. Вектор - потому что неизвестно точное количество входных данных.
Ассемблер отпадает, ибо код будет выполняться на некой АРМ архитектуре.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ответ Создать тему
Новые блоги и статьи
24 Мат модель здравосохранения: функциональные требования к строительству пищеблока
anaschu 18.06.2026
СРесурсами1: финансовый SD-контур, калькулятор функциональных требований пищеблока Сегодня разделили затраты в агенте Экономика по образцу модели НАСОСЫ, добавили расчёт ROI и построили первый. . .
23. что сделано за последнее время.
anaschu 17.06.2026
• Эталон: Клиника НИИ питания РАМН, Москва — централизованный пищеблок, 225 коек, 180 пациентов • Git: репозиторий med2, ветка абсентеизм. Рабочий файл: СРесурсами1_v4. alp • Смежный проект:. . .
22. Подключение слоя системной динамики (потоковые диффуры): экономические метрики модели
anaschu 17.06.2026
Апдейт модели: финансовый контур, разделение затрат Продолжаю развивать модель рабочего коллектива на AnyLogic. В этот раз работа шла над агентом Экономика — финансовым SD-слоем модели. Задача:. . .
[golang] Insert Delete GetRandom O(1) (Leetcode: 380)
alhaos 16.06.2026
Insert Delete GetRandom O(1) Сложность: Medium Источник: LeetCode 380 Задача Реализовать структуру данных RandomizedSet, которая поддерживает следующие операции за O(1) в среднем:
Свет в конце тоннеля
kumehtar 16.06.2026
Поймал себя на одной мысли. Раньше мне всегда казалось неправильным жить без чёткого понимания, куда всё идёт. Будто я иду по дороге судьбы, но не знаю, куда она ведёт. А раз не знаю — значит,. . .
[golang] Реализация стека с поддержкой получения минимального элемента за O(1)
alhaos 16.06.2026
Min Stack Сложность: Medium Источник: LeetCode 155 Задача: Реализовать стек который поддерживает push, pop, top и получение минимального элемента за O(1). Методы:
[golang] Конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов.
alhaos 10.06.2026
Задача Реализовать конкурентный fetcher с ограничением максимального количества одновременных HTTP запросов. Сигнатура func Fetch(urls string, maxConcurrent int) Result Пример urls :=. . .
[golang] Состояние гонки (race condition)
alhaos 10.06.2026
Состояние гонки (race condition) Состояние гонки (Race Condition) — это ошибка, возникающая при одновременном доступе нескольких горутин к одним и тем же данным без должной синхронизации. При этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru