This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
dev:event_data_structure [2020/01/11 19:13] – chaot | dev:event_data_structure [2020/01/11 23:56] (current) – chaot | ||
---|---|---|---|
Line 3: | Line 3: | ||
This page is to make a suggestion for a new events data structure to achieve the following goals: | This page is to make a suggestion for a new events data structure to achieve the following goals: | ||
* avoid the usage of std::list | * avoid the usage of std::list | ||
- | * store events such that we can quickly retrieve the k-th last event for a specific instrument (for fixed k) | + | * store events such that we can quickly retrieve the k-th last event for a specific instrument (for variable |
* generally make this part of the code more beautiful and usable | * generally make this part of the code more beautiful and usable | ||
+ | |||
+ | === Abstraction === | ||
+ | |||
+ | Currently we just use a plain std:: | ||
+ | |||
+ | === Replacement of std::list === | ||
+ | |||
+ | As the events don't need to be in a specific order, we can replace std::list by a std::vector using a standard technique of swapping the element to be removed to the back and doing a pop_back(). This is only possible if the swapping is cheap. Currently the std::list contains pointers, so swapping is cheap. Also Event contains only some bytes (something around 30 maybe), so swapping is also still reasonably cheap. | ||
+ | |||
+ | === Access to the k-th last event === | ||
+ | |||
+ | To access the k-th last event, we have two extreme (with respect to running time and memory tradeoff) options: | ||
+ | * for each instrument store its last events | ||
+ | * just give IDs to each event and then linearly search for the k-th largest ID | ||
+ | |||
+ | If we know that we only need the query for the k-th last event for specific instruments, | ||
+ | |||
+ | === Misc Comments === | ||
+ | |||
+ | * The list currently contains pointers because of polymorphism of Event. | ||
+ | * IRC conversation: | ||
+ |