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
<[email protected]>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
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
_______________________________________________
use-livecode mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
