guile-user
[Top][All Lists]
Advanced

[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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]