Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
TheNooob
0 / 0 / 0
Регистрация: 19.02.2018
Сообщений: 8
1

Кольцевой буффер

01.03.2018, 23:47. Просмотров 843. Ответов 3
Метки нет (Все метки)

Делаю задания с книги Algorithms, 4th Edition by Robert Sedgewick :

1.3.37 Кольцевой буфер.

Кольцевой или кольцевая очередь - это структура данных с правилом FIFO фиксированного размера N, удобная для передачи данных между асинхронными процессами или для хранения файлов журналов. Если буфер пуст, получатель ждет поступления в него данных; если буфер полон, отправитель ждет, когда можно будет поместить данные.
Разработайте API - интерфейс для типа RingBuffer и реализуйте его на основе массива.

Здесь для меня все понятно, кроме того как можно закольцевать массив, не лучше ли реализация на основе списка? Спасибо за внимание.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.03.2018, 23:47
Ответы с готовыми решениями:

Из Edit в буффер
Мне нужно, что бы при вводе пользователем данных в Edit ,данные копировались в буффер. Как это...

ADSP - цыклический буффер.
Есть задание: Организовать цыклический буффер в памьяти данных и занести туду данные с инкрементом...

ReadFile не пишет в буффер
ReadFile не читает файл с ошибкой ERROR_NOACCESS. Я так понимаю что проблема в буфере, но не знаю...

Запись в буффер и обработка
Люди добрые помогите переписать, дописать функцию обработки файла в буфере, у меня пока работает...

Сокеты, динамический буффер
Всем добрый день. Есть клиент и сервер, соединение устанавливается(winsock2). Задача - создать...

3
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,427
02.03.2018, 09:56 2
Цитата Сообщение от TheNooob Посмотреть сообщение
как можно закольцевать массив
Код
index = index % size
1
krapotkin
3587 / 3156 / 1087
Регистрация: 14.04.2014
Сообщений: 15,200
Записей в блоге: 15
02.03.2018, 13:43 3
Кольцевые списки
1
Fulcrum_013
1541 / 1187 / 138
Регистрация: 14.12.2014
Сообщений: 10,106
Завершенные тесты: 3
02.03.2018, 16:34 4
Лучший ответ Сообщение было отмечено TheNooob как решение

Решение

Shamil1, Это Wrap Around - т.е зацикливание самого индекса.
TheNooob, У кольцевого буфера(очереди) все веселее.
Т.е. имеется два указателя(индекса) - голова и хвост в начале равные нулю (указывают на первый элемент). При добавлении в буфер (очередь) новый элемент пишется в положение хвоста и хвост сдвигается на единицу вперед с учетом wrap around. При извлечении элемент извлекается из головы и вперед смещается голова тоже с учетом wrap around. Если голова догнала хвост то буфер пуст и их можно обнулить. Если хвост догнал голову то буфер переполнен.
Т.е. аналог закольцованной ленты с раздельными головками чтения и записи.

Добавлено через 8 минут
Цитата Сообщение от TheNooob Посмотреть сообщение
не лучше ли реализация на основе списка
Реализацию того же самого функционала на основе связного списка обычно можно расценивать как диверсию. Преимущество кольцевого буфера в том что он не требует перераспределения динамической памяти под элементы при их добавлении/извлечении, память распределяется один раз на старте использующей его системы. Используются такие буфера обычно в системах реального времени. Поэтому переполнение буфера (а тем более созданного с небольшим запасом)по условиям системы невозможно. Т.е. если под новый элемент в буфере нет места, то проблема не в том что места нет, а проблема в том что система не смогла отработать элементы очереди в заданный лимит времени и уже считается поломавшейся по определению системы реального времени.

Добавлено через 2 часа 11 минут
При использовании же кольцевого буфера в качестве журнала, считается что актуальными являются последние N записей, т.е. когда головка записи проходит по кругу она просто переписывает более старые записи которые уже неактуальны. Аналог - бортовой самописец (черный ящик). Лента рассчитана на продолжительность полета и закольцована. Т.е. данные накопленные в течение предыдущего полета просто переписываютсяя данными текущего полета, потому что в случае аварии данные предыдущего полета не актуальны, соответственно их можно просто переписать, что как экономит сам носитель так и исключает невозможность записи по причине "забыли заменить заполнившийся носитель при предполетной подготовке".
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.03.2018, 16:34

Правильно прочитать буффер recv
Мне для игры нужно посмотреть куда делается запрос на удаленный адрес, перехват будет позже. Сейчас...

Буффер из std::string c_str()
Здравствуйте! такое дело: Проект на Qt5 и С++11. Есть форма с полем ввода. Введённое содержимое...

Буффер пикселей и его сложение
У меня такой алгоритм: отрисовываю сцену, теоретически создаю буффер, наношу на него темный QUAD,...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru