source: project/wiki/eggref/5/skiplists @ 37470

Last change on this file since 37470 was 37470, checked in by juergen, 11 months ago

skiplists docu

File size: 10.2 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4
5== Skiplists
6
7Skiplists are data-types, which can replace balanced search-trees. They
8are invented by Pugh. The idea is as follows:
9
10Contrary to listnodes, which are pairs of an item and a next pointer,
11skipnodes are pairs of an item and a vector of next pointers. The
12length' of these vectors depend on each skipnode itself. They are
13choosen randomly in such a way, that, in the average, the number of
14nodes with at least k links is half the number of links with at least
15k-1 links, for k>1. Following the next pointers at a fixed link-level,
16k say, one skips all nodes with less than k pointers.
17
18Inserting an item into a skiplist now works as follows. First one
19packages the item into a skipnode, where the number of links is
20generated randomly as described above. Second, one follows the skiplist
21along the highest occupied number of links as long as the skiplist's
22nodes point to items less then the item of the node to be inserted.
23Third, one steps down one level and continues following the skiplist's
24nodes at this new smaller level. Repeating this process until level 0
25is reached we eventually find the place where our new node is to be
26inserted.
27
28Some additional remarks are in order.
29
30We described the process with a width of two, i.e. at each level in the
31average one node of the level below is skipped. A higher value than two
32for the width is possible as well, trading performance against space.
33
34We have to decide, what to do with duplicates. We choose the following
35approach: The skiplist itself stores a list of either one or several
36numerical comparison operators. Only if the last of those operators is
37the special comparison operator dups (which returns constantly 0, i.e.
38it compares nothing) duplicates are allowed. Moreover, we arrage
39matters in such a way, that all nodes of duplicates with the same key
40have the same height, so that a search for the item which was inserted
41last will be found first.
42
43=== Documentation
44
45In this implementation skiplists are implemented in two modules,
46%skiplists and skiplists. They both have the same interface.
47The former implements all routines without any checks, the latter
48imports the former with routines prefixed with % and calling those
49routines with checked arguments. This way you can trade security against
50speed ...
51
52==== skiplists
53
54<procedure>(skiplists)
55<procedure>(skiplists sym)
56
57documentation procedure.
58The first call shows the list of exported symbols,
59the second documentation of symbol sym.
60
61==== skiplist
62
63<procedure>(skiplist width max-height item? order . orders)</procedure>
64<procedure>(skiplist max-height item? order . orders)</procedure>
65<procedure>(skiplist item? order . orders))</procedure>
66
67constructors:
68width is the jump width,
69max-height the maximum allowed length of pointers of an item,
70item? checks
71
72==== skiplist?
73
74<procedure>(skiplist? xpr)</procedure>
75
76type predicate.
77
78==== skiplist->list
79
80<procedure>(skiplist->list sls)</procedure>
81<procedure>(skiplist->list sls level)</procedure>
82
83the list of items stored in each level
84
85==== sl-null?
86
87<procedure>(sl-null? sls)</procedure>
88
89is skiplist empty?
90
91==== sl-dups?
92
93<procedure>(sl-dups? sls)</procedure>
94
95are duplicates allowed?
96
97==== sl-item?
98
99<procedure>(sl-item? sls)</procedure>
100
101item type predicate
102
103==== dups
104
105<procedure>(dups x y)</procedure>
106
107trivial numerical comparison operator to allow for duplicates
108
109transformer.
110
111==== sl-compare
112
113<procedure>(sl-compare sls)</procedure>
114
115combined comparison function
116
117==== sl-count
118
119<procedure>(sl-count sls)</procedure>
120
121number of items stored in skiplist
122
123==== sl-found
124
125<procedure>(sl-found sls)</procedure>
126
127list of found items, to be called after search!
128
129==== sl-found?
130
131<procedure>(sl-found? sls item)</procedure>
132
133is item found?
134
135==== sl-height
136
137<procedure>(sl-height sls)</procedure>
138
139actual maximal height of nodes (can be changed)
140
141==== sl-map
142
143<procedure>(sl-map fn sls)</procedure>
144<procedure>(sl-map fn sls order . orders)</procedure>
145<procedure>(sl-map fn sls width)</procedure>
146<procedure>(sl-map fn sls width order . orders)</procedure>
147
148depending on the mapping function, different order
149procedures might be necessary
150
151==== sl-for-each
152
153<procedure>(sl-for-each proc sls)</procedure>
154
155apply proc to each item in skiplist
156
157==== sl-filter
158
159<procedure>(sl-filter ok? sls)</procedure>
160
161filtering
162
163==== sl-max-height
164
165<procedure>(sl-max-height sls)</procedure>
166
167absolute maximum heigth of nodes in skiplist (not changeble)
168
169==== sl-max
170
171<procedure>(sl-max sls)</procedure>
172
173biggest items stored in skiplist
174
175==== sl-min
176
177<procedure>(sl-min sls)</procedure>
178
179smallest item stored in skiplist
180
181==== sl-orders
182
183<procedure>(sl-orders sls)</procedure>
184
185list of orders defined in the constructor
186
187==== sl-search-level
188
189<procedure>(sl-search-level sls)</procedure>
190
191down to which level a previous search descended?
192
193==== sl-width
194
195<procedure>(sl-width sls)</procedure>
196
197width skipped on average at each search level supplied by constructor
198
199==== sl-reorder
200
201<procedure>(sl-reorder sls order . orders)</procedure>
202
203changing orders
204
205==== sl-restructure
206
207<procedure>(sl-restructure sls width max-height)</procedure>
208
209changing width
210
211==== sl-insert!
212
213<procedure>(sl-insert! sls item . items)</procedure>
214
215insert items into skiplist
216
217==== sl-remove!
218
219<procedure>(sl-remove! sls item . items)</procedure>
220
221remove items from skiplist
222
223==== sl-search!
224
225<procedure>(sl-search! sls item)</procedure>
226
227searching for an item changes cursor transparently
228
229==== sl-clear!
230
231<procedure>(sl-clear! sls)</procedure>
232
233reset skiplist
234
235=== Examples
236
237<enscript highlight=scheme>
238
239(import skiplists)
240
241   A skiplist with primary and secondary search order, allowing duplicates
242;; some constructors
243
244(define sls1 (skiplist 15 fixnum? -))
245(sl-width sls1) ;-> 2
246(sl-max-height sls1) ;-> 15
247(sl-dups? sls1) ;-> #f
248
249(define sls2 (skiplist 4 20 fixnum? - dups))
250(fx= (sl-width sls2) ;-> 4
251(fx= (sl-max-height sls2) ;-> 20
252(sl-dups? sls2) ;-> #t
253
254;; create ...
255
256(define item-type (lambda (x)
257                    (and ((list-of? integer?) x) (> (length x) 2))))
258
259(define primary-order (lambda (x y) (- (car x) (car y))))
260
261(define secondary-order (lambda (x y) (- (cadr x) (cadr y))))
262
263(define sls3 (skiplist 3
264                       15
265                       item-type
266                       primary-order
267                       secondary-order
268                       dups))
269
270;; and populate ...
271
272(define lst1
273        (let loop ((k 0) (lst '()))
274          (if (= k 100)
275            lst
276            (loop (+ k 1) (cons (pseudo-random-integer 10) lst)))))
277
278(define lst2
279        (let loop ((k 0) (lst '()))
280          (if (= k 100)
281            lst
282            (loop (+ k 1) (cons (pseudo-random-integer 10) lst)))))
283
284(define lst3
285        (let loop ((k 0) (lst '()))
286          (if (= k 100)
287            lst
288            (loop (+ k 1) (cons (pseudo-random-integer 100) lst)))))
289
290(apply sl-insert! sls3
291       (map (lambda (x y z) (list x y z))
292            lst1 lst2 lst3))
293
294(sl-count sls3) ;-> 100
295
296(sl-width sls3) ;-> 3
297
298;; inserting item and removing all with same key ...
299
300((sl-item? sls3) '(1 2 3)) ;-> #t
301
302(sl-search! sls3 '(1 2 3))
303
304(if (sl-found? sls3 '(1 2 3))
305  (apply sl-remove! sls3 (sl-found sls3)))
306
307(sl-insert! sls3 '(1 2 3))
308
309(sl-search! sls3 '(1 2 3))
310
311(member '(1 2 3) (sl-found sls3))
312
313(apply sl-remove! sls3 (sl-found sls3))
314
315(sl-search! sls3 '(1 2 3))
316
317(null? (sl-found sls3))
318
319;; produce duplicates at the ends ...
320
321(sl-insert! sls3 '(-1 2 3) '(-1 2 3 4))
322
323(sl-min sls3) ;-> '((-1 2 3 4) (-1 2 3))
324
325(sl-insert! sls3 '(10 1 2) '(10 1 2 3) '(10 1 3))
326
327(sl-found sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2))
328
329(sl-max sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2))
330
331;; and remove them again ...
332
333(sl-search! sls3 '(-1 2 3 4))
334
335(apply sl-remove! sls3 (sl-found sls3))
336
337(sl-search! sls3 '(-1 2 3 4))
338
339(null? (sl-found sls3)) ;-> #t
340
341(sl-search! sls3 '(10 1 3))
342
343(apply sl-remove! sls3 (sl-found sls3))
344
345(null? (sl-found sls3)) ;-> #t
346
347;; reorder removing all dups ...
348
349(apply <= (map car
350               (skiplist->list
351                 (sl-reorder sls3 primary-order secondary-order))))
352
353(<= (sl-count (sl-reorder sls3 primary-order secondary-order))
354    (sl-count sls3))
355
356 reorder using only secondary order ...
357
358(apply < (map cadr
359              (skiplist->list
360                (sl-reorder sls3 secondary-order))))
361
362(>= 10 (sl-count
363         (sl-reorder sls3 secondary-order)))
364
365;; restructure ...
366
367(equal? (skiplist->list sls3)
368        (skiplist->list (sl-restructure sls3 2 10)))
369
370;; filter ...
371
372((list-of? odd?) (map caddr
373                      (skiplist->list
374                        (sl-filter sls3 (lambda (x) (odd? (caddr x)))))))
375
376;; map ...
377
378(let ((fn (lambda (x) (* 2 x))))
379  (equal?
380    (map fn (skiplist->list sls3))
381    (skiplist->list (sl-map sls3 fn))))
382
383</enscript>
384
385=== Requirements
386
387none
388
389=== Last update
390
391Mar 25, 2019
392
393== Author
394
395[[/users/juergen-lorenz|Juergen Lorenz]]
396
397== License
398
399Copyright (c) 2012-2019, Juergen Lorenz
400All rights reserved.
401Redistribution and use in source and binary forms, with or without
402modification, are permitted provided that the following conditions are
403met:
404
405Redistributions of source code must retain the above copyright
406notice, this list of conditions and the following disclaimer.
407
408Redistributions in binary form must reproduce the above copyright
409notice, this list of conditions and the following disclaimer in the
410documentation and/or other materials provided with the distribution.
411Neither the name of the author nor the names of its contributors may be
412used to endorse or promote products derived from this software without
413specific prior written permission.
414
415THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
416IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
417TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
418PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
419HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
420SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
421TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
422PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
423LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
424NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
425SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
426
427== Version History
428
429; 1.0 : port from chicken-4
Note: See TracBrowser for help on using the repository browser.