Re: arrays vs. vectors
- From: Pascal Bourguignon <spam@xxxxxxxxxxxxxxxx>
- Date: Fri, 27 Jan 2006 22:12:49 +0100
"H." <hbe123@xxxxxxxxx> writes:
> from brian harvey 61A lecture notes:
> "The list suffers from one important weakness. Finding the nth element
> of a list takes time theta n because you have to call cdr n-1 times.
> Scheme, like most programming languages, also provides a primitive
> aggregation mechanism without this weakness. In Scheme it's called the
> vector; in many other languages it's called an array, but it's the same
> idea. Finding the nth element of a vector takes theta 1 time."
>
> Actually I only need one sentence of this, but the one sentence
> deserves context::
> "In Scheme it's called the vector; in many other languages it's called
> the array"
>
> When a language exists that has an array type and a vector type (e.g.
> Java), how do the array and vector types in those languages correspond
> to the vector type in Scheme? Did Scheme pack everything into one type
> for which other languages need two?
Vectors are 1-dimensional arrays.
Matrices are 2-dimensional arrays.
Most languages tend to be more practical than Scheme: you can define
arrays of any number of dimension.
eg. in Common Lisp: (make-array '(3 3 3)) makes a tensor.
In Scheme, since the purpose is to teach you how to implement stuff,
it only defines the minimalissimum make-vector, and if you want more
dimensions, you do it yourself.
So, you must come with the correspondance yourself.
One way would be to agregate vectors of vectors:
(define (make-array dimensions element)
(cond
((number? dimensions) (make-vector dimensions element))
((null? (cdr dimensions)) (make-array (car dimensions) element))
(else (let ((slice (make-vector (car dimensions) '())))
(let fill ((i (- (car dimensions) 1)))
(if (<= 0 i)
(begin
(vector-set! slice i (make-array (cdr dimensions) element))
(fill (- i 1)))))
slice))))
(make-array '(2 3 4) 1.0)
-->
#(#(#(1.0 1.0 1.0 1.0) #(1.0 1.0 1.0 1.0) #(1.0 1.0 1.0 1.0))
#(#(1.0 1.0 1.0 1.0) #(1.0 1.0 1.0 1.0) #(1.0 1.0 1.0 1.0)))
Another would be to compute the indices yourself:
(define first car)
(define second cadr)
(define third caddr)
(define (last list)
(cond ((null? list) List)
((null? (cdr list)) list)
(else (last (cdr list)))))
(define (butlast list)
(letrec ((bl (lambda (list res)
(if (null? (cdr list))
(reverse res)
(bl (cdr list) (cons (car list) res))))))
(if (null? list)
list
(bl list '()))))
(define (gen-indices-to-rowindex dimensions)
(letrec ((make-argument (lambda (index)
(string->symbol (string-append "A" (number->string index)))))
(gen-args (lambda (index dim res)
(if (null? dim)
res
(gen-args (+ 1 index)
(cdr dim)
(cons (cons (make-argument index) (car dim)) res)))))
(gen-expr (lambda (args)
(if (null? (cdr args))
(caar args)
(list '+ (caar args) (list '* (cdar args) (gen-expr (cdr args))))))))
(let ((args (gen-args 0 dimensions '())))
(eval (list 'lambda (reverse (map car args)) (gen-expr args))
(scheme-report-environment 5)))))
(define (make-array dimensions element)
(list 'array
(gen-indices-to-rowindex dimensions)
(make-vector (apply * dimensions) element)))
(define (array-ref array . indexes)
(and (eq? 'array (first array))
(vector-ref (third array) (apply (second array) indexes))))
(define (array-set! array . indexes-and-value)
(let ((indexes (butlast indexes-and-value))
(value (car (last indexes-and-value))))
(and (eq? 'array (first array))
(vector-set! (third array) (apply (second array) indexes) value))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
This is a signature virus. Add me to your signature and help me to live.
.
- Follow-Ups:
- Re: arrays vs. vectors
- From: H.
- Re: arrays vs. vectors
- References:
- arrays vs. vectors
- From: H.
- arrays vs. vectors
- Prev by Date: Re: arrays vs. vectors
- Next by Date: Re: no char->string / string-append
- Previous by thread: Re: arrays vs. vectors
- Next by thread: Re: arrays vs. vectors
- Index(es):
Relevant Pages
|
