On 9/26/16 11:47 AM, Dan Douglas wrote:
> Would an array of pointers to structs of key-value pairs be better
> here? It should be faster in the common cases even though it may mean
> some wasted space and reallocs depending on how you decide to grow the
> array. A linear search through an array for an index should be faster
> than linked-list traversal. https://youtu.be/YQs6IC-vgmo (why every
> std::vector implementation uses arrays, really it's true of analogues
> in most non-functional langs).
I made a change that makes for-loop 2 nearly twice as fast as for-loop 1,
mostly because it avoids storing and retrieving variables.
>
> Also bash itself makes it hard to use sparse arrays efficiently regardless
> of the implementation. In the case of lists, one usually wants to address
> elements by ordinal position, but both the index in `arr[index]` and the
> offset in `${arr[@]:offset:length}` don't allow it, which means random
> insertion requires a linear search despite being linked-lists. That also
> makes the "length" inconsistent with everything else that looks at the
> value of the index, though at least length does what I really wish
> offset did.
So you want offset N to be the nth element in the array instead of the
element with index N? Huh. Well, you probably want another data structure.
In any event, random insertion can be optimized in the same way that
random access is.
--
``The lyf so short, the craft so long to lerne.'' - Chaucer
``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU c...@case.edu http://cnswww.cns.cwru.edu/~chet/
