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

Question

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

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

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

Любые идеи?

Thx для всех ответа

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Answer 5

Что такое элемент таймера? Что в ней? Это просто значение, которое постоянно подсчитывается некоторым прерыванием таймера или некоторым сложным классом, возможно, с его собственным потоком, который делает выбор времени?

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

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

Rgds, Martin