[R6RS] a totalization of equal?
William D Clinger
will at ccs.neu.edu
Sun Feb 26 15:53:41 EST 2006
As mentioned in the "non-opaque record equality" thread...
I propose we define an always-terminating predicate, say
equiv?, that always returns the same value as equal? when
equal? actually terminates and returns a value.
If we had finite mappings with amortized constant-time
lookups based on object identity, we could implement a
version of equiv? that runs in O(n) time and space,
where n is the size of the larger of the objects being
compared.
Even if we restrict ourselves to portable R5RS Scheme,
and use linear-time lookups based on lists, we can still
implement a version of equiv? that runs in O(n) space
and O(n^2) time for the worst case, and runs in O(n)
time for most common cases. Note that the R5RS equal?
procedure does not run in polynomial time, even when
restricted to acyclic structures.
For a prototype implementation of equiv?, see
http://www.ccs.neu.edu/home/will/R6RS/equiv.sch
http://www.ccs.neu.edu/home/will/Research/ILC2005/Source/run-benchmark.chez
The second of these files defines the run-benchmark
procedure for Chez Scheme, and can be modified for
most other systems. That procedure is needed only
to run the benchmarks.
I ran the benchmarks on my old SunBlade 100 in Chez
Scheme v6.1 (optimize-level 2) and Larceny v0.90, with
(representation-inference #f) to turn off a compiler bug.
The table below shows the ratios obtained by dividing the
run time for equiv? by the run time for the system's
predefined equal? procedure. The main reason Larceny's
ratios are smaller than Chez's is that Chez Scheme's
pre-defined equal? procedure is faster than Larceny's.
ratios
Chez Larceny
equality0:10 circular flat list .0 .0
equality1:10 DAG (much sharing) 9.5 3.5
equality2:7 tree (no sharing) 8.5 3.0
equality3:1000 flat list 3.2 .7
equality4:300 shallow list 13.5 4.2
equality5:500 worst case 1450 715
equality5:1000 worst case 2650 1225
The last two lines confirm the algorithm's O(n^2) behavior.
Will
More information about the R6RS
mailing list