4 ms·
Looks like author never heard about single pointer double linked list. That could save him 2 pointers per each node. The idea: for simplicity taking list. sing
by numba888 2y ago
Looks like author never heard about single pointer double linked list. That could save him 2 pointers per each node.
The idea: for simplicity taking list. single pointer saved in the node is xor of next and previous nodes. When moving forward we xor current ptr with prev. Moving backward xor with next to get prev. That it. How do we get prev/next for xor? The only way to get in the middle of the list is using iterator. Which can hold one extra pointer. For the first/last nodes extra pointer is NULL.
The same for EB tree, as navigation can be done only using iterator it can hold extra pointer.
These are my $0.02, you are free to implement and use this algorithm. No fees, no references required.
- mmiao 2y agoBut we need extra computation to move forward/backward, which is not suitable for the problem
- deleted 2y ago[deleted]
- numba888 2y agoone xor, yes, but on most systems smaller memory footprint is better. there are many more nodes than iterators. so savings can be significant. another possible optimization is when 'key' fits in pointer or two. which is usually the case. wonder if r1 or 03 can do it, with the right instructions of course.
- numba888 2y ago> wonder if r1 or 03 can do it, with the right instructions of course. for o3-mini-high it's too difficult to write even simple ebt. not many implementations on the web to learn from(?) reasoning isn't strong enough for this. besides what it produced is very inefficient.