I'm implementing Charikar's fast search on a locality sensitive hash and I'm looking for a fast method of permuting bits (the kind of thing that can be done in one operation in MMIX) in C#.
The requirements are:
- Always less than 64 bits, so representation can be a long integer
- Randomly generate a permutation (this can be slow as it's only done once). I'll probably use a Knuth shuffle.
- Use the generated permutation many times, so this needs to be fast
I know Knuth goes into this in detail but I was wondering if there was any .NET/C# specific solutio开发者_如何学Cn.
EDIT: I'm using .NET version 3.5.
Since C# doesn't provide any bit-manipulation instructions that Knuth didn't have in C, no, there's no .NET/C#-specific solution.
At the same time, .NET does offer dynamic compilation which will help you repeatedly perform the shuffle efficiently.
What version of .NET? The easiest approach will probably be to use Knuth's algorithm and encode the resulting operations in an Expression<Func<ulong, ulong>>
, then compile the result as a Func<long, long>
delegate.
精彩评论