skip lists

[Peter Haworth]

On Sun, May 12, 2013 at 3:28 PM, Alex Tweedly <alex at tweedly.net> wrote:

> 1. Ranges.
> Arrays are really good at
>     Give me element N
> but not so good at
>     Give me all elements between N and M
>
> You can do "gets the keys; sort them; scan through (maybe using binary or
> similar search to speed that up). But this can be very inefficient for
> large data sets and small ranges, compared to skip-list or other optimized
> linked-list method. Of course, maybe you avoid that by keeping the keys in
> a separate variable already sorted - but that means extra work on updates,
> ...)
>
> Or you can do "repeat with i = N to M; if there is a variable Array[i]
> then ..." but that can be impossibly inefficient for sparse arrays.
>
> Or you can probably do something clever I haven't thought of :-)
>

A few months back, there was a great post that revealed what I think is a
little known way to reference array keys - if I'm not mistaken it was from
Dick Kriesel.  I have no idea how (in)efficient it might be compared to the
other methods mentioned but here's the technique again.

Basically, you can supply a numerically keyed array as the key of an array.
 So, in the example of getting all the keys between N and M, with N=10 and
M=15, you would build an array, let's call it tKeyA, with the following
keys and values:

1 -10
2- 11
3- 12
4- 13
5- 14
6- 15

To get those key values from an array tDataA, "put tDataA[tKeyA] into
tFilterA".  This works for alpha values of N and M too.

None of that really addresses the skip list technique but it's a useful
feature of arrays.

Pete
lcSQL Software <http://www.lcsql.com>