Re: remove

[espen@coli.uni-sb.de (Espen J. Vestre)]

In article <HALTRAET.92Nov20091121@monsun.si.no> Hallvard Tr{tteberg,
haltraet@monsun.si.no 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,                          espen@coli.uni-sb.de
Universitaet des Saarlandes,        
Computerlinguistik, Gebaeude 17.2 
Im Stadtwald,                          tel. +49 (681) 302 4501
D-6600 SAARBRUECKEN, Germany           fax. +49 (681) 302 4351
--------------------------------------------------------------