-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathsrfi-132.html
625 lines (592 loc) · 27.5 KB
/
srfi-132.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>
<head>
<title>SRFI 132: Sort Libraries</title>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<link rel="stylesheet" href="/srfi.css" type="text/css" />
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Title</h1>
Sort Libraries
<h1>Author</h1>
John Cowan (based on SRFI 32 by Olin Shivers)
<h1>Status</h1>
<p>This SRFI is currently in <em>final</em> status. Here is <a href="https://srfi.schemers.org/srfi-process.html">an explanation</a> of each status that a SRFI can hold. To provide input on this SRFI, please send email to <code><a href="mailto:srfi+minus+132+at+srfi+dotschemers+dot+org">srfi-132@<span class="antispam">nospam</span>srfi.schemers.org</a></code>. To subscribe to the list, follow <a href="http://srfi.schemers.org/srfi-list-subscribe.html">these instructions</a>. You can access previous messages via the mailing list <a href="https://srfi-email.schemers.org/srfi-132">archive</a>.</p>
<ul>
<li>Received: 2015-12-09</li>
<li>60-day deadline: 2016-02-07</li>
<li>Draft #1 published: 2015-12-09</li>
<li>Draft #2 published: 2015-12-17</li>
<li>Draft #3 published: 2016-01-20</li>
<li>Draft #4 published: 2016-01-24 (code changes only)</li>
<li>Draft #5 published: 2016-02-01</li>
<li>Draft #6 published: 2016-03-13</li>
<li>Draft #7 published: 2016-03-21 (code changes only)</li>
<li>Finalized: 2016-04-20</li>
</ul>
<h1>Abstract</h1>
<p>
This SRFI describes the API for a full-featured sort toolkit.
</p>
<h1>Rationale</h1>
<h2>100 SRFIs later...</h2>
<p>
This SRFI is based on <a href="https://srfi.schemers.org/srfi-32/srfi-32.txt">SRFI 32</a>
by Olin Shivers, which was withdrawn twelve years ago.
</p>
<p>
There are two backward incompatible changes to the API. The most
important one is that the
comparison predicate now precedes the data rather than following it.
Most of the SRFI 32 commenters thought that this is the better order, despite
the then-widespread precedent.
The other change is that the algorithm-specific
procedures have been removed from the SRFI, though not necessarily from
the sample implementation.
For documentation on them, see SRFI 32 or the source code.
</p>
<p>
Editorially, the text has been reorganized, removing the massive redundancies.
As in R5RS and R7RS, procedures that return nothing of interest, and in SRFI 32 returned zero or
more unspecified values, are now specified to return one otherwise unspecified value. The multiple
packages, most with only a few procedures, into which SRFI 32 is divided have been consolidated.
References to
<a href="https://srfi.schemers.org/srfi-95/srfi-95.html">SRFI 95</a> and
<a href="http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-5.html#node_chap_4">R6RS</a> equivalents have been added.
</p>
<h2 id="Whatvs.how">What vs. how</h2>
<p>
In SRFI 32 there were two different interfaces: "what" (simple) and "how" (detailed).
</p>
<ul><li>Simple: you specified semantics: datatype (list or vector), mutability, and stability.
</li></ul><ul><li>Detailed: you specified the datatype and the actual algorithm (quick, heap, insert, merge).
</li></ul><p>
However, the difficulty with exposing specific algorithms by name is that the
local optima in the search space of algorithms changes over time.
For example, the "qsort" in the musl C library is actually smooth sort, not
quick sort; Python and Java have switched from quick sort to timsort;
some implementations of the C++ STL use introsort rather than quick sort.
Having procedure names that imply e.g. quick sort, that do not actually
implement quick sort, is confusing.
</p>
<p>
Therefore, only the "what" interface has been retained. The sample implementation
uses some of the original SRFI 32 algorithms, but this is not a requirement of this SRFI.
</p>
<h2 id="Consistencyacrossproceduresignatures">Consistency across procedure signatures</h2>
<p>
Procedures share common signatures wherever
possible, to facilitate switching a given call from one procedure
to another.
</p>
<h2 id="Orderingparameterbeforedataparameter">Ordering parameter before data parameter</h2>
<p>
These procedures uniformly observe the following parameter order:
the ordering, equality, or comparison argument
precedes the argument(s) denoting the data to be sorted.
In SRFI 32, the data-first convention was used, because it was
consistent with all the implementations examined in 2002, with
the sole exception of Chez Scheme.
However, <a href="http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-5.html#node_chap_4">R6RS</a> adopted
the procedure-first convention, which is more consistent with other Scheme libraries that
put the procedure first — the "operation currying" convention,
as in <tt>for-each</tt> or <tt>map</tt> or <tt>find</tt>.
This SRFI uses the R6RS convention throughout.
</p>
<h2 id="Stability">Stability</h2>
<p>
A "stable" sort is one that preserves the pre-existing order of equal
elements. Suppose, for example, that we sort a list of numbers by
comparing their absolute values using <tt>abs<</tt> (defined below).
If we sort a list that contains both 3 and -3,
then a stable sort is an algorithm that will not swap the order
of these two elements, that is, the answer will look like <tt>... 3 -3 ...</tt>,
not <tt>... -3 3 ...</tt>.
</p>
<p>
A "stable" merge is one that reliably favors one of its data sets
when equal items appear in both data sets.
All merge operations specified in this SRFI are stable,
breaking ties between data sets in favor
of the first data set — elements of the first list come before equal
elements in the second list.
</p>
<p>
So, if we are merging two lists of numbers ordered by absolute value
using the stable merge operation <tt>list-merge</tt> and <tt>abs<</tt>
compares numbers by their absolute values, then
</p>
<pre class="wiki">(list-merge abs< '(0 -2 4 8 -10) '(-1 3 -4 7))
</pre><p>
reliably places the 4 of the first list before the equal-comparing -4
of the second list: <tt>(0 -1 -2 4 -4 7 8 -10)</tt>.
</p>
<p>
Here's a definition of <tt>abs<</tt>, introduced just for the examples
as it is not part of this SRFI:
</p>
<pre class="wiki">(define (abs< x y) (< (abs x) (abs y))))
</pre><h2 id="Allvectoroperationsacceptoptionalsubrangeparameters">All vector operations accept optional subrange parameters</h2>
<p>
The vector operations specified below all take optional <em>start</em> and <em>end</em>
arguments indicating a selected subrange of a vector's elements.
This compensates for the absence in most Schemes of shared subvectors.
</p>
<h2 id="Requiredvs.allowedside-effects">Required vs. allowed side-effects</h2>
<p>
The <tt>list-sort!</tt> and <tt>list-stable-sort!</tt> procedures are
allowed, but not required,
to alter their arguments' cons cells to construct the result list.
</p>
<p>
The other procedures ending in <tt>!</tt>, on the other hand, explicitly
commit to the use of side-effects on their input lists in order to guarantee
their key algorithmic properties (e.g., linear-time operation, constant-space
stack use).
</p>
<h2 id="Sortinglists">Sorting lists</h2>
<p>
Note that sorting lists involves chasing pointers through memory, which
can be a loser on modern machine architectures because of poor cache and
page locality. Pointer <em>writing</em>, which is what the <tt>set-cdr!</tt>s of a
destructive list-sort algorithm do, is even worse, especially if your
Scheme has a generational GC — the writes will thrash the write-barrier.
Sorting vectors has inherently better locality.
</p>
<p>In particular, all complexity guarantees assume that the basic accessors
and mutators of standard Scheme have O(1) space and time complexity.
</p>
<p>
The reference implementation's destructive list merge and merge sort implementations are
opportunistic — they avoid redundant <tt>set-cdr!</tt>s, and try to take long
already-ordered runs of list structure as-is when doing the merges.
</p>
<h1>Specification</h1>
<h2 id="Procedurenamingandfunctionality">Procedure naming and functionality</h2>
<p>
Most of the procedures described below are variants of two basic
operations: sorting and merging. These procedures are consistently named
by composing a set of basic lexemes to indicate what they do.
</p>
<table class="wiki">
<tr><td>Lexeme</td><td style="text-align: left">Meaning
</td></tr><tr><td><tt>vector</tt></td><td>The procedure operates upon vectors.
</td></tr><tr><td><tt>list</tt></td><td>The procedure operates upon lists.
</td></tr><tr><td><tt>stable</tt></td><td>This lexeme indicates that the sort is a stable one.
</td></tr><tr><td><tt>sort</tt></td><td>The procedure sorts its input data set by some ordering function.
</td></tr><tr><td><tt>merge</tt></td><td>The procedure merges two ordered data sets into a single ordered result.
</td></tr><tr><td><tt>!</tt></td><td>Procedures that end in <tt>!</tt> are allowed, and sometimes required, to reuse their input storage to construct their answer.
</td></tr></table>
<h2 id="Typesofparametersandreturnvalues">Types of parameters and return values</h2>
<p>
In the procedures specified below:
</p>
<ul><li>A <em>lis</em> parameter is a list.
</li></ul><ul><li>A <em>v</em> parameter is a vector.
</li></ul><ul><li>An <em>=</em> parameter is an equality predicate. See <a href="https://srfi.schemers.org/srfi-128/srfi-128.html">SRFI 128</a> for the requirements on equality predicates.
Note that neither this SRFI nor its sample implementation depend on SRFI 128.
</li></ul><ul><li>A <em><</em> parameter is an ordering predicate. See <a href="https://srfi.schemers.org/srfi-128/srfi-128.html">SRFI 128</a> for the requirements on ordering predicates.
</li></ul><ul><li>A <em>start</em> parameter or <em>start</em> and <em>end</em> parameter pair are exact non-negative integers such that 0 <= <em>start</em> <= <em>end</em> <= <tt>(vector-length </tt><em>v</em><tt>)</tt>, where <em>v</em> is the related vector parameter. If not specified, they default to 0 and the length of the vector, respectively. They are interpreted to select the range [<em>start</em>, <em>end</em>), that is, all elements from index <em>start</em> (inclusive) up to, but not including, index <em>end</em>.
</li></ul><p>
Passing values to procedures with these parameters that do not satisfy these
constraints is an error.
</p>
<p>
If a procedure is said to return "an unspecified value", this means that nothing at all
is said about what the procedure returns, except that it returns one value.
</p>
<h2 id="Predicates">Predicates</h2>
<p>
<tt>(list-sorted? </tt><em>< lis</em><tt>)</tt>
</p>
<p>
<tt>(vector-sorted? </tt><em>< v</em> [<em>start</em> [ <em>end</em> ] ]
</p>
<p>
These procedures return true iff their input list or vector
is in sorted order, as determined by <em><</em>.
Specifically, they return <tt>#f</tt> iff there is an adjacent pair ... X Y ... in the input
list or vector such that Y < X in the sense of <em><</em>. The optional <em>start</em> and <em>end</em> range
arguments restrict <tt>vector-sorted?</tt> to examining the indicated subvector.
</p>
<p>
These procedures are equivalent to the SRFI 95 <tt>sorted?</tt> procedure when applied to lists or vectors
respectively, except that they do not accept a key procedure.
</p>
<h2 id="Generalsortprocedures">General sort procedures</h2>
<p>
These procedures provide basic sorting and merging functionality suitable for
general programming. The procedures are named by their semantic properties,
i.e., what they do to the data (sort, stable sort, and so forth).
</p>
<p>
<tt>(list-sort </tt><em>< lis</em><tt>)</tt>
</p>
<p>
<tt>(list-stable-sort </tt><em>< lis</em><tt>)</tt>
</p>
<p>
These procedures
do not alter their inputs, but are allowed to return a value that shares
a common tail with a list argument.
</p>
<p>
The <tt>list-stable-sort</tt> procedure is equivalent to the R6RS <tt>list-sort</tt> procedure. It is also
equivalent to the SRFI 95 <tt>sort</tt> procedure when applied to lists, except that it does not accept a key
procedure.
</p>
<p>
<tt>(list-sort! </tt><em>< lis</em><tt>)</tt>
</p>
<p>
<tt>(list-stable-sort! </tt><em>< lis</em><tt>)</tt>
</p>
<p>
These procedures
are linear update operators — they are allowed, but not required, to
alter the cons cells of their arguments to produce their results.
They return a sorted list containing the same elements as <i>lis</i>.
</p>
<p>
The <tt>list-stable-sort!</tt> procedure is
equivalent to the SRFI 95 <tt>sort!</tt> procedure when applied to lists, except that it does not accept a key
procedure.
</p>
<p>
<tt>(vector-sort </tt><em>< v</em> [ <em>start</em> [ <em>end</em> ] ]<tt>)</tt>
</p>
<p>
<tt>(vector-stable-sort </tt><em>< v</em> [ <em>start</em> [ <em>end</em> ] ]<tt>)</tt>
</p>
<p>
These procedures
do not alter their inputs, but allocate a fresh vector as their result,
of length <em>end</em> - <em>start</em>.
The <tt>vector-stable-sort</tt> procedure with no optional arguments
is equivalent to the R6RS <tt>vector-sort</tt> procedure. It is also
equivalent to the SRFI 95 <tt>sort</tt> procedure when applied to vectors, except that it does not accept a key
procedure.
</p>
<p>
<tt>(vector-sort! </tt><em>< v</em> [ <em>start</em> [ <em>end</em> ] ]<tt>)</tt>
</p>
<p>
<tt>(vector-stable-sort! </tt><em>< v</em> [ <em>start</em> [ <em>end</em> ] ]<tt>)</tt>
</p>
<p>
These procedures
sort their data in-place. (But note that <tt>vector-stable-sort!</tt> may
allocate temporary storage proportional to the size of the input — there are
no known O(n lg n) stable vector sorting algorithms that
run in constant space.) They return an unspecified value.
</p>
<p>
The <tt>vector-sort!</tt> procedure with no optional arguments is equivalent
to the R6RS <tt>vector-sort!</tt> procedure.
</p>
<h2 id="Mergeprocedures">Merge procedures</h2>
<p>
All four merge operations are stable: an element of the initial list <em>lis<sub>1</sub></em> or
vector <em>v<sub>1</sub></em> will come before an equal-comparing element in the second
list <em>lis<sub>2</sub></em> or vector <em>v<sub>2</sub></em> in the result.
</p>
<p>
<tt>(list-merge </tt><em>< lis<sub>1</sub> lis<sub>2</sub></em><tt>)</tt>
</p>
<p>
This procedure
does not alter its inputs, and is allowed to return a value that shares
a common tail with a list argument.
</p>
<p>
This procedure is equivalent to the SRFI 95 <tt>merge</tt> procedure when applied to lists,
except that it does not accept a key procedure.
</p>
<p>
<tt>(list-merge! </tt><em>< lis<sub>1</sub> lis<sub>2</sub></em><tt>)</tt>
</p>
<p>
This procedure
makes only a single, iterative, linear-time pass over its argument lists,
using <tt>set-cdr!</tt>s to rearrange the cells of the lists into the list that is returned
— it works "in place." Hence, any cons cell appearing in the result must
have originally appeared in an input. It returns the sorted input.
</p>
<p>
Additionally,
<tt>list-merge!</tt> is iterative, not recursive — it can operate on arguments of
arbitrary size without requiring an unbounded amount of stack space.
The intent of this
iterative-algorithm commitment is to allow the programmer to be sure that
if, for example, <tt>list-merge!</tt> is asked to merge two ten-million-element
lists, the operation will complete without performing some extremely
(possibly twenty-million) deep recursion.
</p>
<p>
This procedure is equivalent to the SRFI 95 <tt>merge!</tt> procedure when applied to lists,
except that it does not accept a key procedure.
</p>
<p>
<tt>(vector-merge</tt> <em>< v<sub>1</sub> v<sub>2</sub></em> [ <em>start<sub>1</sub></em> [ <em>end<sub>1</sub></em> [ <em>start<sub>2</sub></em> [ <em>end<sub>2</sub></em> ] ] ] ]<tt>)</tt>
</p>
<p>
This procedure does not alter its inputs,
and returns a newly allocated vector
of length (<em>end<sub>1</sub></em> - <em>start<sub>1</sub></em>) + (<em>end<sub>2</sub></em> - <em>start<sub>2</sub></em><tt>)</tt>.
</p>
<p>
This procedure is equivalent to the SRFI 95 <tt>merge</tt> procedure when applied to vectors,
except that it does not accept a key procedure.
</p>
<p>
<tt>(vector-merge! </tt><em>< to from<sub>1</sub> from<sub>2</sub></em> [ <em>start</em> [ <em>start<sub>1</sub></em> [ <em>end<sub>1</sub></em> [ <em>start<sub>2</sub></em> [ <em>end<sub>2</sub></em> ] ] ] ] ]<tt>)</tt>
</p>
<p>
This procedure writes its result into vector <em>to</em>, beginning at index <em>start</em>,
for indices less than
<em>end</em>, which is defined as <em>start</em> + (<em>end<sub>1</sub></em> - <em>start<sub>1</sub></em>) + (<em>end<sub>2</sub></em> - <em>start<sub>2</sub></em><tt>)</tt>.
The target subvector <em>to</em>[<em>start</em>, <em>end</em>) may not overlap either of the source subvectors
<em>from<sub>1</sub></em>[<em>start<sub>1</sub></em>, <em>end<sub>1</sub></em>] and <em>from<sub>2</sub></em>[<em>start<sub>2</sub></em>, <em>end<sub>2</sub></em>].
It returns an unspecified value.
</p>
<p>
This procedure is equivalent to the SRFI 95 <tt>merge!</tt> procedure when applied to lists,
except that it does not accept a key procedure.
</p>
<h2 id="Deletingduplicateneighbors">Deleting duplicate neighbors</h2>
<p>
These procedures delete adjacent duplicate elements from a list or a
vector, using a given element-equality procedure. The first/leftmost
element of a run of equal elements is the one that survives. The list or
vector is not otherwise disordered.
</p>
<p>
These procedures are linear time — much faster than the O(n<sup>2</sup>) general
duplicate-element deletion procedures that do not assume any "bunching" of elements
provided by <a href="https://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>.
If you want to delete duplicate
elements from a large list or vector, sort the elements to bring equal
items together, then use one of these procedures, for a total time of
O(n lg n).
</p>
<p>
The equality procedure is always
invoked as <tt>(= x y)</tt>, where <em>x</em> comes before <em>y</em> in the containing list or vector.
</p>
<p>
<tt>(list-delete-neighbor-dups </tt><em>= lis</em><tt>)</tt>
</p>
<p>
This procedure does not alter its input list, but its result may share
storage with the input list.
</p>
<p>
<tt>(list-delete-neighbor-dups! </tt><em>= lis</em><tt>)</tt>
</p>
<p>
This procedure mutates its input list in order to construct its result.
It makes only a single, iterative, linear-time pass over its
argument, using <tt>set-cdr!</tt>s to rearrange the cells of the list
into the final result — it works "in place." Hence, any cons cell appearing
in the result must have originally appeared in the input.
</p>
<p>
<tt>(vector-delete-neighbor-dups </tt><em>= v</em> [ <em>start</em> [ <em>end</em> ] ]<tt>)</tt>
</p>
<p>
This procedure does not alter its input vector, but rather
newly allocates and returns a vector to hold the result.
</p>
<p>
<tt>(vector-delete-neighbor-dups! </tt><em>= v</em> [ <em>start</em> [ <em>end</em> ] ]<tt>)</tt>
</p>
<p>
This procedure reuses its input vector to hold the answer,
packing it into the index range [<em>start, newend</em>),
where <em>newend</em> is the non-negative exact integer that is returned as its value.
The vector is not altered outside the range [<em>start, newend</em>).
</p>
<p>
Examples:
</p>
<pre class="wiki"> (list-delete-neighbor-dups = '(1 1 2 7 7 7 0 -2 -2))
=> (1 2 7 0 -2)
(vector-delete-neighbor-dups = '#(1 1 2 7 7 7 0 -2 -2))
=> #(1 2 7 0 -2)
(vector-delete-neighbor-dups < '#(1 1 2 7 7 7 0 -2 -2) 3 7))
=> #(7 0 -2)
;; Result left in v[3,9):
(let ((v (vector 0 0 0 1 1 2 2 3 3 4 4 5 5 6 6)))
(cons (vector-delete-neighbor-dups! < v 3)
v))
=> (9 . #(0 0 0 1 2 3 4 5 6 4 4 5 5 6 6))
</pre>
<h2 id="Findingthemedian">Finding the median</h2>
<p>
These procedures do not have SRFI 32 counterparts.
They find the median element of a vector after
sorting it in accordance with an ordering procedure.
If the number of elements in <tt><i>v</i></tt> is odd, the middlemost
element of the sorted result is returned. If the number of elements is
zero, <tt><i>knil</i></tt> is returned. Otherwise,
<tt><i>mean</i></tt> is applied to the two middlemost elements
in the order in which they appear in <tt><i>v</i></tt>, and
whatever it returns is returned. If <tt><i>mean</i></tt> is omitted,
then the default mean procedure is <tt>(lambda (a b) (/ (+ a b) 2)</tt>,
but this procedure is applicable to non-numeric values as well.
</p>
<p>
<tt>(vector-find-median </tt><em>< v knil</em> [ <em>mean</em> ]<tt>)</tt>
</p>
<p>
This procedure does not alter its input vector, but rather
newly allocates a vector to hold the intermediate result.
Runs in O(n) time.
</p>
<p>
<tt>(vector-find-median! </tt><em>< v knil</em> [ <em>mean</em> ]<tt>)</tt>
</p>
<p>
This procedure reuses its input vector to hold the intermediate result,
leaving it sorted, but is otherwise the same as <tt>vector-find-median</tt>.
Runs in O(n ln n) time.
</p>
<h2 id="Selection">Selection</h2>
<p>
These procedures do not have SRFI 32 counterparts.
</p>
<p>
<tt>(vector-select! </tt><em>< v k </em> [ <em>start</em> [ <em>end</em> ] ]</em> <tt>)</tt>
</p>
<p>
This procedure returns the <i>k</i>th smallest element (in the sense of
the < argument) of the region of
a vector between <i>start</i> and <i>end</i>.
Elements within the range may be reordered, whereas those
outside the range are left alone. Runs in O(n) time.
</p>
<p>
<tt>(vector-separate! </tt><em>< v k </em> [ <em>start</em> [ <em>end</em> ] ]</em> <tt>)</tt>
</p>
<p>
This procedure places the smallest <i>k</i> elements (in the sense of
the < argument) of the region of
a vector between <i>start</i> and <i>end</i> into the first <i>k</i>
positions of that range, and the remaining elements into the remaining
positions. Otherwise, the elements are not in any particular order. Elements
outside the range are left alone. Runs in O(n) time. Returns an unspecified value.
</p>
<h1>Implementation</h1>
<p>The sample implementation is a modified version of the Scheme 48
implementation of the <tt>sorting</tt> structure,
and is found in the repository of this SRFI.
It will use the R6RS sorting library if it is available, but does not depend on it.
This is close to the original SRFI 32 reference implementation, but includes some
bug fixes and switches the < and = arguments to the initial position.
It also adds implementations for the median and selection procedures.
The code is very portable and freely reusable.
It is tightly bummed, as far as could be done in portable Scheme, and
is commented in Olin's usual
voluminous style, including notes on porting and implementation-specific
optimizations. The median and selection code is specific to this SRFI.
</p>
<p>
The only non-R4RS features in the code
are the use of R5RS/R6RS/R7RS multiple-value return, with <tt>values</tt> and <tt>call-with-values</tt> procedures,
and the use of R7RS-style <tt>error</tt> to report an assertion violation.
</p>
<p>
You could speed up the vector code a lot by error-checking the procedure
parameters and then shifting over to fixnum-specific arithmetic and
dangerous vector-indexing and vector-setting primitives. The comments
in the code indicate where the initial error checks would have to be
added. There are several <tt>(quotient </tt><em>n</em><tt> 2)</tt> calls that could be changed to a
fixnum right-shift, as well, in both the list and vector code. The code
is designed to enable this — each file usually exports one or two "safe"
procedures that end up calling an internal "dangerous" primitive. The
little exported cover procedures are where you move the error checks.
</p>
<p>
This should provide <em>big</em> speedups. In fact, all the code bumming in the source
pretty much disappears in the noise unless you have a good compiler and also
can dump the vector-index checks and generic arithmetic — so it's really set up
for optimization rather than fully optimized.
</p>
<p>
The optional-arg parsing, defaulting, and error checking is done with a
portable <tt>syntax-rules</tt> macro. But if the target Scheme has a
faster mechanism (e.g., Chez),
it's definitely better to switch to using it. Note that argument defaulting and
error-checking are interleaved — there's no need to error-check defaulted
<em>start</em> and <em>end</em> args to see if they are fixnums that are legal vector indices for
the corresponding vector, etc.
</p>
<h2 id="Files">Files</h2>
<p>
<tt>delndups.scm</tt> - the <tt>delete-neighbor-dups</tt> procedures <br />
<tt>lmsort.scm</tt> - list merge sort <br />
<tt>median.scm</tt> - the <tt>find-median</tt> procedures <br />
<tt>selection.scm</tt> - the <tt>selection</tt> procedure <br />
<tt>sort.scm</tt> - generic sort and merge procedures <br />
<tt>sorting-test.scm</tt> - test file <br />
<tt>sortp.scm</tt> - sort predicates <br />
<tt>srfi-132.scm</tt> - a Chicken library providing this SRFI <br />
<tt>srfi-132.sld</tt> - an R7RS counterpart of <tt>srfi-132.scm</tt> <br />
<tt>vector-util.scm</tt> - vector utilities <br />
<tt>vhsort.scm</tt> - vector heap sort <br />
<tt>visort.scm</tt> - vector insert sort <br />
<tt>vmsort.scm</tt> - vector merge sort <br />
<tt>vqsort2.scm</tt> - vector quick sort <br />
</p>
<h1>Acknowledgements</h1>
<p>
Olin thanked the authors of the open source consulted when designing this
library, particularly Richard O'Keefe, Donovan Kolbly and the MIT Scheme Team.
John thanks Will Clinger for his detailed comments, and both Will Clinger and
Alex Shinn for their implementation efforts.
</p>
<h1>Copyright</h1>
<h2 id="SRFItextcopyright">SRFI text copyright</h2>
<p>
This document is copyright (C) Olin Shivers (1998, 1999).
All Rights Reserved.
</p>
<p>
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
</p>
<p>
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
</p>
<p>
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
</p>
<h2 id="Sampleimplementationcopyright">Sample implementation copyright</h2>
<p>
Short summary: no restrictions.
</p>
<p>
While Olin wrote all of this code himself, he read a lot of code before he began
writing. However, all such code is, itself, either open source or public
domain, rendering irrelevant any issue of "copyright taint."
</p>
<p>
Hence the sample implementation is Copyright © 1998 by Olin Shivers
and made available under the same copyright as the SRFI text (see above).
</p>
<hr>
<address>Editor: <a href="mailto:srfi-editors at srfi dot schemers dot org">Arthur A. Gleckler</a></address></body></html>