11–20 of 22 posts
Earlier quoted context omitted.
Is « cacheability » a property of the data structure or of the lookup algorithm?
Locality is a property of how data is arranged, so it's a property of the data structure, no?
Earlier quoted context omitted.
Is « cacheability » a property of the data structure or of the lookup algorithm?
Locality is a property of how data is arranged, so it's a property of the data structure, no?
> The main benefit of the Eytzinger layout is that all values needed for the first steps of the binary search are close together, so they can be cached efficiently: we put the root at index 1 and the two children of the node at index i are at 2i and 2i + 1. This is exactly what is done in good old binary heaps; though binary heaps do not maintain a balanced binary tree, only the property that key(parent) . Binary hea…
Is « cacheability » a property of the data structure or of the lookup algorithm?
Imagine, e.g., doing a b-tree lookup on a binary Eytzinger layout. You would always grab more cache lines than optimal. Even more obviously, consider an inorder traversal. The properties of an algorithm and data structure depend properly on both components.
Okay, but that's not even remotely like the kind of input that this tree was created for. From the next paragraph, this work is in part
> [...] to make efficient datastructures to index DNA [...]. One such datastructure is the suffix array, that sorts the suffixes of the input string. Classically, one can then find the locations where a string occurs by binary searching the suffix array.
So where is the analysis of how it performs for that use-case? Searching through "already sorted 32 bit numbers" has nothing to do with searching a 3 billion character string (that by definition cannot be internally sorted) for substrings.
Earlier quoted context omitted.
Locality is a property of how data is arranged, so it's a property of the data structure, no?
Data arrangement and data structure are the same word...
When we put the binary tree nodes into an array and move from the parent to children using indexing calculations, rather following pointers that could go anywhere, then it's an explicit part of the data structure.
> Input. A sorted list of 32bit unsigned integers vals: Vec . Okay, but that's not even remotely like the kind of input that this tree was created for. From the next paragraph, this work is in part > [...] to make efficient datastructures to index DNA [...]. One such datastructure is the suffix array, that sorts the suffixes of the input string. Classically, one can then find the locations where a string occurs by bi…