event_queue: список или дерево?

Post by **AndreyB** » Fri Apr 25, 2014 2:39 pm

Планировщик https://svn.code.sf.net/p/rusefi/code/trunk/firmware/controllers/system/SingleTimerExecutor.cpp состоит из аппаратного таймера https://svn.code.sf.net/p/rusefi/code/trunk/firmware/hw_layer/microsecond_timer.c и очереди https://svn.code.sf.net/p/rusefi/code/trunk/firmware/controllers/algo/event_queue.cpp

У очереди три операции:
1) добавить задание в заданный момент времени
2) вернуть время слежующего события
3) выполнить все запланнированные на данный момент задания

Сейчас очередь написана с использованием списка https://svn.code.sf.net/p/rusefi/code/trunk/firmware/ext_algo/utlist.h
Количесвто событий в очереди у нас всегда будет достаточно небольшое (этак примерно 10), так что в принципе линейный алгоритм не будет большоё проблемой. Но всё-таки, по уму нужно переписать на дерево, а в идеале вообще провестим микро-тест и сравнить. Как вариант - http://en.cppreference.com/w/cpp/container/multimap

Никто не хочет заняться?

puff · Post by **puff** » Fri Apr 25, 2014 3:12 pm

при этом компилятор всё равно сделает по-своему?
а чем дерево лучше списка?
но тесты покажут, да…

Post by **AndreyB** » Fri Apr 25, 2014 3:16 pm

puff wrote:а чем дерево лучше списка?

Простого ответа тут нет, тут Вычислительная сложность список O(n), а дерево - O(log n)

puff · Post by **puff** » Fri Apr 25, 2014 3:33 pm

зато небось памяти отжирает…

rusefi.com