|
From: antirez <an...@in...> - 2004-02-06 15:05:06
|
On Fri, Jan 30, 2004 at 09:21:35AM +0100, David N. Welton wrote:
>
> So, everyone seems to complain about the lists tests, and I don't
> blame them.
>
> Maybe what we need are two tests, one where linked list
> implementations will win, and another where vectors underneath will
> win? So that would be 'list' and 'vector'...
That's a first try for a list test. Here the winners should
be languages implementing lists as real linked stuctures.
# Note: the K combinator may speed-up this a lot
# but as this code is for 'reference' better to take
# it this way for now.
set N $argv
# Populate the L1 list with a random function
set X 41
set L1 {}
for {set i 0} {$i < $N} {incr i} {
set X [expr ($i+($X*17))%$N]
lappend L1 $X
}
# Create a new list L2 inserting every element of L1 so that the L2 list
# remains ordered.
set L2 {}
set len 0
foreach e $L1 {
for {set i 0} {$i < $len} {incr i} {
if {[lindex $L2 $i] >= $e} break
}
set L2 [linsert $L2 $i $e]
incr len
}
# For every element in L2, remove the first element with the same
# value from L1 (so the L1 list become every step shorter).
foreach e $L2 {
set idx [lsearch -exact $L1 $e]
set L1 [lreplace $L1 $idx $idx]
}
puts [llength $L1]
The correct output is always 0
--
Salvatore Sanfilippo <antirez at invece dot org>
"However, there is a tension between making the language simpler and making the
organization of a system manifest. As the variety of costructs decreases, so
does the variety of linguistic clues of a system's structure." (Ungar and Smith)
|