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