3 ms·
I wonder if it is worth it to create a hybrid data structure: A linked list of arrays. Say you'd tune it so each array fits in the L1 cache. You don't need a h
by hyperman1 8y ago
I wonder if it is worth it to create a hybrid data structure: A linked list of arrays. Say you'd tune it so each array fits in the L1 cache. You don't need a huge chunk of contiguous memory, but still gain most of the performance gains of arrays. Iteration gets a lot more complicated, of course.
- htfy96 8y agoIt's called unrolled linked list. (https://en.m.wikipedia.org/wiki/Unrolled_linked_list https://en.m.wikipedia.org/wiki/Unrolled_linked_list). Note that if you can make sure each chuck contains sqrt(N) elements, then you can achieve insertion/deletion/lookup in O(sqrt(N)) time