(defun lastvec (m)
(loop for i from 0 below (array-dimension m 0)
collect (aref m i (1- (array-dimension m 1)))))
(defun upper-triangular-solve! (A &aux (b (lastvec A)) &key (n (length
b)))
...)
If you don't want to change UPPER-TRIANGULAR-SOLVE!, write a wrapper
for it.
Leslie
On Jun 27, 7:57 am, "Leslie P. Polzer" <·············@gmx.net> wrote:
> (defun lastvec (m)
> (loop for i from 0 below (array-dimension m 0)
> collect (aref m i (1- (array-dimension m 1)))))
>
> (defun upper-triangular-solve! (A &aux (b (lastvec A)) &key (n (length
> b)))
> ...)
>
> If you don't want to change UPPER-TRIANGULAR-SOLVE!, write a wrapper
> for it.
>
> Leslie
Wouldn't collect return a list? i.e. don't you need (coerce
(loop ...) 'vector) around the list?
Mirko
> Wouldn't collect return a list? i.e. don't you need (coerce
> (loop ...) 'vector) around the list?
Yeah, right. And the AUX part needs to go after the KEY part.
On 27 Jun., 16:14, Francogrex <······@grex.org> wrote:
> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
>
> > > Wouldn't collect return a list? i.e. don't you need (coerce
> > > (loop ...) 'vector) around the list?
>
> > Yeah, right. And the AUX part needs to go after the KEY part.
>
> Ok thanks. but how to I coerce this list into a vector?
> because if I do this:> (vector (lastvec m))
>
> #((2.0 3.0 2.5))
>
> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
(read-from-string (princ-to-string (vector (lastvec m))) nil
nil :start 2)
...but seriously - I think you want one of those:
(coerce (lastvec m) 'vector)
(map 'list #'identity (lastvec m))
The latter would be particularily good if you plan to do something on
each element first (so you would call another function than
#'identity).
It is a good idea to declare the type of the list - at least in
LispWorks it really makes a difference:
(defun to-vector (list) (declare (type list list)) (coerce list
'vector))
Will compile to code that calls the LispWorks dependend internal
functions SYSTEM::LIST-TO-SIMPLE-VECTOR instead of the more general
internal function SYSTEM::COERCE-TO-VECTOR. The first one is (as the
name might suggest) faster for lists than the latter, more generic
one.
--
Jochen Schmidt
CRISPYLOGICS
Julienstr. 1, 90419 Nuremberg
Fon +49 (0)911 517 999 82
Fax +49 (0)911 517 999 83
mailto:(format nil "~(····@~36r.~36r~)" 870180 1680085828711918828
16438) http://www.crispylogics.com
On 27 Jun., 18:35, Jochen Schmidt <····@crispylogics.com> wrote:
> (map 'list #'identity (lastvec m))
should be
(map 'vector #'identity (lastvec m))
of course.
MAP is quite nice for doing vector calculations:
(defun vector+ (a b)
(map 'vector #'+ a b))
The nice thing is that you can use add any sequence using this VECTOR+
(vector+ #(1 2 3) '(1 2 3))
=> #(2 4 6)
ciao,
Jochen
--
Jochen Schmidt
CRISPYLOGICS
Julienstr. 1, 90419 Nuremberg
Fon +49 (0)911 517 999 82
Fax +49 (0)911 517 999 83
mailto:(format nil "~(····@~36r.~36r~)" 870180 1680085828711918828
16438) http://www.crispylogics.com
>
> The latter would be particularily good if you plan to do something on
> each element first (so you would call another function than
> #'identity).
>
> It is a good idea to declare the type of the list - at least in
> LispWorks it really makes a difference:
>
> (defun to-vector (list) (declare (type list list)) (coerce list
> 'vector))
>
> Will compile to code that calls the LispWorks dependend internal
> functions SYSTEM::LIST-TO-SIMPLE-VECTOR instead of the more general
> internal function SYSTEM::COERCE-TO-VECTOR. The first one is (as the
> name might suggest) faster for lists than the latter, more generic
> one.
>
> --
> Jochen Schmidt
> CRISPYLOGICS
> Julienstr. 1, 90419 Nuremberg
>
> Fon +49 (0)911 517 999 82
> Fax +49 (0)911 517 999 83
>
> mailto:(format nil "~(····@~36r.~36r~)" 870180 1680085828711918828
> 16438)http://www.crispylogics.com
In article
<····································@m36g2000hse.googlegroups.com>,
"Leslie P. Polzer" <·············@gmx.net> wrote:
> > Wouldn't collect return a list? i.e. don't you need (coerce
> > (loop ...) 'vector) around the list?
>
> Yeah, right. And the AUX part needs to go after the KEY part.
and you don't want to retrieve the array dimension in the
loop in each iteration...
--
http://lispm.dyndns.org/
Francogrex <······@grex.org> writes:
> On Jun 27, 4:03�pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
>> > Wouldn't collect return a list? �i.e. don't you need (coerce
>> > (loop ...) 'vector) around the list?
>>
>> Yeah, right. And the AUX part needs to go after the KEY part.
>
> Ok thanks. but how to I coerce this list into a vector?
> because if I do this:
>> (vector (lastvec m))
> #((2.0 3.0 2.5))
>
> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
Read the hyperspec page about the function VECTOR and compare with COERCE.
--
__Pascal Bourguignon__
On Jun 27, 4:14 pm, Francogrex <······@grex.org> wrote:
> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
>
> > > Wouldn't collect return a list? i.e. don't you need (coerce
> > > (loop ...) 'vector) around the list?
>
> > Yeah, right. And the AUX part needs to go after the KEY part.
>
> Ok thanks. but how to I coerce this list into a vector?
> because if I do this:> (vector (lastvec m))
>
> #((2.0 3.0 2.5))
>
> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
(loop for x in (list 1 2 3)
collect x into r
finally (return (coerce r 'vector)))
or
(loop with r = (make-array (length the-list))
for x in the-list
for i from 0
do (setf (aref r i) x)
finally (return r))
or
(map 'vector 'identity (loop for x in (list 1 2 3) collect x))
Cheers
--
Marco
Marco Antoniotti wrote:
> On Jun 27, 4:14 pm, Francogrex <······@grex.org> wrote:
>> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
>>
>>>> Wouldn't collect return a list? i.e. don't you need (coerce
>>>> (loop ...) 'vector) around the list?
>>> Yeah, right. And the AUX part needs to go after the KEY part.
>> Ok thanks. but how to I coerce this list into a vector?
>> because if I do this:> (vector (lastvec m))
>>
>> #((2.0 3.0 2.5))
>>
>> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
>
> (loop for x in (list 1 2 3)
> collect x into r
> finally (return (coerce r 'vector)))
>
> or
>
> (loop with r = (make-array (length the-list))
> for x in the-list
> for i from 0
> do (setf (aref r i) x)
> finally (return r))
>
> or
>
> (map 'vector 'identity (loop for x in (list 1 2 3) collect x))
I think all these solutions have the disadvantage that they have to
traverse the lists twice, right?
What about this?
(loop for x in '(1 2 3)
collect x into r
count t into length
finally (return (map-into (make-array length) 'identity r)))
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
In article <···············@mid.individual.net>,
Pascal Costanza <··@p-cos.net> wrote:
> Marco Antoniotti wrote:
> > On Jun 27, 4:14 pm, Francogrex <······@grex.org> wrote:
> >> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
> >>
> >>>> Wouldn't collect return a list? i.e. don't you need (coerce
> >>>> (loop ...) 'vector) around the list?
> >>> Yeah, right. And the AUX part needs to go after the KEY part.
> >> Ok thanks. but how to I coerce this list into a vector?
> >> because if I do this:> (vector (lastvec m))
> >>
> >> #((2.0 3.0 2.5))
> >>
> >> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
> >
> > (loop for x in (list 1 2 3)
> > collect x into r
> > finally (return (coerce r 'vector)))
> >
> > or
> >
> > (loop with r = (make-array (length the-list))
> > for x in the-list
> > for i from 0
> > do (setf (aref r i) x)
> > finally (return r))
> >
> > or
> >
> > (map 'vector 'identity (loop for x in (list 1 2 3) collect x))
>
> I think all these solutions have the disadvantage that they have to
> traverse the lists twice, right?
>
> What about this?
>
> (loop for x in '(1 2 3)
> collect x into r
> count t into length
> finally (return (map-into (make-array length) 'identity r)))
>
>
> Pascal
(make-array length :initial-contents r)
Though the whole form makes only sense if there is some
filtering going on:
(loop for x in '(1 2 3)
when (oddp x)
collect x into r and count t into length
finally (return (make-array length :initial-contents r)))
--
http://lispm.dyndns.org/
On Jun 28, 12:52 pm, Rainer Joswig <······@lisp.de> wrote:
> In article <···············@mid.individual.net>,
> Pascal Costanza <····@p-cos.net> wrote:
>
>
>
> > Marco Antoniotti wrote:
> > > On Jun 27, 4:14 pm, Francogrex <······@grex.org> wrote:
> > >> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
>
> > >>>> Wouldn't collect return a list? i.e. don't you need (coerce
> > >>>> (loop ...) 'vector) around the list?
> > >>> Yeah, right. And the AUX part needs to go after the KEY part.
> > >> Ok thanks. but how to I coerce this list into a vector?
> > >> because if I do this:> (vector (lastvec m))
>
> > >> #((2.0 3.0 2.5))
>
> > >> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
>
> > > (loop for x in (list 1 2 3)
> > > collect x into r
> > > finally (return (coerce r 'vector)))
>
> > > or
>
> > > (loop with r = (make-array (length the-list))
> > > for x in the-list
> > > for i from 0
> > > do (setf (aref r i) x)
> > > finally (return r))
>
> > > or
>
> > > (map 'vector 'identity (loop for x in (list 1 2 3) collect x))
>
> > I think all these solutions have the disadvantage that they have to
> > traverse the lists twice, right?
>
> > What about this?
>
> > (loop for x in '(1 2 3)
> > collect x into r
> > count t into length
> > finally (return (map-into (make-array length) 'identity r)))
>
> > Pascal
>
> (make-array length :initial-contents r)
>
> Though the whole form makes only sense if there is some
> filtering going on:
>
> (loop for x in '(1 2 3)
> when (oddp x)
> collect x into r and count t into length
> finally (return (make-array length :initial-contents r)))
>
> --http://lispm.dyndns.org/
Microbenchmarking time!
Here is the code (of course the code is bogus and this just tests
allocation and looping and whatnot).
Bottom line: as expected, don't do double allocation!
(defun vector-collect-coerce (n)
(loop for x from 0 below n
collect x into r
finally (return (coerce r 'vector))))
(defun vector-collect-setf (n)
(loop with r = (make-array n)
for x from 0 below n
do (setf (aref r x) x)
finally (return r)))
(defun vector-collect-map (n)
(map 'vector 'identity (loop for x from 0 below n collect x)))
(defun vector-collect-make-array (n)
(loop for x from 0 below n
collect x into r
finally (return (make-array n :initial-contents r))))
(defun test (&optional (n 100000))
(time (vector-collect-coerce n))
(time (vector-collect-setf n))
(time (vector-collect-map n))
(time (vector-collect-make-array n))
t
)
and here is the test (run on LWM and Allegro 8.1 Mac, Intel)
LWM
CL-USER 5 > (test 1000000)
Timing the evaluation of (VECTOR-COLLECT-COERCE N)
User time = 0.282
System time = 0.005
Elapsed time = 0.306
Allocation = 16003940 bytes
934 Page faults
Timing the evaluation of (VECTOR-COLLECT-SETF N)
User time = 0.031
System time = 0.000
Elapsed time = 0.049
Allocation = 4003076 bytes
0 Page faults
Timing the evaluation of (VECTOR-COLLECT-MAP N)
User time = 0.753
System time = 0.015
Elapsed time = 0.808
Allocation = 16002688 bytes
2849 Page faults
Timing the evaluation of (VECTOR-COLLECT-MAKE-ARRAY N)
User time = 0.140
System time = 0.000
Elapsed time = 0.180
Allocation = 16002400 bytes
0 Page faults
T
ACL
CL-USER> (test 1000000)
VECTOR-COLLECT-COERCE
; cpu time (non-gc) 50 msec user, 0 msec system
; cpu time (gc) 60 msec user, 0 msec system
; cpu time (total) 110 msec user, 0 msec system
; real time 111 msec
; space allocation:
; 1,000,001 cons cells, 4,000,016 other bytes, 0 static bytes
VECTOR-COLLECT-SETF
; cpu time (non-gc) 30 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 30 msec user, 0 msec system
; real time 22 msec
; space allocation:
; 1 cons cell, 4,000,016 other bytes, 0 static bytes
VECTOR-COLLECT-MAP
; cpu time (non-gc) 90 msec user, 0 msec system
; cpu time (gc) 30 msec user, 0 msec system
; cpu time (total) 120 msec user, 0 msec system
; real time 128 msec
; space allocation:
; 1,000,002 cons cells, 4,000,016 other bytes, 0 static bytes
VECTOR-COLLECT-MAKE-ARRAY
; cpu time (non-gc) 40 msec user, 0 msec system
; cpu time (gc) 60 msec user, 0 msec system
; cpu time (total) 100 msec user, 0 msec system
; real time 97 msec
; space allocation:
; 1,000,003 cons cells, 4,000,016 other bytes, 0 static bytes
T
Cheers
--
Marco
In article
<····································@d45g2000hsc.googlegroups.com>,
Marco Antoniotti <·······@gmail.com> wrote:
> On Jun 28, 12:52�pm, Rainer Joswig <······@lisp.de> wrote:
> > In article <···············@mid.individual.net>,
> > �Pascal Costanza <····@p-cos.net> wrote:
> >
> >
> >
> > > Marco Antoniotti wrote:
> > > > On Jun 27, 4:14 pm, Francogrex <······@grex.org> wrote:
> > > >> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
> >
> > > >>>> Wouldn't collect return a list? �i.e. don't you need (coerce
> > > >>>> (loop ...) 'vector) around the list?
> > > >>> Yeah, right. And the AUX part needs to go after the KEY part.
> > > >> Ok thanks. but how to I coerce this list into a vector?
> > > >> because if I do this:> (vector (lastvec m))
> >
> > > >> #((2.0 3.0 2.5))
> >
> > > >> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
> >
> > > > (loop for x in (list 1 2 3)
> > > > � � � collect x into r
> > > > � � � finally (return (coerce r 'vector)))
> >
> > > > or
> >
> > > > (loop with r = (make-array (length the-list))
> > > > � � � for x in the-list
> > > > � � � for i from 0
> > > > � � � do (setf (aref r i) x)
> > > > � � � finally (return r))
> >
> > > > or
> >
> > > > (map 'vector 'identity (loop for x in (list 1 2 3) collect x))
> >
> > > I think all these solutions have the disadvantage that they have to
> > > traverse the lists twice, right?
> >
> > > What about this?
> >
> > > (loop for x in '(1 2 3)
> > > � � � �collect x into r
> > > � � � �count t into length
> > > � � � �finally (return (map-into (make-array length) 'identity r)))
> >
> > > Pascal
> >
> > (make-array length :initial-contents r)
> >
> > Though the whole form makes only sense if there is some
> > filtering going on:
> >
> > (loop for x in '(1 2 3)
> > � � � when (oddp x)
> > � � � collect x into r and count t into length
> > � � � finally (return (make-array length :initial-contents r)))
> >
> > --http://lispm.dyndns.org/
>
> Microbenchmarking time!
>
> Here is the code (of course the code is bogus and this just tests
> allocation and looping and whatnot).
>
> Bottom line: as expected, don't do double allocation!
>
> (defun vector-collect-coerce (n)
> (loop for x from 0 below n
> collect x into r
> finally (return (coerce r 'vector))))
>
>
> (defun vector-collect-setf (n)
> (loop with r = (make-array n)
> for x from 0 below n
> do (setf (aref r x) x)
> finally (return r)))
>
>
> (defun vector-collect-map (n)
> (map 'vector 'identity (loop for x from 0 below n collect x)))
>
>
> (defun vector-collect-make-array (n)
> (loop for x from 0 below n
> collect x into r
> finally (return (make-array n :initial-contents r))))
>
>
> (defun test (&optional (n 100000))
> (time (vector-collect-coerce n))
> (time (vector-collect-setf n))
> (time (vector-collect-map n))
> (time (vector-collect-make-array n))
> t
> )
Try these:
(defun vector-replace (n)
(let ((r (make-array n)))
(replace r r)))
(defun vector-collect-replace (n)
(loop for x from 0 below n
collect x into r
finally (return (replace (make-array n) r))))
Did you compile it? Maybe time to upgrade?
My 64bit LispWorks is quite a bit faster on a MacBook Pro with 2.33Ghz.
May I say that 64bit LispWorks rocks?! ;-)
>
> and here is the test (run on LWM and Allegro 8.1 Mac, Intel)
>
> LWM
>
> CL-USER 5 > (test 1000000)
> Timing the evaluation of (VECTOR-COLLECT-COERCE N)
>
> User time = 0.282
> System time = 0.005
> Elapsed time = 0.306
> Allocation = 16003940 bytes
> 934 Page faults
> Timing the evaluation of (VECTOR-COLLECT-SETF N)
>
> User time = 0.031
> System time = 0.000
> Elapsed time = 0.049
> Allocation = 4003076 bytes
> 0 Page faults
> Timing the evaluation of (VECTOR-COLLECT-MAP N)
>
> User time = 0.753
> System time = 0.015
> Elapsed time = 0.808
> Allocation = 16002688 bytes
> 2849 Page faults
> Timing the evaluation of (VECTOR-COLLECT-MAKE-ARRAY N)
>
> User time = 0.140
> System time = 0.000
> Elapsed time = 0.180
> Allocation = 16002400 bytes
> 0 Page faults
> T
>
> ACL
>
> CL-USER> (test 1000000)
>
> VECTOR-COLLECT-COERCE
> ; cpu time (non-gc) 50 msec user, 0 msec system
> ; cpu time (gc) 60 msec user, 0 msec system
> ; cpu time (total) 110 msec user, 0 msec system
> ; real time 111 msec
> ; space allocation:
> ; 1,000,001 cons cells, 4,000,016 other bytes, 0 static bytes
> VECTOR-COLLECT-SETF
> ; cpu time (non-gc) 30 msec user, 0 msec system
> ; cpu time (gc) 0 msec user, 0 msec system
> ; cpu time (total) 30 msec user, 0 msec system
> ; real time 22 msec
> ; space allocation:
> ; 1 cons cell, 4,000,016 other bytes, 0 static bytes
> VECTOR-COLLECT-MAP
> ; cpu time (non-gc) 90 msec user, 0 msec system
> ; cpu time (gc) 30 msec user, 0 msec system
> ; cpu time (total) 120 msec user, 0 msec system
> ; real time 128 msec
> ; space allocation:
> ; 1,000,002 cons cells, 4,000,016 other bytes, 0 static bytes
> VECTOR-COLLECT-MAKE-ARRAY
> ; cpu time (non-gc) 40 msec user, 0 msec system
> ; cpu time (gc) 60 msec user, 0 msec system
> ; cpu time (total) 100 msec user, 0 msec system
> ; real time 97 msec
> ; space allocation:
> ; 1,000,003 cons cells, 4,000,016 other bytes, 0 static bytes
> T
>
> Cheers
> --
> Marco
--
http://lispm.dyndns.org/
On Jun 28, 9:32 pm, Rainer Joswig <······@lisp.de> wrote:
> In article
> <····································@d45g2000hsc.googlegroups.com>,
> Marco Antoniotti <·······@gmail.com> wrote:
>
>
>
> > On Jun 28, 12:52 pm, Rainer Joswig <······@lisp.de> wrote:
> > > In article <···············@mid.individual.net>,
> > > Pascal Costanza <····@p-cos.net> wrote:
>
> > > > Marco Antoniotti wrote:
> > > > > On Jun 27, 4:14 pm, Francogrex <······@grex.org> wrote:
> > > > >> On Jun 27, 4:03 pm, "Leslie P. Polzer" <·············@gmx.net> wrote:
>
> > > > >>>> Wouldn't collect return a list? i.e. don't you need (coerce
> > > > >>>> (loop ...) 'vector) around the list?
> > > > >>> Yeah, right. And the AUX part needs to go after the KEY part.
> > > > >> Ok thanks. but how to I coerce this list into a vector?
> > > > >> because if I do this:> (vector (lastvec m))
>
> > > > >> #((2.0 3.0 2.5))
>
> > > > >> while what I need is #(2.0 3.0 2.5) with only one set of parenthesis?
>
> > > > > (loop for x in (list 1 2 3)
> > > > > collect x into r
> > > > > finally (return (coerce r 'vector)))
>
> > > > > or
>
> > > > > (loop with r = (make-array (length the-list))
> > > > > for x in the-list
> > > > > for i from 0
> > > > > do (setf (aref r i) x)
> > > > > finally (return r))
>
> > > > > or
>
> > > > > (map 'vector 'identity (loop for x in (list 1 2 3) collect x))
>
> > > > I think all these solutions have the disadvantage that they have to
> > > > traverse the lists twice, right?
>
> > > > What about this?
>
> > > > (loop for x in '(1 2 3)
> > > > collect x into r
> > > > count t into length
> > > > finally (return (map-into (make-array length) 'identity r)))
>
> > > > Pascal
>
> > > (make-array length :initial-contents r)
>
> > > Though the whole form makes only sense if there is some
> > > filtering going on:
>
> > > (loop for x in '(1 2 3)
> > > when (oddp x)
> > > collect x into r and count t into length
> > > finally (return (make-array length :initial-contents r)))
>
> > > --http://lispm.dyndns.org/
>
> > Microbenchmarking time!
>
> > Here is the code (of course the code is bogus and this just tests
> > allocation and looping and whatnot).
>
> > Bottom line: as expected, don't do double allocation!
>
> > (defun vector-collect-coerce (n)
> > (loop for x from 0 below n
> > collect x into r
> > finally (return (coerce r 'vector))))
>
> > (defun vector-collect-setf (n)
> > (loop with r = (make-array n)
> > for x from 0 below n
> > do (setf (aref r x) x)
> > finally (return r)))
>
> > (defun vector-collect-map (n)
> > (map 'vector 'identity (loop for x from 0 below n collect x)))
>
> > (defun vector-collect-make-array (n)
> > (loop for x from 0 below n
> > collect x into r
> > finally (return (make-array n :initial-contents r))))
>
> > (defun test (&optional (n 100000))
> > (time (vector-collect-coerce n))
> > (time (vector-collect-setf n))
> > (time (vector-collect-map n))
> > (time (vector-collect-make-array n))
> > t
> > )
>
> Try these:
>
> (defun vector-replace (n)
> (let ((r (make-array n)))
> (replace r r)))
>
> (defun vector-collect-replace (n)
> (loop for x from 0 below n
> collect x into r
> finally (return (replace (make-array n) r))))
>
> Did you compile it? Maybe time to upgrade?
> My 64bit LispWorks is quite a bit faster on a MacBook Pro with 2.33Ghz.
> May I say that 64bit LispWorks rocks?! ;-)
Yep. I forgot the REPLACE version. And yes. I compiled everything
(no optimizations), but I am running everything in 32bits.
Bottom line: LOOP cannot be extended portably. Otherwise we would be
able to write
(loop for i from o below n
insert (+ 1 42) into (make-array n :element-type integer) of-
type (array integer))
which is, of course, the LOOP WITH form or the
(map '(vector integer) 'identity int-list)
Cheers
--
Marco
>
>
>
>
>
> > and here is the test (run on LWM and Allegro 8.1 Mac, Intel)
>
> > LWM
>
> > CL-USER 5 > (test 1000000)
> > Timing the evaluation of (VECTOR-COLLECT-COERCE N)
>
> > User time = 0.282
> > System time = 0.005
> > Elapsed time = 0.306
> > Allocation = 16003940 bytes
> > 934 Page faults
> > Timing the evaluation of (VECTOR-COLLECT-SETF N)
>
> > User time = 0.031
> > System time = 0.000
> > Elapsed time = 0.049
> > Allocation = 4003076 bytes
> > 0 Page faults
> > Timing the evaluation of (VECTOR-COLLECT-MAP N)
>
> > User time = 0.753
> > System time = 0.015
> > Elapsed time = 0.808
> > Allocation = 16002688 bytes
> > 2849 Page faults
> > Timing the evaluation of (VECTOR-COLLECT-MAKE-ARRAY N)
>
> > User time = 0.140
> > System time = 0.000
> > Elapsed time = 0.180
> > Allocation = 16002400 bytes
> > 0 Page faults
> > T
>
> > ACL
>
> > CL-USER> (test 1000000)
>
> > VECTOR-COLLECT-COERCE
> > ; cpu time (non-gc) 50 msec user, 0 msec system
> > ; cpu time (gc) 60 msec user, 0 msec system
> > ; cpu time (total) 110 msec user, 0 msec system
> > ; real time 111 msec
> > ; space allocation:
> > ; 1,000,001 cons cells, 4,000,016 other bytes, 0 static bytes
> > VECTOR-COLLECT-SETF
> > ; cpu time (non-gc) 30 msec user, 0 msec system
> > ; cpu time (gc) 0 msec user, 0 msec system
> > ; cpu time (total) 30 msec user, 0 msec system
> > ; real time 22 msec
> > ; space allocation:
> > ; 1 cons cell, 4,000,016 other bytes, 0 static bytes
> > VECTOR-COLLECT-MAP
> > ; cpu time (non-gc) 90 msec user, 0 msec system
> > ; cpu time (gc) 30 msec user, 0 msec system
> > ; cpu time (total) 120 msec user, 0 msec system
> > ; real time 128 msec
> > ; space allocation:
> > ; 1,000,002 cons cells, 4,000,016 other bytes, 0 static bytes
> > VECTOR-COLLECT-MAKE-ARRAY
> > ; cpu time (non-gc) 40 msec user, 0 msec system
> > ; cpu time (gc) 60 msec user, 0 msec system
> > ; cpu time (total) 100 msec user, 0 msec system
> > ; real time 97 msec
> > ; space allocation:
> > ; 1,000,003 cons cells, 4,000,016 other bytes, 0 static bytes
> > T
>
> > Cheers
> > --
> > Marco
>
> --http://lispm.dyndns.org/
On Sat, 28 Jun 2008 12:52:06 +0200, Rainer Joswig <······@lisp.de> said:
| ...
| Though the whole form makes only sense if there is some
| filtering going on:
| (loop for x in '(1 2 3)
| when (oddp x)
| collect x into r and count t into length
| finally (return (make-array length :initial-contents r)))
With filtering, when we know the length M of the initial sequence,
but we don't know the count N of the values that the filter will
keep, yet another approach to measure would be to start by
allocating the result vector to be of size M and adjustable, count
as we filter into it, and shrink it to size N at the end. (Do this
several times in a row to see any effects from fragmentation.) This
avoids double allocation at the cost of adjustability. E.g. the
above becomes
(loop with args = '(1 2 3)
and m = 3 ;rather than (length args) to emphazise that we know it already
with results = (make-array m :adjustable t)
and n = 0 ;or let results have a fill pointer and use that
for x in args
when (oddp x)
do (setf (aref results n) x)
(incf n)
finally (adjust-array results n)
(return results))
Obviously, if we know the expected values of M and N (or at least
their ratio, on which the actual cost of double allocation depends),
we may be able to make a better informed choice among all possible
variants.
The road to premature optimization may well be paved with
microbenchmarks, though...
---Vassil.
--
Peius melius est. ---Ricardus Gabriel.
Pascal Costanza <··@p-cos.net> writes:
>
> I think all these solutions have the disadvantage that they have to
> traverse the lists twice, right?
>
> What about this?
>
> (loop for x in '(1 2 3)
> collect x into r
> count t into length
> finally (return (map-into (make-array length) 'identity r)))
Well, this also traverses the list twice. Once in the loop and once in
the MAP-INTO.
I don't think there is any solution that would avoid that, since the two
items of information that one needs is the length of the list and then
one has to process the elements. But one can't process the elements
without first knowing the length of the list, since otherwise a vector
of the required size cannot be constructed.
Using an adjustable vector with fill pointers may appear to avoid the
need to know the size, but it can hide the fact that the processing time
can be something like O(n^2) or O(n log n) instead, with the need to
perform internal copying when the initial guess as to vector size turns
out to be wrong.
--
Thomas A. Russ, USC/Information Sciences Institute
On 30 Jun 2008 12:23:50 -0700, ···@sevak.isi.edu (Thomas A. Russ) said:
| ...
| I don't think there is any solution that would avoid [traversing the
| list twice], since the two items of information that one needs is
| the length of the list and then one has to process the elements.
| But one can't process the elements without first knowing the length
| of the list, since otherwise a vector of the required size cannot be
| constructed.
| Using an adjustable vector with fill pointers may appear to avoid the
| need to know the size, but it can hide the fact that the processing time
| can be something like O(n^2) or O(n log n) instead, with the need to
| perform internal copying when the initial guess as to vector size turns
| out to be wrong.
One could allocate the array with the maximum size initially and
shrink it at the end; at least for some values of the length of the
argument list and the length of the result (and their ration), and
for some implementations, this ought not to be a bad deal. (The
result does not have to have a fill pointer.)
---Vassil.
--
Peius melius est. ---Ricardus Gabriel.