Home > Archive > Scheme > January 2006 > arrays vs. vectors
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
arrays vs. vectors
|
|
|
| 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?
| |
| Hans Oesterholt 2006-01-27, 7:03 pm |
| I'm not sure about the vector/array types in Java.
But in scheme vectors elements can contain any (scheme) type.
However, vectors are fixed length.
Array implementations in scheme are usually "variable length vectors".
--Hans Oesterholt-Dijkema
>
> 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?
>
| |
| Pascal Bourguignon 2006-01-27, 7:03 pm |
| "H." <hbe123@gmail.com> 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.
| |
| Brian Harvey 2006-01-27, 7:03 pm |
| "H." <hbe123@gmail.com> writes:
>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?
A Java array is like a Scheme vector.
A Java vector is an attempt to have one's cake and eat it too. It's an
array that you add elements to, one by one, like CONS, and when you fill
it up, it automatically replaces itself with a bigger one. So lookup
is Theta(1), and insert is also Theta(1) but every so often there's a
Theta(N) delay as it copies itself.
| |
| Kon Lovett 2006-01-28, 3:57 am |
| In article <1138391765.209714.214890@z14g2000cwz.googlegroups.com>,
"H." <hbe123@gmail.com> wrote:
> 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?
See
http://srfi.schemers.org/srfi-4/srfi-4.html
http://srfi.schemers.org/srfi-43/srfi-43.html
http://srfi.schemers.org/srfi-47/srfi-47.html
http://srfi.schemers.org/srfi-63/srfi-63.html
Many Schemes have ports of these. R5RS vectors (& lists) are pitiful,
without much in the way of mutators/etc, and no >1 dim arrays (vectors
being 1 dim, as others stated).
I have only used srfi-4/43 w/ Chicken. It does have a srfi-47 (>1 dim
arrays) but I have no experience. Srfi-63 is not available, currently,
w/ Chicken.
| |
| Lauri Alanko 2006-01-28, 3:57 am |
| In article <dreer7$kqg$1@abbenay.CS.Berkeley.EDU>,
Brian Harvey <bh@cs.berkeley.edu> wrote:
> A Java vector is an attempt to have one's cake and eat it too. It's an
> array that you add elements to, one by one, like CONS, and when you fill
> it up, it automatically replaces itself with a bigger one. So lookup
> is Theta(1), and insert is also Theta(1) but every so often there's a
> Theta(N) delay as it copies itself.
Which is of course amortized to Theta(1), so it's not really relevant
unless you're doing real-time applications.
Just had to add this since you made it sound like there was an
efficiency problem. A dynamic array is a perfectly useful imperative
data structure.
Lauri
| |
|
| > 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.
Let me make sure I understand this correctly. If I want to implement
something in Scheme based on nested for loops with i,j notation, I have
to go though all of what you did above?
| |
|
|
| Brian Harvey 2006-01-28, 7:05 pm |
| Lauri Alanko <la@iki.fi> writes:
>Which is of course amortized to Theta(1), so it's not really relevant
>unless you're doing real-time applications.
Oh, sure, I didn't mean to imply otherwise -- although, since we're quibbling,
there is an optional mode, for people more worried about space than about
time, in which each copying step adds a constant number of cells, and if you
choose that, then even the amortized time is Theta(n), but with a small
constant factor.
| |
| Vesa Karvonen 2006-01-29, 7:00 pm |
| Brian Harvey <bh@abbenay.cs.berkeley.edu> wrote:
> Lauri Alanko <la@iki.fi> writes:
[color=darkred]
> Oh, sure, I didn't mean to imply otherwise -- although, since we're quibbling,
> there is an optional mode, for people more worried about space than about
> time, in which each copying step adds a constant number of cells, and if you
> choose that, then even the amortized time is Theta(n), but with a small
> constant factor.
Speaking of space and dynamically growing arrays, one caveat with most
implementations, that I have seen, is that they never shrink. This
can become an issue if/when you want to build more complex dynamic
data structures (e.g. spatial index for accelerating queries in a 3D
game, where each node has a dynamically growing array of objects). It
is quite possible, that, over time (as objects move from node to
node), space usage will grow significantly higher than what the total
number of objects might suggest. There is fairly simple way to fix
this (to make an array also shrink dynamically) while retaining the
same amortized bounds (hint: it is a nice data structure design
exercise), but I don't recall seeing (m)any libraries offering such a
dynamically growing *and* shrinking array.
-Vesa Karvonen
| |
| Marcin 'Qrczak' Kowalczyk 2006-01-29, 7:00 pm |
| Vesa Karvonen <vesa.karvonen@cs.helsinki.fi> writes:
> Speaking of space and dynamically growing arrays, one caveat with most
> implementations, that I have seen, is that they never shrink.
My implementation shrinks them during GC.
--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
| |
| Ray Dillinger 2006-01-30, 7:04 pm |
| Lauri Alanko wrote:
> In article <dreer7$kqg$1@abbenay.CS.Berkeley.EDU>,
> Brian Harvey <bh@cs.berkeley.edu> wrote:
>
>
>
> Which is of course amortized to Theta(1), so it's not really relevant
> unless you're doing real-time applications.
In real-time applications though this idea of "amortized" can
become critical. You want to write the code very carefully
to detect the need to copy long before it becomes critical,
do a strictly limited amount of copying on each call, and
handle indexing into partly-copied vectors before you
guarantee O(1) time. All this is possible; in fact I wrote
a scheme library once that does it. But it's vitally important
when you want to guarantee that your code is both 0(1) and
Theta(1).
Slower in total? Yes. Uses more memory, most of the time?
Definitely. But if your application *really* can't afford
unpredictable delays or delays of durations that depend
on runtime data, then you pay your price and you deliver on
your design requirements.
Bear
|
|
|
|
|