[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: One trivial querstion about datatype
From: |
Alex Shinn |
Subject: |
Re: One trivial querstion about datatype |
Date: |
21 Dec 2001 10:53:44 +0900 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) Emacs/21.1 |
>>>>> "Dmitry" == Dmitry Morozhnikov <address@hidden> writes:
Dmitry> I need datatype witch can store some unknown amount of
Dmitry> elements. Elements must be referensed by index. Time for
Dmitry> referencing is critical parameter.
Dmitry> In C i can use array of pointers for that purpose, start
Dmitry> from some size and realloc() it on need. In scheme vectors
Dmitry> are applicable for that with one small exception -- they
Dmitry> can`t change size.
You can use this approach in Scheme as well:
(define (grow-vector vec size)
(let ((len (vector-length vec)))
(if (<= size len)
vec ; or error/shrink on <
(let ((new (make-vector size)))
(vector-move-left! vec 0 len new 0)
new))))
But this isn't so useful... you would want a more opaque data type (in C
also) so that references to the sequence see the same changes. You
could create a goops object for this, or any other level of indirection:
(define (make-sequence size) (cons 'sequence (make-vector size)))
(define (sequence? obj) (and (pair? obj) (eq? (car obj) 'sequence)))
(define (grow-sequence seq size)
(let* ((vec (cdr seq))
(len (vector-length vec)))
(if (< len size)
(let ((new (make-vector size)))
(vector-move-left! vec 0 len new 0)
(set-cdr! seq new)))
seq))
(define (sequence-ref seq i)
(let* ((vec (cdr seq))
(len (vector-length vec)))
(if (< len i)
(grow-sequence seq (* 2 i))) ; or return #f
(vector-ref (cdr seq) i)))
(define (sequence-set! seq i v)
(let* ((vec (cdr seq))
(len (vector-length vec)))
(if (< len i)
(grow-sequence seq (* 2 i)))
(vector-set! (cdr seq) i v)))
This is probably the closest thing to a "sequence," in that it will give
almost vector speed access and will perform well if you build the
sequence in order.
If access speed is the most important thing, and you're building up
arbitrary elements of a potentially large sequence, you might consider
a hash.
If you want something more like the list/array data types in scripting
languages such as Python/Perl, where you want to quickly push elements
onto either end of the data structure (treating them both as vectors and
lists) then you might try a list of vectors rather than the single
vector above. Appending (pushing, etc.) applies the above approach to
the last element of the list, and cons (unshift in Perl speak) then
means cons'ing a new single element vector onto the front of the list
(probably with consolidation routines).
--
Alex