While in terms of O-notation, all linear algorithms are equivalent, the actual
time to run a linear algorithm can significantly depend on the actual data
structure. In the program below, I calculate the sum of the elements of a
vector or list in three ways, all of them linear algorithms.
* calculating the sum of the elements in a list (do-time sum1 10) takes 296
milliseconds on my machine
* calculating the sum of the elements in the vector, (do-time sum2 10) takes
374 milliseconds (slower than the list version!)
* calculating the sum of the elements in the vector by explicitly referencing
elements, (do-time sum3 10) takes 62 milliseconds.
I guess my example shows two things:
* the generator for vectors appears to have a performance problem (1.25 times
slower)
* it is 4.7 times faster to iterate over vectors than it is to do it over lists.
Best Regards,
Alex.
#lang racket
(define nitems 1000000)
(define as-list (for/list ([x (in-range nitems)]) (random nitems)))
(define as-vector (list->vector as-list)) ; same data as in the list
(define (sum1)
(for/fold ((sum 0))
((x as-list))
(+ sum x)))
(define (sum2)
(for/fold ((sum 0))
((x as-vector))
(+ sum x)))
(define (sum3)
(for/fold ((sum 0))
((x (in-range (vector-length as-vector))))
(+ sum (vector-ref as-vector x))))
(define (do-time fn (iterations 1))
(collect-garbage 'major)
(define start (current-inexact-milliseconds))
(for ((n (in-range iterations)))
(fn))
(define end (current-inexact-milliseconds))
(- end start))
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
