Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision
Previous revision
dev:event_data_structure [2020/01/11 19:09] – created chaotdev:event_data_structure [2020/01/11 23:56] (current) chaot
Line 1: Line 1:
-bla+====== Events Data Structure ====== 
 + 
 +This page is to make a suggestion for a new events data structure to achieve the following goals: 
 +  * avoid the usage of std::list 
 +  * store events such that we can quickly retrieve the k-th last event for a specific instrument (for variable k) 
 +  * generally make this part of the code more beautiful and usable 
 + 
 +=== Abstraction === 
 + 
 +Currently we just use a plain std::list<Event*>. Probably we should give it a dedicated type to make the code clearer and also facilitate future refactoring and avoiding bugs. I suggest EventsDS as the type name. 
 + 
 +=== 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, we can restrict storing this information to those instruments. 
 + 
 +=== Misc Comments === 
 + 
 +  * The list currently contains pointers because of polymorphism of Event. 
 +  * IRC conversation: [[https://www.drumgizmo.org/irc-logs/drumgizmo.log.2020_01_11|here]] 
dev/event_data_structure.1578766180.txt.gz · Last modified: 2020/01/11 19:09 by chaot
Trace:
GNU Free Documentation License 1.3
Valid CSS Driven by DokuWiki Recent changes RSS feed Valid XHTML 1.0