skip-list in Dylan available via FTP 
Author Message
 skip-list in Dylan available via FTP

Dear Fellow Dylan Users.

I just put an extension to the standard Dylan collection classes onto the
FTP archives:  skip-lists.  They are described towards the end of this article.
This work was inspired by the work of the Gwydion Project at Carnegie Mellon
University.  Thank you at CMU!

The code has currently only been tested with the Apple Dylan TR.  
A port to Mindy is in the works.  You can find it currently at the
following places:

* Skip-Lists alone.  Get the file  I created the files by
  exporting from Apple's TR.  I had no problems re-importing them again.

  The archive is packed with zip.  Unpack with
  > unzip
    inflating: Readme.txt
    inflating: coll-ext-library.dylan
    inflating: Skip-List.dylan
    inflating: Tests.dylan
  > ls -axl
  total 51
  drwxrw-rw-  2 zimmerma      512 Mar 17 17:07 ./
  drwx------  3 zimmerma      512 Mar 17 17:04 ../
  -rw-rw-rw-  1 zimmerma     4191 Mar 17 15:57 Readme.txt
  -rw-rw-rw-  1 zimmerma    23052 Mar 17 15:36 Skip-List.dylan
  -rw-rw-rw-  1 zimmerma     4210 Mar 17 15:36 Tests.dylan
  -rw-rw-rw-  1 zimmerma     3297 Mar 17 15:36 coll-ext-library.dylan
  -rw-rw-rw-  1 zimmerma    11486 Mar 17 17:06

* Skip-lists together with the Collection Extensions from the
  Gwydion Project at Carnegie Mellon University, as available from CMU's FTP
  site and the Apple Dylan TR CD.  This is a rather large file containing two
  Apple Dylan TR projects:  one for the collection extensions from CMU
  including skip-lists and one for the Random library from CMU.  
  Stuffed and binhexed.

* An up-to-date version of the archives will be reachable from my
  home page, soon (not yet, as of March 19th)


I hope, my code is of use to somebody.  If you have the time,
please let me know, what you think about it.  Does anybody
volunteer to implement AVL trees ?-)

With best regards

Kai W. Zimmermann



 A skip-list is a data type equivalent to a balanced (binary) tree.
 All keys must be comparable by some kind of ordering function, e.g., <.

 The data structure looks like this.  You start searching for a key in the
 highest level of header H, taking big steps along the list and then descend
 to the one step level.  Example: looking for 6, start at H, highest level.
 Find 7.  Descend, because 7>6.  Find 3.  Move on, since 3<6.  Find 7.
 Descend, because 7>6.  Find 5.  Move on, since 5<6.  Find 7,
 for the last time now :-).  Descend.  Find 6.

 o ------------------------------------> o -----------> NIL  Level 4
 o ----------------> o ----------------> o -----------> NIL  Level 3
 o ------> o ------> o ------> o ------> o ------> o -> NIL  Level 2
 o -> o -> o -> o -> o -> o -> o -> o -> o -> o -> o -> NIL  Level 1
      0    1    2    3    4    5    6    7   123  777        <- Keys
      A    X    k    G    U    d    p    q    W    B         <- Values

 The expensive part, equivalent to balancing, is to find the corresponding
 level for each node.  Therefore a probabilistic alternative is implemented,
 where a new level is chosen at random, whenever a node is added. The
 performance is comparable to a probabilistically balanced binary tree.

 Look-up in a perfectly balanced skip-list is        O(ln(N))
 Adding an element to a probabilistic skip-list is   O(ln(N))
 Like in a binary tree, in a perfectly balanced skip-list
 you need about O(2*N) pointers (+ storage for the data)

 For details see:
   W. Pugh (1990)  "Skip Lists:  A Probabilistic Alternative to
   Balanced Trees."  Communications of the ACM  33 (6): 668-676

 I tried to make the library (hash)table like.

 Create a skip-list, e.g.,    define variable H = make(<skip-list>)
 Now add the elements         H[0] := "A"; H[777] := "B"; H[3] := "G";
 You can look them up via     H[3]
 Map over them with:          for (x in H) signal("%s ", x) end;
 To get rid of a key use      remove-key!(H, 4711);
 You can convert a table      as(<skip-list>, make(<table>));
 or any other collection      as(<skip-list>, #(a:, b:, c:, d:))

 Of course you can use any key and not only integers,
 as long as you provide an ordering function.

 Some test functions at the end show that Pugh is right.  There is very
 little difference in the timing for p=1/2 and p=1/4, even 1/5 is fine.
 The lower the propability, the less additional space you need.  p=1/2  uses
 more additional pointers than p=1/4.  E.g., with p=1/4 and 10000 elements
 you need about 24 key comparisons to look up one value.  The measures
 are about the same for p=1/2, but the maximum level used is about two
 times higher.  A totally balanced binary tree would need about 14 comparisons.

 This module is intended as an extension to the collection library and
 inspired by the extensions from the Gwydion Project at Carnegie Mellon
 University.  In addition, it's my first try on Dylan :-)   If you have
 any tips concerning style, efficiency, etc., please let me know.

 The code depends on the availability of a RANDOM function. For portability
 I used the one from the Gwydion Project at Carnegie Mellon University.
 That is not very efficient, because a lot of number conversions occur.
 There is another in the Mac toolbox.

 I had to reformulate the algorithms from iterative to tail recursive
 versions, due to some feature (design flaw?) of the Apple Dylan TR.
 In Apple's Dylan TR the use of := on a local variable creates 8 byte
 garbage per variable.  Rebinding it using let or tail recursion does
 not use extra space.  Just move the comment delimiters to revert to
 iterative, if you think that is necessary.

 I hope this code is of use to somebody.



Kai Zimmermann   FB Informatik WSV, University Hamburg, Vogt-Koelln-Str. 30
                 D-22527 Hamburg, Germany, Phone +49-40-54715-368, Fax -385

Sat, 05 Sep 1998 03:00:00 GMT  
 [ 1 post ] 

 Relevant Pages 

1. Dylan Interim Manual available via WWW

2. VWNC 5i.2 available via FTP?

3. M4th available via ftp

4. FORTH primer available via ftp

5. Forth Book available via FTP(correct this time!)

6. Forth book available via FTP

7. A POP-11 Book Available via FTP

8. Files available via FTP from FIDOnet

9. New beta-test Release of CAML available via anonymous ftp

10. ICI available via FTP

11. A POP-11 Book Available via FTP

12. NO-COST MS-DOS version of M (MUMPS) available via anonymous FTP


Powered by phpBB® Forum Software