ddekany commented on PR #97: URL: https://github.com/apache/freemarker/pull/97#issuecomment-1793876693
How to accelerate this further: My idea is this. We can accelerate accessing elements sequentially, by index, with keeping the current data structure. The current data structure is (assuming I remember correctly) such that the concatenation result is a TemplateSequenceModel, which is a the root node of an unbalanced binary tree, where each nodes itself is TempalteSequenceModel that stores a left- and right-sequence (and with this PR now also their sizes). We could maintain a cursor in the root node. This cursor stores the path in the tree, from its root, to the last element that we had to retrieved. The path is just a List of elements, where each element stores a reference to a tree node, and the left-most index of the sequence slice the node represents in the whole (root node) sequence. When a new element is get by index, we can navigate to it starting out from that cursor, and not from the root node. The cursor initally points to the root node. Then, accessing seq[0] is O(N) fo r the first time, but O(1) next time, as the cursor (the last element of the path) already points that element. Furthermore, accessing the next element (seq[1]) will also be O(1), since if the next index is out of the range for the current node, you just have to step back in the path (hence naviating to the parent node), and then down to the right node. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
