On 03/17/2011 11:25 PM, dsimcha wrote:
On 3/17/2011 6:18 PM, spir wrote:
I'd have much use for both below.
On 03/17/2011 04:33 PM, dsimcha wrote:
1. Rational: A library for handling rational numbers exactly.
Templated on
integer type, can use BigInts for guaranteed accuracy, or fixed-width
integers
for more speed where the denominator and numerator will be small.
Completion
state: Mostly finished. Just need to fix a litte bit rot and submit for
review. (Phobos candidate)
For decimal exactitude, what about plain fixed point (with decimal
factor and binary mantissa)?
I wouldn't mind having this, but I see it as completely orthogonal to rational
numbers and don't have any near-term intentions of implementing it.
Right.
2. RandAA: A hash table implementation with deterministic memory
management,
based on randomized probing. Main advantage over builtin AAs is that
it plays
much nicer with the GC and multithreaded programs. Lookup times are also
expected O(1) no matter how many collisions exist in modulus hash
space, as
long as there are few collisions in full 32- or 64-bit hash space.
Completion
state: Mostly finished. Just needs a little doc improvement, a few
benchmarks and submission for review. (Phobos candidate)
How complicated would it be to add (optional) support for keeping
insertion order (for iteration only)? Thought at a // array with
pointers to the cells holding key/value pairs.
It's a good idea, but IMHO something like this should be templated on the type
of the associative array and work with builtin AAs, etc., too. It should be a
decorator or something:
/**
Wraps any type that conforms to the duck interface of an associative
array to preserve ordering for iteration.
*/
struct OrderedAA(AA) {
alias typeof(AA.init.keys.front) K;
alias typeof(AA.init.values.front) V;
K[] order;
AA aa;
void opIndexAssign(V val, K key) {
if(!(key in aa)) {
order ~= key;
}
aa[key] = val;
}
// opApply, etc.
}
Right too. But the reason I have not implemented it yet is I don't want to keep
a // array of keys, which require AA lookup for each key. Instead, I thought at
an array of pointers to where the (key:value) cells are stored (cell
"buckets"), to avoid AA key lookups. This, I guess, requires tweaking the
implementation of the actual data structure. Reason why I asked you as you are
dfevelopping a new one (so, you may have such a use case in mind before design
is frozen).
I have not yet had a look at the implementation of builtin AAs to see whether
this would be easy. I guess not: it just require catching the very moment where
a new pair is placed into a given bucket corresponding to its hash value. (And
possibly the same thing at re-hash time.)
Denis
--
_________________
vita es estrany
spir.wikidot.com
