Sorry. I shouldn't do math at 4am. Ignore the numbers. However, it
is still correct that the byte array will use less space than an array
of bignums.
George
On 1/27/2016 3:54 AM, George Neuner wrote:
i run a custom built hash. i use separate chaining with a vector of
bignums. i am willing to let my chains run up to 5 keys per chain
so i need a vector of 6 million pointers. that's 48 mb for the array.
another 480 mb for the bignums. let's round that sum to .5 gb.
This structure uses a lot more space than necessary. Where did you
get the idea that a bignum is 10 bytes?
Unless something changed recently, Racket uses the GMP library for
multiple precision math. GMP bignums require 2 allocations: a struct
plus an array. Repesenting a full size 128-bit value on a 64-bit
machine takes 40-48 bytes depending on the library's int size, and not
including any allocator overhead.
In the worst case of every key being a bignum, your hash is using 2.6
to 3.1 GB ... not 0.5 GB. Again, not including allocator overhead.
Since you are only comparing the hash entries for equality, you could
save a lot of space [at the expense of complexity] by defining a
{bucket x chain_size x 16} byte array and storing the 16-byte keys
directly.
Even using an auxillary vector for tracking residency in the array,
you'd be down under 1GB for the same 6 million hash entries.
Even so, this seems like a bad approach to me.
--
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.
