Hi Tim,
Thank you for the extensive and pedagogical answer (as usual).
> Some questions/tips:
> - are you doing this at global scope? Put it in a function. See the
> performance tips section of the manual.
>
No, both snippets are inside a function.
- It looks like you might be storing the result as an Int (0, as in accum
> =>
> 0, is an Int) in one case and a Float64 in the other case. While it
> shouldn't
> make a practical difference in speed, unless there's some reason for that,
> you
> probably want to make sure you're comparing them fairly.
>
My apologies. But as you predicted, changing the declaration to
lhs = Array(BigInt, 2^20)
makes no difference: assignment into the array is 2-3 seconds.
> - Have you profiled?
I must admit that I did not do that.
>
> If you don't actually require BigInts, you definitely shouldn't use
> them---they
> will slow your code a lot.
The variables invg and p are integers with more than 100 digits.
> That said, if you need them and want stuff to be
> fast:
> - it would be best to look into whether it's possible to implement more
> efficient hashing.
>
- even the multiplication of BigInts requires memory allocation. If you're
> desperate for speed, you could consider adding methods to gmp.jl that use
> a
> pre-allocated output.
>
Other students from the course reported that the Python implementation
takes a couple of seconds using the dictionary.
michele
> On Friday, October 17, 2014 08:31:59 PM Michele Zaffalon wrote:
> > Hello,
> >
> > I am using a dict as a look up table for the result of a computation (it
> is
> > for a Coursera class on cryptography if anybody is wondering):
> >
> > accum = BigInt(1)
> > lhs = Dict(accum => 0)
> > for x1 = 1:2^20-1
> > accum = rem(accum * invg, p)
> > lhs[accum] = x1
> > end
> >
> > and this takes about 20 seconds on my computer. On the other hand, for
> > comparison (but not useful for my purpose because I index by the
> variable
> > x1), storing the result in an array of preallocated size is about 2
> > seconds. Here is the code:
> >
> > lhs = Array(Float64, 2^20)
> > for x1 = 1:2^20-1
> > accum = rem(accum * invg, p)
> > lhs[x1] = accum
> > end
> >
> > Declaring
> > lhs = Dict{BigInt, Int64}(accum => 0)
> > does not make any difference.
> >
> > Is there a way of preallocating the dictionary of a given size?
> >
> > Thank you,
> > michele
>
>
