As a followup to my last thread regarding my generic collections library, I
have now created a package that uses it to define an entirely new data
structure. I've implemented Clojure's 32-way bitmapped tries to create a
persistent vector implementation. If you're interested in trying it out, it's
available as a package under the name ‘alexis-pvector’.
Since my collections library only supports immutable collections, Racket's
built-in immutable vectors aren't very well-suited to my model. My
implementation of `conj` for Racket vectors is not exactly efficient:
(define (conj vec item)
(vector->immutable-vector
(vector-append vec (vector item))))
With persistent vectors, the majority of conj operations are truly O(1), and a
small portion (about 3%) of them are O(log_32 n), so the performance overhead
should be negligible.
Some initial profiling has proved promising:
(time (void (extend #() (in-range 100000))))
(time (void (extend (pvector) (in-range 100000))))
;; output:
;; cpu time: 41116 real time: 41336 gc time: 6176
;; cpu time: 124 real time: 124 gc time: 3
(define (random-set seq)
(define l (length seq))
(for/fold ([seq seq])
([i (in-range 100000)])
(set-nth seq (random l) (random))))
(time (void (random-set (vector->immutable-vector (make-vector 10000)))))
(time (void (random-set (extend (pvector) (take 10000 (in-naturals))))))
;; output:
;; cpu time: 3674 real time: 3677 gc time: 552
;; cpu time: 194 real time: 193 gc time: 8
Admittedly, these tests (especially the first one) are fairly biased towards
persistent vectors, but even so, they cover two of the most common vector
operations, so I think they're still relevant.
Some rudimentary documentation is available, but the vast majority of the
vectors' interface is through the methods provided by alexis/collection. Try
them out! Let me know if you find any bugs or if you have any performance
considerations.
As a final note, there are still some improvements that definitely need to be
made. Currently vectors print as #<pvector>, which is not very helpful, so
implementing a custom write procedure is high on my todo list. Also, this is
not an implementation of RRB vectors, which are an improved version of this
implementation but are more complex, so I have yet to look into how I could
adapt this to use that algorithm.
Let me know what you think!
Alexis
--
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.
