Hi!
In a package I'm writing, the following function is called VERY
often. According to metering.lisp, most of the execution time is spent in this
function. Thus I would like to have it really fast. Here are two versions, is
there another one which is still better?
Note that s-edges and all-edges are rather short lists: In my test, s-edges has
avarage length 3.7 and maximum length 6, all-edges 12.4 and 21 respectively.
Thanks a lot,
Martin
(defstruct edge vertices (weight 1) (key 0 :type fixnum))
;; s-edges and all-edges are lists of edges, I want to have those edges in
;; all-edges that have the same key as the s-edges
;; both lists are sorted by key - which is a unique integer, any key appearing
;; in an s-edge appears also in an edge of all-edges
;; no error checking is necessary
;; version 1
(defun map-edges-sorted (s-edges all-edges)
(when s-edges
(let ((rest (member (edge-key (car s-edges))
all-edges :key 'edge-key :test '=)))
(cons (car rest)
(map-edges-sorted (cdr s-edges) (cdr rest))))))
;; version 2
(defun map-edges-sorted (s-edges all-edges)
(labels ((rec (s-edges all-edges collect)
(if s-edges
(let ((rest
(member (edge-key (car s-edges))
all-edges :key 'edge-key :test '=)))
(rec (cdr s-edges)
(cdr rest)
(cons (car rest) collect)))
collect)))
(nreverse (rec s-edges all-edges nil))))
········@yahoo.de (Martin) wrote in message news:<····························@posting.google.com>...
> Hi!
>
> In a package I'm writing, the following function is called VERY
> often. According to metering.lisp, most of the execution time is spent in this
> function. Thus I would like to have it really fast. Here are two versions, is
> there another one which is still better?
>
> Note that s-edges and all-edges are rather short lists: In my test, s-edges has
> avarage length 3.7 and maximum length 6, all-edges 12.4 and 21 respectively.
>
> Thanks a lot,
> Martin
>
> [... snip ...]
Your algorithm is good. Here is a untested slight re-working of your
first version:
;; version 1
(defun map-edges-sorted (s-edges all-edges &optional (result '()))
(declare (type cons s-edges all-edges result))
(if (null s-edges)
(reverse result)
(let ((match (member (car s-edges) all-edges :key 'edge-key :test
'=)))
(map-edges-sorted (cdr s-edges) (cdr match) (cons (car match)
result)))))
The only difference is that mine is tail-recursive and I declared the
types of the parameters.
Also, make sure you have a (proclaim '(optimize speed)) somewhere
above the function definition so that the tail-recursion will get
optimized into a loop.
Depending on where your data comes from, you may want to consider
using a vector instead of a list, and then changing the recursion into
a loop. A loop over a simple-vector would be faster than recursion
over a list.
But, I'm no LISP guru, or algorithm guru for that matter. Good luck,
Justin Dubs
Martin Somebody wrote:
> In a package I'm writing, the following function is called VERY
> often. According to metering.lisp, most of the execution time is spent in this
> function. Thus I would like to have it really fast. Here are two versions, is
> there another one which is still better?
>
> Note that s-edges and all-edges are rather short lists: In my test, s-edges has
> avarage length 3.7 and maximum length 6, all-edges 12.4 and 21 respectively.
...
> (defstruct edge vertices (weight 1) (key 0 :type fixnum))
>
> ;; s-edges and all-edges are lists of edges, I want to have those edges in
> ;; all-edges that have the same key as the s-edges
> ;; both lists are sorted by key - which is a unique integer, any key appearing
> ;; in an s-edge appears also in an edge of all-edges
> ;; no error checking is necessary
>
> ;; version 1
> (defun map-edges-sorted (s-edges all-edges)
> (when s-edges
> (let ((rest (member (edge-key (car s-edges))
> all-edges :key 'edge-key :test '=)))
> (cons (car rest)
> (map-edges-sorted (cdr s-edges) (cdr rest))))))
>
> ;; version 2
> (defun map-edges-sorted (s-edges all-edges)
> (labels ((rec (s-edges all-edges collect)
> (if s-edges
> (let ((rest
> (member (edge-key (car s-edges))
> all-edges :key 'edge-key :test '=)))
> (rec (cdr s-edges)
> (cdr rest)
> (cons (car rest) collect)))
> collect)))
> (nreverse (rec s-edges all-edges nil))))
You may get better performance in those calls to MEMBER by writing
#'edge-key instead of 'edge-key.
If the total number of edges in the system is modest, you might
want to use completely different data structures -- e.g., bitmaps
to represent sets of edges. I suspect, though, that your sets
are sparse and this would be a bad idea.
If the keys are really unique, there may be some benefit from
having an array somewhere that maps keys to edges, and then
working with lists of keys rather than lists of edges. But
that can't be so, or else MAP-EDGES-SORTED would be the identity
function.
You *might* find that you get better speed by dropping down to
a lower level of abstraction and doing all, or almost all, the
list traversal by hand:
(defun map-edges-sorted (s-edges all-edges)
(when s-edges ;; actually, I prefer AND...
(loop with ks fixnum = (edge-key (first s-edges))
with ka fixnum = (edge-key (first all-edges))
if (< ks ka)
do (unless (setf s-edges (rest s-edges)) (loop-finish))
(setf ks (edge-key (first s-edges)))
else
;; it is guaranteed that (= ks ka) !
collect (first all-edges)
and
do (unless (setf s-edges (rest s-edges)) (loop-finish))
(unless (setf all-edges (rest all-edges)) (loop-finish))
(setf ks (edge-key (first s-edges))
ka (edge-key (first all-edges))))))
More speed might come from sticking (the edge ...) in suitable
places and declaring (optimize (speed 3)).
(defun map-edges-sorted (s-edges all-edges)
(declare (optimize (speed 3)))
(when s-edges ;; actually, I prefer AND...
(loop with ks fixnum = (edge-key (the edge (first s-edges)))
with ka fixnum = (edge-key (the edge (first all-edges)))
if (< ks ka)
do (unless (setf s-edges (rest s-edges)) (loop-finish))
(setf ks (edge-key (first s-edges)))
else
;; it is guaranteed that (= ks ka) !
collect (first all-edges)
and
do (unless (setf s-edges (rest s-edges)) (loop-finish))
(unless (setf all-edges (rest all-edges)) (loop-finish))
(setf ks (edge-key (the edge (first s-edges)))
ka (edge-key (the edge (first all-edges)))))))
Ugh!
--
Gareth McCaughan ················@pobox.com
.sig under construc
Gareth McCaughan <················@pobox.com> wrote in message news:<································@g.local>...
> You may get better performance in those calls to MEMBER by writing
> #'edge-key instead of 'edge-key.
why would this be?
> If the total number of edges in the system is modest, you might
> want to use completely different data structures -- e.g., bitmaps
> to represent sets of edges. I suspect, though, that your sets
> are sparse and this would be a bad idea.
This is indeed the case
> If the keys are really unique, there may be some benefit from
> having an array somewhere that maps keys to edges, and then
> working with lists of keys rather than lists of edges. But
> that can't be so, or else MAP-EDGES-SORTED would be the identity
> function.
???
Thanks a lot,
Martin
* Martin wrote:
> Gareth McCaughan <················@pobox.com> wrote in message news:<································@g.local>...
>> You may get better performance in those calls to MEMBER by writing
>> #'edge-key instead of 'edge-key.
> why would this be?
In the symbol case, something has to find the function associated with
that symbol, and then call it. In the second case you are passing the
function directly, so the extra fetch is (or may be) avoided.
--tim
In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
>* Martin wrote:
>> Gareth McCaughan <················@pobox.com> wrote in message
>news:<································@g.local>...
>>> You may get better performance in those calls to MEMBER by writing
>>> #'edge-key instead of 'edge-key.
>
>> why would this be?
>
>In the symbol case, something has to find the function associated with
>that symbol, and then call it. In the second case you are passing the
>function directly, so the extra fetch is (or may be) avoided.
I hope that any decent implementation will do this just once per call to
MEMBER, not each time the key- or comparison-function is called.
Also, it wouldn't be unreasonable for the compiler to optimize this away.
--
Barry Margolin, ··············@level3.com
Genuity Managed Services, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
"Barry Margolin" <··············@level3.com> wrote in message ··················@paloalto-snr1.gtei.net...
> In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
> >* Martin wrote:
> >> Gareth McCaughan <················@pobox.com> wrote in message
> >news:<································@g.local>...
> >>> You may get better performance in those calls to MEMBER by writing
> >>> #'edge-key instead of 'edge-key.
> >
> >> why would this be?
> >
> >In the symbol case, something has to find the function associated with
> >that symbol, and then call it. In the second case you are passing the
> >function directly, so the extra fetch is (or may be) avoided.
>
> I hope that any decent implementation will do this just once per call to
> MEMBER, not each time the key- or comparison-function is called.
>
> Also, it wouldn't be unreasonable for the compiler to optimize this away.
Just when you thought it was safe to go back into the water...
(defun oddball(y)
(setf (symbol-function 'oddball) (lambda (x) y))
y)
(defun test(list)
(mapcar #'oddball list))
vs.
(defun test2(list)
(mapcar 'oddball list))
Tested on '(1 2 3)
compiled functions: test, test2
LW Allegro CLISP LW Allegro CLISP
test (1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 1 1) (1 2 3)
test2 (1 1 1) (1 1 1) (1 1 1) (1 1 1) (1 1 1) (1 1 1)
I expected test to give (1 2 3) and test2 to give either (1 1 1) or (1 2 3)
with the first being my preferred answer. The description of MAP in the HS
isn't exacting on the timing of the lookup put the placement appears to indicate
that the lookup should occur every time. But I really didn't expect Allegro's
compiled behaviour, it just strikes me as wrong.
---
Geoff
"Martin" <········@yahoo.de> wrote in message ·································@posting.google.com...
> Oh dear, even stranger in gcl:
>
> (defun oddball(y)
> (setf (symbol-function 'oddball) (lambda (x) y))
> y)
>
> (defun test(list)
> (mapcar #'oddball list))
>
>
> (defun test2(list)
> (mapcar 'oddball list))
>
> >(load "tst.lisp")
> >(test (list 1 2 3))
> (1 2 3)
> >(test2 (list 1 2 3))
> (3 3 3)
Naturally, oddball needs to be redefined between the tests.
If you run them without doing that you'll get the last redefinition,
in this case a closure with y as 3.
> >(load "tst.o")
> >(test (list 1 2 3))
> (1 1 1)
> >(test2 (list 1 2 3))
> (1 1 1)
>
GCL isn't particularly compliant anyway, IIRC. Strange though,
both Allegro and GCL appear to return a place pointing to the
functional object from the FUNCTION call in the compiled code
since the definition change is reflected.
Anyone know of a relevant passage(s) in the HS to determine what
these calls should be returning in a correct CL, or is it just
another thing to be avoided?
---
Geoff
"Geoffrey Summerhayes" <·············@hotmail.com> writes:
> Naturally, oddball needs to be redefined between the tests.
> If you run them without doing that you'll get the last redefinition,
> in this case a closure with y as 3.
Stupid me... OK now it gives (1 1 1).
The compiled behaviour stays the same though...
> GCL isn't particularly compliant anyway, IIRC. Strange though,
> both Allegro and GCL appear to return a place pointing to the
> functional object from the FUNCTION call in the compiled code
> since the definition change is reflected.
>
> Anyone know of a relevant passage(s) in the HS to determine what
> these calls should be returning in a correct CL, or is it just
> another thing to be avoided?
I'm not sure. I like the interpreted behaviour better (even though I failed to
reproduce it properly...
Martin
"Geoffrey Summerhayes" <·············@hotmail.com> writes:
> (defun oddball(y)
> (setf (symbol-function 'oddball) (lambda (x) y))
> y)
>
> (defun test(list)
> (mapcar #'oddball list))
>
>
> (defun test2(list)
> (mapcar 'oddball list))
>
> >(test (list 1 2 3))
> (1 1 1)
> >(test2 (list 1 2 3))
> (1 1 1)
>
> Anyone know of a relevant passage(s) in the HS to determine what
> these calls should be returning in a correct CL, or is it just
> another thing to be avoided?
TEST should return (1 2 3). The definition of FUNCTION says, in this
case, that it returns "the global functional definition" of ODDBALL, a
function. The definition of SYMBOL-FUNCTION says SETF SYMBOL-FUNCTION
changes the function cell, which is defined as the place that holds
"the definition of the global function binding". These clearly mean
the same thing. There's no calculus of time and change in the
standard, but still, "the definition" means "the definition at the
time of FUNCTION", to take the result of FUNCTION to be anything but
the function defined by DEFUN ODDBALL is stretching too far. Also, in
the case of FUNCTION, we have the treatment of closures to compare to.
It should be noted, however, that if all three functions are placed in
the same file and compiled, then the results are undefined (so (1 1 1)
is fine), because ANS 3.2.2.3 point 5 applies.
TEST2 is harder from a formal point of view, even though the result is
uncontroversially (1 1 1) from the empirical and pragmatic points of
view. This is because the definition of MAPCAR talks about applying
its first argument, which is defined as a function designator, whereas
the definition of "apply" only talks about functions, not designators.
So it doesn't explicitly say when the designation is resolved.
However, code like this is a thing to be avoided, because it is
wilfully obscure.
--
Pekka P. Pirinen
More than any time in history mankind faces a crossroads. One path
leads to despair and utter hopelessness, the other to total extinction.
Let us pray that we have the wisdom to choose correctly. - Woody Allen
* Barry Margolin wrote:
> I hope that any decent implementation will do this just once per call to
> MEMBER, not each time the key- or comparison-function is called.
Oh, yes, I hadn't noticed that. Ooops.
--tim
"Barry Margolin" <··············@level3.com> wrote in message
··················@paloalto-snr1.gtei.net...
> In article <···············@cley.com>, Tim Bradshaw <···@cley.com> wrote:
> >* Martin wrote:
> >> Gareth McCaughan <················@pobox.com> wrote in message
> >news:<································@g.local>...
> >>> You may get better performance in those calls to MEMBER by writing
> >>> #'edge-key instead of 'edge-key.
> >
> >> why would this be?
> >
> >In the symbol case, something has to find the function associated with
> >that symbol, and then call it. In the second case you are passing the
> >function directly, so the extra fetch is (or may be) avoided.
>
> I hope that any decent implementation will do this just once per call to
> MEMBER, not each time the key- or comparison-function is called.
>
> Also, it wouldn't be unreasonable for the compiler to optimize this away.
it seems to me that it would be wrong (morally at least, if not legally ;)
to do that. If you chose to use the symbol rather than the symbol function
this could indicate that the symbol function will be changing at run time.
This optimization would remove that behaviour.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
An iteration will almost certainly be faster than a recursion unless it is a
tail recursion and the implementation optimizes it.
There are a number of additional considerations -- how often are the
all-edges or s-edges lists modified? Is a single list traversed many times
or just once and then discarded?
If you were going to call this function many times on the same sorted
all-edges list, you might make it doubly linked and start in the middle,
determining which direction to go based on a comparison of keys. If
all-edges were larger, you might use some kind of balanced tree structure.
I was once told that (member ... :test #'eq) was faster than #'eq hash
lookup for lists shorter than about 40 in one of the old Unix lisps, so a
really fancy data structure will probably not help when the lists are this
short.
Jeff
On 8299 day of my life ········@yahoo.de wrote:
> Hi!
>
> In a package I'm writing, the following function is called VERY
> often. According to metering.lisp, most of the execution time is
> spent in this function. Thus I would like to have it really
> fast. Here are two versions, is there another one which is still
> better?
>
> Note that s-edges and all-edges are rather short lists: In my test,
> s-edges has avarage length 3.7 and maximum length 6, all-edges 12.4
> and 21 respectively.
>
> Thanks a lot,
> Martin
>
> (defstruct edge vertices (weight 1) (key 0 :type fixnum))
>
> ;; s-edges and all-edges are lists of edges, I want to have those edges in
> ;; all-edges that have the same key as the s-edges
> ;; both lists are sorted by key - which is a unique integer, any key appearing
> ;; in an s-edge appears also in an edge of all-edges
> ;; no error checking is necessary
>
(defun map-edges-sorted (s-edges all-edges)
(labels ((find-next (key all-edges)
(if (= key
(edge-key (first all-edges)))
(values (first all-edges)
(rest all-edges))
(find-next key (rest all-edges))))
(find-all (s-edges all-edges)
(if (null s-edges)
nil
(multiple-value-bind
(item all-rest) (find-next (edge-key (car s-edges))
all-edges)
(cons item (find-all (rest s-edges) all-rest))))))
(find-all s-edges all-edges)))
I compiled this code, but didn't eval. You may also rewrite
find-all with accumulator and nreverse.
Problem of your implementations is that member doesn't account
ordering of lists, so time of your implementation is O(n*m), where n
and m are lengths of these two lists.
My implementation use each element of all-edges only once, and time is
O(m).
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
There are 256 symbols in English alphabet.
Thanks, your version seems to be really fast. I'll buy it!
(Embarrassing as it is, I have to confess that I found out that I
called map-edges-sorted far too often. However, with your version it
doesn't make much difference...)
Thank you VERY much,
Martin
On 8299 day of my life ········@yahoo.de wrote:
> Thanks, your version seems to be really fast. I'll buy it!
Did you measure a time? I was wrong a little in my posting...
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Perl is a language where 2 x 2 is not equal to 4.
Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote in message news:<·············@elaleph.borges.uiggm.nsc.ru>...
> On 8299 day of my life ········@yahoo.de wrote:
> > Hi!
> >
> > In a package I'm writing, the following function is called VERY
> > often. According to metering.lisp, most of the execution time is
> > spent in this function. Thus I would like to have it really
> > fast. Here are two versions, is there another one which is still
> > better?
> >
> > Note that s-edges and all-edges are rather short lists: In my test,
> > s-edges has avarage length 3.7 and maximum length 6, all-edges 12.4
> > and 21 respectively.
> >
> > Thanks a lot,
> > Martin
> >
> > (defstruct edge vertices (weight 1) (key 0 :type fixnum))
> >
> > ;; s-edges and all-edges are lists of edges, I want to have those edges in
> > ;; all-edges that have the same key as the s-edges
> > ;; both lists are sorted by key - which is a unique integer, any key appearing
> > ;; in an s-edge appears also in an edge of all-edges
> > ;; no error checking is necessary
> >
> (defun map-edges-sorted (s-edges all-edges)
> (labels ((find-next (key all-edges)
> (if (= key
> (edge-key (first all-edges)))
> (values (first all-edges)
> (rest all-edges))
> (find-next key (rest all-edges))))
> (find-all (s-edges all-edges)
> (if (null s-edges)
> nil
> (multiple-value-bind
> (item all-rest) (find-next (edge-key (car s-edges))
> all-edges)
> (cons item (find-all (rest s-edges) all-rest))))))
> (find-all s-edges all-edges)))
>
> I compiled this code, but didn't eval. You may also rewrite
> find-all with accumulator and nreverse.
>
> Problem of your implementations is that member doesn't account
> ordering of lists, so time of your implementation is O(n*m), where n
> and m are lengths of these two lists.
>
> My implementation use each element of all-edges only once, and time is
> O(m).
Actually, No. He was taking the sorting of the lists into account.
Read his code again.
> (let ((rest (member (edge-key (car s-edges)) all-edges :key 'edge-key :test '=)))
> (cons (car rest) (map-edges-sorted (cdr s-edges) (cdr rest))))))
He's recursing on (cdr rest), which he got from the return value of
member. And, as member returns the sublist with the matching element
at the front, he is only traversing the all-edges list once.
His algorithm is O(n+m) with n = length of s-edges, m = length of
all-edges.
A theoretical speed-up could be obtained by finding the matching
element via a recursive halving process, which will make the finding
O(lg m) instead of O(m). However, recursive halving algorithms like
binary tree searching on sorted lists require pretty-much random
access to the list elements. With a linked list this will be slow.
And with lists of his size, I don't think the difference between lg m,
and m is enough to make up for that difference.
Justin Dubs
On 8299 day of my life Justin Dubs wrote:
> Ivan Boldyrev <········@uiggm.nsc.ru.microsoft.com> wrote
> > On 8299 day of my life ········@yahoo.de wrote:
> > > Hi!
> > >
> > Problem of your implementations is that member doesn't account
> > ordering of lists, so time of your implementation is O(n*m), where n
> > and m are lengths of these two lists.
> >
> > My implementation use each element of all-edges only once, and time is
> > O(m).
>
> Actually, No. He was taking the sorting of the lists into account.
Yes, I noticed it later.
> Read his code again.
>
> His algorithm is O(n+m) with n = length of s-edges, m = length of
> all-edges.
As far as n<=m, it is O(m) :) Just simplification.
> A theoretical speed-up could be obtained by finding the matching
> element via a recursive halving process, which will make the finding
> O(lg m) instead of O(m). However, recursive halving algorithms like
> binary tree searching on sorted lists require pretty-much random
> access to the list elements. With a linked list this will be slow.
Random assess to list element is always O(n), where n is distance to
element from first element.
But if original poster used binary trees for all-edges, then
time would be O(n+lg m).
But fastest algorithm would use hash-table, and time would be
O(m). But real constant before m might be too large for such small
lists.
> And with lists of his size, I don't think the difference between lg m,
> and m is enough to make up for that difference.
Exactly.
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
On 8299 day of my life Ivan Boldyrev wrote:
> On 8299 day of my life ········@yahoo.de wrote:
> Problem of your implementations is that member doesn't account
> ordering of lists, so time of your implementation is O(n*m), where n
> and m are lengths of these two lists.
Oh, I am wrong. I forgot thar member returns rest of lisp, not object
itself, and your functions effectively use this fact.
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Outlook has performed an illegal operation and will be shut down.
If the problem persists, contact the program vendor.
OK, I ran some tests: (all compiled, each version in a fresh gcl). It seems
that they all do the same amount of consing. I couldn't compare gareth's
version, because it doesn't do the same thing, unfortunately.
I'd be interested why Ivan's version is faster. Maybe this is implementation
specific? (I use gcl 2.5.0) Or is it the multiple value stuff? Note that my
second version is also tail recursive...
Ah yes, thanks a lot for the oddball example and for the hint to use #' instead
of ' - in fact, it also makes the code clearer, I think.
Thank you very much, Martin.
; Ivan Boldyrev (········@uiggm.nsc.ru)
(defun map-edges-sorted1 (s-edges all-edges)
(labels ((find-next (key all-edges)
(if (= key (edge-key (car all-edges)))
(values (car all-edges)
(cdr all-edges))
(find-next key (cdr all-edges))))
(find-all (s-edges all-edges)
(when s-edges
(multiple-value-bind
(item all-rest) (find-next (edge-key (car s-edges))
all-edges)
(cons item (find-all (cdr s-edges) all-rest))))))
(find-all s-edges all-edges)))
(time (length (g-spanning-trees ($complete_graph 7))))
real time : 16.280 secs
run time : 16.210 secs
16807
real time : 13.670 secs
run time : 13.520 secs
16807
real time : 13.410 secs
run time : 13.170 secs
16807
real time : 13.680 secs
run time : 13.410 secs
16807
; my versions:
(defun map-edges-sorted2 (s-edges all-edges)
(when s-edges
(let ((rest (member (edge-key (car s-edges))
all-edges :key #'edge-key :test #'=)))
(cons (car rest)
(map-edges-sorted (cdr s-edges) (cdr rest))))))
(time (length (g-spanning-trees ($complete_graph 7))))
real time : 20.010 secs
run time : 20.010 secs
16807
real time : 15.550 secs
run time : 15.520 secs
16807
real time : 15.610 secs
run time : 15.580 secs
16807
real time : 16.300 secs
run time : 15.460 secs
16807
(defun map-edges-sorted3 (s-edges all-edges)
(labels ((rec (s-edges all-edges collect)
(if s-edges
(let ((rest
(member (edge-key (car s-edges))
all-edges :key #'edge-key :test #'=)))
(rec (cdr s-edges)
(cdr rest)
(cons (car rest) collect)))
collect)))
(nreverse (rec s-edges all-edges nil))))
>(time (length (g-spanning-trees ($complete_graph 7))))
real time : 21.100 secs
run time : 20.200 secs
16807
real time : 16.020 secs
run time : 15.670 secs
16807
real time : 16.020 secs
run time : 15.630 secs
16807
real time : 16.050 secs
run time : 15.640 secs
16807
Martin wrote:
> OK, I ran some tests: (all compiled, each version in a fresh gcl). It seems
> that they all do the same amount of consing. I couldn't compare gareth's
> version, because it doesn't do the same thing, unfortunately.
Uh-oh. I did warn you that it was untested. How does it differ?
> I'd be interested why Ivan's version is faster. Maybe this is implementation
> specific? (I use gcl 2.5.0) Or is it the multiple value stuff? Note that my
> second version is also tail recursive...
It may be because Ivan's version doesn't call MEMBER. Not because
MEMBER is particularly slow, but because by writing everything
inside the function the compiler has more to play with and optimize.
Some compilers might automatically "expand" calls to MEMBER, but
I bet gcl doesn't.
--
Gareth McCaughan ················@pobox.com
.sig under construc
Gareth McCaughan <················@pobox.com> writes:
> Uh-oh. I did warn you that it was untested. How does it differ?
yes, you did. I don't want to spend more time on this, really. On the other
hand, I think that its an interesting problem... So if you fix your version,
I'll test it! Here is the difference:
>(length (g-spanning-trees ($complete_graph 3)))
"s-edges:"
(#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 2 INDEX NIL))
WEIGHT 1 KEY 2)
#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 1 INDEX NIL))
WEIGHT 1 KEY 3))
"all-edges:"
(#S(EDGE VERTICES
(#S(VERTEX NAME 1 INDEX NIL) #S(VERTEX NAME 2 INDEX NIL))
WEIGHT 1 KEY 1)
#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 2 INDEX NIL))
WEIGHT 1 KEY 2)
#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 1 INDEX NIL))
WEIGHT 1 KEY 3))
"ivan"
(#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 2 INDEX NIL))
WEIGHT 1 KEY 2)
#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 1 INDEX NIL))
WEIGHT 1 KEY 3))
"gareth"
(#S(EDGE VERTICES
(#S(VERTEX NAME 1 INDEX NIL) #S(VERTEX NAME 2 INDEX NIL))
WEIGHT 1 KEY 1)
#S(EDGE VERTICES
(#S(VERTEX NAME 0 INDEX NIL) #S(VERTEX NAME 2 INDEX NIL))
WEIGHT 1 KEY 2))
Error: !
Martin
Martin Rubey wrote:
> Gareth McCaughan <················@pobox.com> writes:
>
> > Uh-oh. I did warn you that it was untested. How does it differ?
>
> yes, you did. I don't want to spend more time on this, really. On the other
> hand, I think that its an interesting problem... So if you fix your version,
> I'll test it! Here is the difference:
[SNIP]
Oh yes, I see. How embarrassing. The point is that when walking
the two lists only two of the possible comparison relations between
the keys of the heads of the lists are possible, and I somehow
managed to latch onto the wrong two :-). Here's the with-declarations
version of the fixed code.
(defun map-edges-sorted (s-edges all-edges)
(declare (optimize (speed 3)))
(when s-edges ;; actually, I prefer AND...
(loop with ks fixnum = (edge-key (the edge (first s-edges)))
with ka fixnum = (edge-key (the edge (first all-edges)))
if (> ks ka)
do (unless (setf all-edges (rest all-edges)) (loop-finish))
(setf ka (edge-key (first all-edges)))
else
;; it is guaranteed that (= ks ka) !
collect (first all-edges)
and
do (unless (setf s-edges (rest s-edges)) (loop-finish))
(setf all-edges (rest all-edges)
ks (edge-key (the edge (first s-edges)))
ka (edge-key (the edge (first all-edges)))))))
For what it's worth, it seems to be about 10% slower than Ivan's code
for me using CMU CL on FreeBSD/x86, once I put a suitable type
declaration into Ivan's code so that it can work with fixnums
everywhere. I don't know how that would translate to GCL performance.
I have another version that runs (for me) about 8% faster than Ivan's,
but it's disgusting. Avert your eyes.
(defun map-edges-sorted (s-edges all-edges)
(declare (optimize (speed 3)))
(when s-edges
(nreverse
(let ((ks 0)
(ka 0)
(result nil))
(declare (fixnum ks ka))
(block nil
(tagbody
0 (setq ks (edge-key (the edge (first s-edges))))
1 (setq ka (edge-key (the edge (first all-edges))))
(if (> ks ka)
(progn
(unless (setf all-edges (rest all-edges))
(return result))
(go 1))
(progn
(push (first all-edges) result)
(unless (setf s-edges (rest s-edges))
(return result))
(setf all-edges (rest all-edges))
(go 0)))))))))
But if you wanted code like that, you'd write in C. Or assembler.
Again, none of my timings are necessarily representative of what
you'll get in GCL. By way of comparison, in CLISP Ivan's code is
substantially slower than either of the two above, and the
"disgusting" one is actually a bit slower than the first one.
All these were at least 6 times faster than your original versions
for me, by the way, which I found very surprising.
--
Gareth McCaughan ················@pobox.com
.sig under construc
On 8300 day of my life ········@yahoo.de wrote:
> OK, I ran some tests: (all compiled, each version in a fresh gcl).
> It seems that they all do the same amount of consing. I couldn't
> compare gareth's version, because it doesn't do the same thing,
> unfortunately.
>
> I'd be interested why Ivan's version is faster. Maybe this is
> implementation specific? (I use gcl 2.5.0)
May be, gcl doesn't inline member call, but in fact I have wrote
task-specific version of member (find-next), so it is faster.
Try another lisp compiler, CMU CL or SBCL.
> Or is it the multiple value stuff? Note that my second version is
> also tail recursive...
In my example, only find-next is tail-recursive, but find-all isn't.
As far as find-next is tail-recursive, it is expanded to loop, and
probably inlined in find-all. So, I think multiple value doesn't
matter here.
> ; Ivan Boldyrev (········@uiggm.nsc.ru)
> (defun map-edges-sorted1 (s-edges all-edges)
> (labels ((find-next (key all-edges)
> (if (= key (edge-key (car all-edges)))
> (values (car all-edges)
> (cdr all-edges))
I return car and cdr of same value! I could return all-edges
and call car/cdr in find-all. And it _might_ be faster.
--
Ivan Boldyrev remove .microsoft.com from my address
PGP fp: 3640 E637 EE3D AA51 A59F 3306 A5BD D198 5609 8673 ID 56098673
Today is the first day of the rest of your life.