Irreal

The most common way of doing this is shown in the first code block. The cntr definition just provides a stream of integers—a new one each time it’s called. The E1 function does the actual work of assembling the list and the let at the end just calls E1 and calculates the time it took to do its work. All this should be very familiar to even beginning Scheme programmers.

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E1
  (lambda (n)
    (let loop ((k n) (lst '()))
      (if (zero? k)
          (reverse lst)
          (loop (1- k) (cons (cntr) lst))))))
(let ((start (get-internal-run-time)))
  (E1 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

The next code block is almost the same as the first except that it uses reverse! instead of reverse to reverse the list. Theoretically, reverse! should be faster because it reuses the cons cells from the first list rather than making a separate list from scratch.

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E2
  (lambda (n)
    (let loop ((k n) (lst '()))
      (if (zero? k)
          (reverse! lst)
          (loop (1- k) (cons (cntr) lst))))))
(let ((start (get-internal-run-time)))
  (E2 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

In some sense this is the most intuitive, if naive, method if you are not a Lisp or Scheme programmer. The problem is that append must search down the list each time to find the list’s end and is therefore very inefficient. No serious Lisp or Scheme programmer would ever do this.

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E3
  (lambda (n)
    (let loop ((k n) (lst '()))
      (if (zero? k)
          lst
          (loop (1- k) (append  lst (list (cntr))))))))
(let ((start (get-internal-run-time)))
  (E3 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

This is certainly the fastest method and the one that, say, C programmers would use. Its problem is that you have to know the largest number of items that you can get so that you can preallocate the vector. Common Lisp has a way of extending vectors and the Lisp Idioms article has an experiment for that method but Scheme doesn’t have resizable vectors so we don’t have that case.

(define cntr ((lambda () (let ((k 0)) (lambda () (set! k (1+ k)) k)))))
(define E4
  (lambda (n)
    (let ((vec (make-vector n)))
      (let loop ((k 0))
        (if (= k n)
            vec
            (begin
              (vector-set! vec k (cntr))
              (loop (1+ k))))))))
(let ((start (get-internal-run-time)))
  (E4 n)
  (/ (- (get-internal-run-time) start) internal-time-units-per-second))

We start with a table like this:

|       n | Reverse | Reverse! | Append   | Vector |
|---------+---------+----------+----------+--------|
|       1 |         |          |          |        |
|       2 |         |          |          |        |
|    1024 |         |          |          |        |
|    4096 |         |          |          |        |
|   16384 |         |          |          |        |
|  262144 |         |          | Too Long |        |
| 1048576 |         |          | Too Long |        |

The code blocks have the same names as in the header. For example, the first code block has a

#+SRCNAME Reverse(n)

just above it. The last two rows of the Append column are set to “Too Long” because the Append method takes too long to run for lists of those sizes. All the other cells in columns 2–5 are empty.

Next, we set the code for each of the empty cells to ‘(sbe @1 (n $1)). This is easily done with the table editor and results in the TBLFM line

#+TBLFM: $2='(sbe @1 (n $1))::$3='(sbe @1 (n $1))::$5='(sbe @1 (n $1))::@2$4..@7$4='(sbe @1 (n $1))

sbe is a macro that calls the code block with the name of its first argument and passes the code block the rest of its arguments. The @1 means row one of the current column and thus refers to the name of the code block from the table header. The $1 in the second argument means column 1 of the current row and thus refers to the n-value for this cell.

Now all we need do is put the point anywhere in the table and type C-u C-c C-c and the table will be filled in with the run times.

get-internal-run-time returns number of 100 Hz ticks used by the Guile interpreter (thus internal-time-units-per-second = 100). As expected, the Vector method is fastest but not by as much as we might expect. The other interesting result is that except for really long lists, reverse! does not outperform reverse to any significant extent. The Append method, of course, is out of the running.

This post is a simple example of Reproducible Research because everything needed to reproduce the post is contained in a single the Org-mode file. If this were a serious research paper, any scientist could request a copy of the file and run the experiments for his or herself.

Update: Corrected the definition of get-internal-run-time.