NetNews Usenet Archive 1992 #27/NN_1992_27.iso/spool/comp/lang/lisp/2936

Internet Message Format | 1992-11-16 | 3.8 KB

Xref: sparky comp.lang.lisp:2936 comp.lang.lisp.mcl:1657
Path: sparky!uunet!zaphod.mps.ohio-state.edu!usc!sol.ctr.columbia.edu!ira.uka.de!sbusol.rz.uni-sb.de!coli.uni-sb.de!mp-mac10.coli.uni-sb.de!espen
From: Espen J. Vestre <[e-mail]>
Newsgroups: comp.lang.lisp,comp.lang.lisp.mcl
Subject: Re: remove
Date: 23 Nov 1992 09:12:55 GMT
Organization: Computerlinguistik, Universitaet des Saarlandes
Lines: 83
Distribution: world
Message-ID: <[e-mail]>
References: <[e-mail]>
NNTP-Posting-Host: mp-mac10.coli.uni-sb.de
X-UserAgent: Nuntius v1.1.1d12
X-XXMessage-ID: <[e-mail]>
X-XXDate: Mon, 23 Nov 92 08:57:18 GMT

In article <[e-mail]> Hallvard Tr{tteberg,
[e-mail] writes:
>Time-ing shows a big difference:
>
>(DOTIMES (A 1000) (DOTIMES (B 8) (FASTER-REMOVE B '(1 2 3 4 5 1 2 3 4
>5)))) took 2421 milliseconds (2.421 seconds) to run.
>Of that, 117 milliseconds (0.117 seconds) were spent in The
>Cooperative Multitasking Experience.
> 240000 bytes of memory allocated.
>NIL
>?
>(DOTIMES (A 1000) (DOTIMES (B 8) (REMOVE B '(1 2 3 4 5 1 2 3 4 5))))
>took 6966 milliseconds (6.966 seconds) to run.
>Of that, 376 milliseconds (0.376 seconds) were spent in The
>Cooperative Multitasking Experience.
> 640000 bytes of memory allocated.
>NIL
>
>I know my function isn't as general as remove since it only works on
>lists and doesn't take all those arguments. But I feel remove should
>be optimized for the simplest cases and also should try to cons as
>little as possible. As the results show, faster-remove (or should it
>be called low-consing-remove) is far better when it comes to consing.
>

[hei Hallvard, hyggelig aa se at det fortsatt programmeres i MCL paa SI!]

Hallvard,

Your function can definitely be faster for several purposes, but because
it isn't tail-recursive, it's not as general in its applicability as
REMOVE: It doesn't work for large lists.
In the following example, the value of TSTLIST is the list
  (10000 9999 ... 2 1):

? (room)
There are at least 12185032 bytes of available RAM.

                  Total Size            Free               Used
Mac Heap:       972552 (949K)       361152 (352K)       611400 (598K)
Lisp Heap:    12607488 (12312K)     11823880 (11546K)       788320 (769K)
 (Static):      528384 (516K)
Stacks:         208952 (204K)
? (progn (time (remove 5000 tstlist)) t)
(REMOVE 5000 TSTLIST) took 69 milliseconds (0.069 seconds) to run.
 80016 bytes of memory allocated.
T
? (progn (time (faster-remove 5000 tstlist)) t)
> Error: Stack overflow.
> While executing: FASTER-REMOVE
> Type Command-. to abort.
See the RestartsU menu item for further choices.
1 >

For shorter lists, but larger than in your example, your function shows a
memory, but no time gain (egc is not used, btw).  The following example
is your own example scaled by a factor of 100, i.e., TSTLIST is set to (1
... 500 1 ... 500):

? (time (dotimes (X 800) (remove X tstlist)))
(DOTIMES (X 800) (REMOVE X TSTLIST)) took 6078 milliseconds (6.078
seconds) to run.
Of that, 191 milliseconds (0.191 seconds) were spent in The Cooperative
Multitasking Experience.
 6400080 bytes of memory allocated.
NIL
? (gc)
NIL
? (time (dotimes (X 800) (faster-remove X tstlist)))
(DOTIMES (X 800) (FASTER-REMOVE X TSTLIST)) took 6280 milliseconds (6.280
seconds) to run.
Of that, 200 milliseconds (0.200 seconds) were spent in The Cooperative
Multitasking Experience.
 2994000 bytes of memory allocated.
NIL

--------------------------------------------------------------
Espen J. Vestre,                          [e-mail]
Universitaet des Saarlandes,
Computerlinguistik, Gebaeude 17.2
Im Stadtwald,                          tel. [phone]
D-6600 SAARBRUECKEN, Germany           fax. [phone]
--------------------------------------------------------------