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

Last change on this file since 37471 was 37471, checked in by juergen, 18 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 be used
108as last order to allow duplicates.
109
110transformer.
111
112==== sl-compare
113
114<procedure>(sl-compare sls)</procedure>
115
116combined comparison function
117
118==== sl-count
119
120<procedure>(sl-count sls)</procedure>
121
122number of items stored in skiplist
123
124==== sl-found
125
126<procedure>(sl-found sls)</procedure>
127
128list of found items, to be called after search!
129
130==== sl-found?
131
132<procedure>(sl-found? sls item)</procedure>
133
134is item found?
135
136==== sl-height
137
138<procedure>(sl-height sls)</procedure>
139
140actual maximal height of nodes (can be changed)
141
142==== sl-max-height
143
144<procedure>(sl-max-height sls)</procedure>
145
146absolute maximum heigth of nodes in skiplist (not changeble)
147
148==== sl-max
149
150<procedure>(sl-max sls)</procedure>
151
152biggest item stored in skiplist
153
154==== sl-min
155
156<procedure>(sl-min sls)</procedure>
157
158smallest item stored in skiplist
159
160==== sl-orders
161
162<procedure>(sl-orders sls)</procedure>
163
164list of orders defined in the constructor
165
166==== sl-search-level
167
168<procedure>(sl-search-level sls)</procedure>
169
170down to which level a previous search descended?
171
172==== sl-width
173
174<procedure>(sl-width sls)</procedure>
175
176width skipped on average at each search level supplied by constructor
177
178==== sl-map
179
180<procedure>(sl-map fn sls)</procedure>
181<procedure>(sl-map fn sls order . orders)</procedure>
182<procedure>(sl-map fn sls width)</procedure>
183<procedure>(sl-map fn sls width order . orders)</procedure>
184
185depending on the mapping function, different order
186procedures might be necessary
187
188==== sl-for-each
189
190<procedure>(sl-for-each proc sls)</procedure>
191
192apply proc to each item in skiplist
193
194==== sl-filter
195
196<procedure>(sl-filter ok? sls)</procedure>
197
198filtering
199
200==== sl-reorder
201
202<procedure>(sl-reorder sls order . orders)</procedure>
203
204changing orders
205
206==== sl-restructure
207
208<procedure>(sl-restructure sls width max-height)</procedure>
209
210changing width
211
212==== sl-insert!
213
214<procedure>(sl-insert! sls item . items)</procedure>
215
216insert items into skiplist
217
218==== sl-remove!
219
220<procedure>(sl-remove! sls item . items)</procedure>
221
222remove items from skiplist
223
224==== sl-search!
225
226<procedure>(sl-search! sls item)</procedure>
227
228searching for an item changes internal cursor transparently
229
230==== sl-clear!
231
232<procedure>(sl-clear! sls)</procedure>
233
234reset skiplist
235
236=== Examples
237
238<enscript highlight=scheme>
239
240(import skiplists)
241
242   A skiplist with primary and secondary search order, allowing duplicates
243;; some constructors
244
245(define sls1 (skiplist 15 fixnum? -))
246(sl-width sls1) ;-> 2
247(sl-max-height sls1) ;-> 15
248(sl-dups? sls1) ;-> #f
249
250(define sls2 (skiplist 4 20 fixnum? - dups))
251(fx= (sl-width sls2) ;-> 4
252(fx= (sl-max-height sls2) ;-> 20
253(sl-dups? sls2) ;-> #t
254
255;; create ...
256
257(define item-type (lambda (x)
258                    (and ((list-of? integer?) x) (> (length x) 2))))
259
260(define primary-order (lambda (x y) (- (car x) (car y))))
261
262(define secondary-order (lambda (x y) (- (cadr x) (cadr y))))
263
264(define sls3 (skiplist 3
265                       15
266                       item-type
267                       primary-order
268                       secondary-order
269                       dups))
270
271;; and populate ...
272
273(define lst1
274        (let loop ((k 0) (lst '()))
275          (if (= k 100)
276            lst
277            (loop (+ k 1) (cons (pseudo-random-integer 10) lst)))))
278
279(define lst2
280        (let loop ((k 0) (lst '()))
281          (if (= k 100)
282            lst
283            (loop (+ k 1) (cons (pseudo-random-integer 10) lst)))))
284
285(define lst3
286        (let loop ((k 0) (lst '()))
287          (if (= k 100)
288            lst
289            (loop (+ k 1) (cons (pseudo-random-integer 100) lst)))))
290
291(apply sl-insert! sls3
292       (map (lambda (x y z) (list x y z))
293            lst1 lst2 lst3))
294
295(sl-count sls3) ;-> 100
296
297(sl-width sls3) ;-> 3
298
299;; inserting item and removing all with same key ...
300
301((sl-item? sls3) '(1 2 3)) ;-> #t
302
303(sl-search! sls3 '(1 2 3))
304
305(if (sl-found? sls3 '(1 2 3))
306  (apply sl-remove! sls3 (sl-found sls3)))
307
308(sl-insert! sls3 '(1 2 3))
309
310(sl-search! sls3 '(1 2 3))
311
312(member '(1 2 3) (sl-found sls3))
313
314(apply sl-remove! sls3 (sl-found sls3))
315
316(sl-search! sls3 '(1 2 3))
317
318(null? (sl-found sls3))
319
320;; produce duplicates at the ends ...
321
322(sl-insert! sls3 '(-1 2 3) '(-1 2 3 4))
323
324(sl-min sls3) ;-> '((-1 2 3 4) (-1 2 3))
325
326(sl-insert! sls3 '(10 1 2) '(10 1 2 3) '(10 1 3))
327
328(sl-found sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2))
329
330(sl-max sls3) ;-> '((10 1 3) (10 1 2 3) (10 1 2))
331
332;; and remove them again ...
333
334(sl-search! sls3 '(-1 2 3 4))
335
336(apply sl-remove! sls3 (sl-found sls3))
337
338(sl-search! sls3 '(-1 2 3 4))
339
340(null? (sl-found sls3)) ;-> #t
341
342(sl-search! sls3 '(10 1 3))
343
344(apply sl-remove! sls3 (sl-found sls3))
345
346(null? (sl-found sls3)) ;-> #t
347
348;; reorder removing all dups ...
349
350(apply <= (map car
351               (skiplist->list
352                 (sl-reorder sls3 primary-order secondary-order))))
353
354(<= (sl-count (sl-reorder sls3 primary-order secondary-order))
355    (sl-count sls3))
356
357 reorder using only secondary order ...
358
359(apply < (map cadr
360              (skiplist->list
361                (sl-reorder sls3 secondary-order))))
362
363(>= 10 (sl-count
364         (sl-reorder sls3 secondary-order)))
365
366;; restructure ...
367
368(equal? (skiplist->list sls3)
369        (skiplist->list (sl-restructure sls3 2 10)))
370
371;; filter ...
372
373((list-of? odd?) (map caddr
374                      (skiplist->list
375                        (sl-filter sls3 (lambda (x) (odd? (caddr x)))))))
376
377;; map ...
378
379(let ((fn (lambda (x) (* 2 x))))
380  (equal?
381    (map fn (skiplist->list sls3))
382    (skiplist->list (sl-map sls3 fn))))
383
384</enscript>
385
386=== Requirements
387
388none
389
390=== Last update
391
392Mar 25, 2019
393
394== Author
395
396[[/users/juergen-lorenz|Juergen Lorenz]]
397
398== License
399
400Copyright (c) 2012-2019, Juergen Lorenz
401All rights reserved.
402Redistribution and use in source and binary forms, with or without
403modification, are permitted provided that the following conditions are
404met:
405
406Redistributions of source code must retain the above copyright
407notice, this list of conditions and the following disclaimer.
408
409Redistributions in binary form must reproduce the above copyright
410notice, this list of conditions and the following disclaimer in the
411documentation and/or other materials provided with the distribution.
412Neither the name of the author nor the names of its contributors may be
413used to endorse or promote products derived from this software without
414specific prior written permission.
415
416THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
417IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
418TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
419PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
420HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
421SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
422TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
423PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
424LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
425NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
426SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
427
428== Version History
429
430; 1.0 : port from chicken-4
Note: See TracBrowser for help on using the repository browser.