ВходНаше всё Теги codebook PARTS Поиск Опросы Закон Пятница
27 ноября
/1046630
Топик полностью
fk0 (23.10.2020 20:49, просмотров: 169) в ответ на Да в принципе можно и так как вы пишите, но вместо односвязного списка - очередь упорядоченная по оставшемуся времени. Сортировка по времени происходит в момент добавления события. В момент обработки события событие выбрасывается, и головой очереди становится следующее. НО если нужно сформировать какую-то циклическую последовательной действий очень все это не красиво будет. - автор: Boвa
Проблема линейной очереди -- гигантское время вставки если в очереди 6144 таймеров, например. Кроме того API прикладного уровня может иметь, например, функцию остановки/отмены запущенного таймера. Т.е. нужны операции: 1) вставки в очередь, 2) извлечение из головы очереди, 3) удаление произвольного элемента. Бинарная куча выглядит диковато и перетряхивает вообще всю память, но у ней худшее время понятно. Есть вариант со скип-листами, но там удалить физически нельзя, только 

промаркировать как удалённый, что чревато нехваткой памяти (тебе в цикле создали и удалили 65536 таймеров...) и вообще нужен аллокатор какой-то, сложно. Возможный вариант по ссылке -- Pairing Heap. Но со сложными алгоритмами проблема, в том, что несмотря на высокие средние результаты, худший результат зачастую не понятен (а для условно, части RTOS, важен именно он...) Так что библиотека очень даже начинает иметь смысл.


https://habr.com/ru/post/470674

[ZX]
Ответить
Ответы