>>>>> "SDS" == SDS <···········@cctrading.com> writes:
>>>>> In a very interesting message <·············@WINTERMUTE.eagle>
>>>>> Sent on 26 Aug 1997 16:41:40 -0400 Honorable SDS
>>>>> <···········@cctrading.com> writes on the subject of "dolist vs
>>>>> mapc; length+last ?":
>>>
>>> These are again rather technical and simplistic questions.
>>>
>>> 2. I have several lists (~300 records) and I need to get their
>>> lengths with the last elements. [using arrays is not an option -
>>> I have to concatenate/split them easily]. What is more efficient:
>>> using built-in last and length (traversing each list twice) or
>>> writing my own function (thus traversing only once, but using a
>>> compiled function instead of a built-in one). Yes, I *will* try
>>> to run a benchmark, but I wonder if the answer should be obvious.
SDS> clisp on winnt
SDS> (proclaim '(optimize (speed 3) (space 0) (safety 0) (debug 0)))
SDS> (defun length-last (lst)
SDS> (let ((len 0) cur)
SDS> (declare (fixnum len))
SDS> (dolist (ll lst)
SDS> (incf len) (setq cur ll))
SDS> (values len cur)))
SDS> ;;; compiled
>> (time (length-last (make-list 1000000)))
Timing the previous expression will include the time needed to build
that huge list with 1000000 elements, and we aren't interested in that.
SDS> Real time: 5.858 sec.
SDS> Run time: 5.3376752 sec.
Space> 8000000 Bytes
GC> 6, GC time: 3.5350832 sec.
SDS> 1000000 ;
SDS> nil
>>
SDS> ;;; not compiled
>> (time (length-last (make-list 1000000)))
If you have a compiler, timing a non-compiled function is absurd.
SDS> Real time: 27.019 sec.
SDS> Run time: 25.7970944 sec.
Space> 8000016 Bytes
GC> 4, GC time: 1.9728368 sec.
SDS> 1000000 ;
SDS> nil
Now, using built-in functions:
>> (time (let ((a (make-list 1000000))) (values (length a) (car (last a)))))
Again, most of the time spend in the last expression goes to the
make-list.
SDS> Real time: 2.724 sec.
SDS> Run time: 2.703888 sec.
Space> 8000000 Bytes
GC> 3, GC time: 2.3133264 sec.
SDS> 1000000 ;
SDS> nil
>>
SDS> So, built-in is faster, by the ratio of 2.
No, it isn't. If you exclude the time needed for building the 1000000
conses, you may get quite different results. Here is an example, in
ACL 4.1 for SPARC.
Including (incorrectly) the time needed to build the list:
USER(5): (time (length-last (make-list 1000000)))
cpu time (non-gc) 1850 msec user, 950 msec system
cpu time (gc) 12300 msec user, 2100 msec system
cpu time (total) 14150 msec user, 3050 msec system
real time 22910 msec
space allocation:
1000026 cons cells, 0 symbols, 512 other bytes,
1000000
NIL
Not including the time needed to build the list:
USER(6): (let ((ll (make-list 1000000))) (time (length-last ll)))
cpu time (non-gc) 384 msec user, 17 msec system
cpu time (gc) 0 msec user, 0 msec system
cpu time (total) 384 msec user, 17 msec system
real time 515 msec
space allocation:
1 cons cell, 0 symbols, 32 other bytes,
1000000
NIL
As you see, we timed only the length-last function. We can see that we
reduced from 14150+3050 msec to 384+17 msec. As expected, building
the list was the most expensive operation.
Now, timing the built-in functions:
USER(7): (let ((ll (make-list 1000000))) (time (values (length ll) (car (last ll)))))
cpu time (non-gc) 900 msec user, 0 msec system
cpu time (gc) 0 msec user, 0 msec system
cpu time (total) 900 msec user, 0 msec system
real time 947 msec
space allocation:
7 cons cells, 0 symbols, 32 other bytes,
1000000
NIL
A bit slower, which contradicts your results.
SDS> Should it have been obvious? Why?
Counting and returning the last element are such simple operations
that there shouldn't be much difference between a compiled function
and an hand-coded built-in function. As a result, we can only
optimize on the number of times we travel the list. Traveling twice
(using the built-in functions) should be more time consuming than
traveling once (as we do using length-last).
Hope this helps,
Ant�nio Menezes Leit�o.