On Mon, May 14, 2012 at 8:16 PM, Jay McCarthy <jay.mccar...@gmail.com> wrote:
> They could be identical, but they are different because one set is
> about lists and the other is about pairs. The fact that pairs may be
> used to implement lists is immaterial.
>
> You should really never use the c[ad]*r functions unless you are
> specifically dealing with pairs.
So, what should one use on proper lists?
- c[ad]*r no;
- first and rest appear to be O(n):
#lang racket
(define (test len times)
(let ((ll (make-list len 1)))
(time (for/sum ((i (in-range times)))
(+ (first ll)
(second ll))))))
> (test (expt 10 6) 1000)
cpu time: 15 real time: 16 gc time: 0
2000
> (test (expt 10 7) 1000)
cpu time: 109 real time: 109 gc time: 0
2000
Why this check is made only for first, rest, etc, and not for all the
functions that take a list?
For example, (list-ref list 1) appears to be O(1) in the length of list.
?
P.
____________________
Racket Users list:
http://lists.racket-lang.org/users
