[plt-scheme] reverse operation - how fast?

From: Jens Axel Søgaard (jensaxel at soegaard.net)
Date: Fri Apr 8 10:35:48 EDT 2005

Hans Oesterholt-Dijkema wrote:

> Dear All,
> Could someone tell me what the performance impact
> is of the 'reverse' primitive in the code beneath:
> *********************************************
> (define (get-element-from-fifo fifo)
>  (let ((elem (car (reverse (car fifo)))))
>    (set-car! fifo (reverse (cdr (reverse (car fifo)))))
>    elem))
> *********************************************

Reverse takes time proportional to the length of the list.
To avoid this work every time an element is to be removed
from the queue, you can keep two lists: one for insertion
and one for removal. When the removal list is empty,
you reverse the insertion list and use that as removal



Jens Axel Søgaard

Posted on the users mailing list.