skip lists

[Alex Tweedly]

I think your description is correct but there are a couple of 
(categories of) cases where other considerations *may* apply.

(in this context of skip-lists, the data is sorted by some key(s))

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 :-)


2. Non-unique keys

You can't "simply write to an array" if the key isn't unique. Skip-lists 
can deal with non-unique keys (the description in Wikipedia doesn't 
fully, but it's easy to change that so it would).


Dealing with these cases, in LC you might want to use an array, but 
keyed by some (probably numeric ID), and have a separate data structure 
or additional per-element data to represent the sorted info. You could 
consider using skip-list nodes with the data part being the numeric ID 
of the array element for that extra data structure - though there are 
lots of other data structures I'd probably think of before that 
(doubly-linked list, head-linked list, ...)

btw - someone said on the list recently something like "Arrays should 
have an equivalent of the filter command". I completely agree, and if 
they did, then it might be an even better answer to many of the cases of 
ranges / non-unique value matching.

-- Alex.




On 12/05/2013 21:26, Geoff Canyon wrote:
> On Sat, May 11, 2013 at 5:20 PM, Richard Gaskin
> <ambassador at fourthworld.com>wrote:
>
>> Geoff Canyon wrote:
>>
>>> I'm curious why you'd want to do this?
>> Because I'm a madman. :)
>
> A perfectly fine reason, I've done many things for the same reason. In this
> instance, just to make sure there's nothing I'm overlooking, as far as I
> can see:
>
> In non-high-level languages:
> Linked lists, are compact and easy to write to. They don't have to allocate
> all storage space up front the way arrays do. They're slow to find elements
> in, which skip lists help to address.
>
> In LC:
> Arrays allocate memory below the level we look at, as do all other storage
> forms. Any implementation of a linked list that I can think of would
> probably be slower than simply writing to an array. The only thing that
> comes to mind that *might* be faster to write to would be some sort of
> two-variable solution where one variable contained the data, and new
> additions involved simply appending to the end of the (increasingly long)
> string, along with a second variable that, in some efficient way, keeps
> track of what is where in the first variable, which sounds horrible.
>
> Am I overlooking anything?
>
> gc
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode