какую структуру данных мне выбрать и почему

Question

Я пишу менеджер таймеров на C, который включает в себя:

• создание нового таймера
• удаление таймеров
• удаление мертвых таймеров
• таймеры замораживания
• и все остальное, о чем я еще не думал.

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

Есть идеи?

Спасибо за ответ

Answer 1

Вам не нужно ничего перестраивать при удалении из связанного списка.Это O(1) оп.Независимо от того, какую структуру вы выберете, вы, вероятно, должны быть осторожны с указателями.

Answer 2

Обычно массив использует минимальное количество памяти. Отдельный блок, поэтому меньше накладных расходов и нет накладных расходов на управление, как у следующих / предыдущих указателей в связанном списке.

Конечно, это менее эффективно по времени для удаления из начала / середины достаточно большого массива, чем для удаления данного узла из связанного списка, а также любые указатели / индексы в массиве больше не будут ссылаться на После того, как вы это сделали, вы должны быть осторожны, какие дескрипторы вы предоставляете пользователям API таймера и как вы находите данные таймера для конкретного дескриптора. Но если использование памяти действительно является единственной важной проблемой, то массив выигрывает.

Я делал что-то подобное раньше, и лично я бы начал со связанного списка, если он явно не потерпит какого-то конкретного ограничения. Массив указателей на структуры «timerdata» также может работать хорошо, если вы можете предотвратить слишком большой список активных таймеров.

Answer 3

Что такое элемент таймера? Что в нем? Это просто значение, которое постоянно отсчитывается каким-то прерыванием по таймеру или каким-то сложным классом, возможно, со своим собственным потоком, который выполняет синхронизацию?

Какие операции могут выполняться чаще всего? - оптимизировать доступ к ним в качестве приоритета.

Есть ли какое-либо преимущество при заказе списка, например. в порядке возрастания времени истечения, так что таймер тайм-аута всегда находится в начале списка (т. е. дельта-очередь).

Rgds, Martin

Answer 4

Вы можете использовать кучу / приоритетную очередь.Это имеет те же требования к памяти, что и массив, но вставка и удаление O (LG N) операций.Элементы в очереди могут быть упорядочены по времени до запуска каждого объекта таймера.Когда срабатывает реальный таймер, вам нужно настроить время срабатывания каждого другого таймера в списке.Таким образом, если timer1 настроен на отключение через 1 секунду, а timer2 настроен на отключение через 1,5 секунды, когда срабатывает таймер1, вам придется настроить таймер2 на отключение через 0,5 секунды.Может быть, что-то подобное?

Answer 5

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