Вход
Наше всё
Теги
codebook
PARTS
Поиск
Опросы
Закон
Пятница
26 февраля
О смысле всего сущего
0xFF
Средства и методы разработки
Мобильная и беспроводная связь
Блошиный рынок
Объявления
Микроконтроллеры
ARM, RISC-V
AVR
PIC
PLD, FPGA, DSP
Кибернетика
Технологии
Схемы, платы, компоненты
Микроконтроллеры
/1046639
Топик полностью
lloyd
(23.10.2020 21:10, просмотров: 132)
в ответ на
Проблема линейной очереди -- гигантское время вставки если в очереди 6144 таймеров, например. Кроме того API прикладного уровня может иметь, например, функцию остановки/отмены запущенного таймера. Т.е. нужны операции: 1) вставки в очередь, 2) извлечение из головы очереди, 3) удаление произвольного элемента. Бинарная куча выглядит диковато и перетряхивает вообще всю память, но у ней худшее время понятно. Есть вариант со скип-листами, но там удалить физически нельзя, только
- автор:
fk0
Есть замечательная статья, расписывающая возможные подходы к организации списка таймеров
https://blog.acolyer.org/2015/11/23/hashed-and-hierarchical-timing-wheels/
Ответить
Ответы
"Simple Timing Wheels" -- это какой-то испорченный пересказ на тему bucket queue. Для которых известно, что они хорошо работают когда там распределение равномерное и/или число приоритетов -- небольшое. В нашем случае числа большие (32-битное время, например) и распределение явно не равномерное, все таймеры могут свалиться в один bucket. "Since there may be many timers in any given slot, we maintain an ordered list of timers for each slot..." -- и здесь мы возвращаемся к
fk0
(1897 знак.,
23.10.2020 22:28
,
ссылка
)