On 09/05/2013 08:42 AM, Konrad Hinsen wrote:
Scott Klarenbach writes:
> Check out some of the functional data structures found here:
>
> http://www.ccs.neu.edu/racket/pubs/sfp10-kth.pdf
>
> VLists may be of particular interest in your case.
That's the stuff in the pfds package, right?
https://pkg.racket-lang.org/info/pfds
Interesting indeed, makes me think of Clojure vectors. And written to
be used as a drop-in replacement for lists. I'll play with that as
well!
The implementation is in Typed Racket as well, so should I expect the
same performance problems as with arrays when I work in plain Racket?
Yes. A first-order data structure gets traversed every time it passes
from untyped to typed code, to ensure its structure conforms to its
type. This makes all operations Omega(n) in untyped code; i.e. an
O(log(n)) operation becomes O(n), and an O(n*log(n)) operation remains
O(n*log(n)).
The best advice I have is to keep performance-critical loops either all
typed or all untyped, unless the only things that cross the contract
boundary are flat first-order datums like flonums, strings and vectors.
(The math library's flonum functions, for example, are plenty fast to
call from untyped code.) Speeding up the contract boundary is an active
area of research, so I expect to have to modify this advice in the future.
Neil ⊥
____________________
Racket Users list:
http://lists.racket-lang.org/users
