Here's the fixed one:
uint[] randomSample(uint N, uint M) {
uint[] result = new uint[N];
struct hashPair {
uint key;
uint index;
}
size_t tableSize = N*4;
if (tableSize > M)
tableSize = M;
hashPair[] table = new hashPair[tableSize];
for (uint i = 0; i < N; ++i) {
uint v = (rndGen.front % (M-i))+i;
uint newv = v, newi = i;
rndGen.popFront();
uint ihash = i%tableSize;
while (table[ihash].index) {
if (table[ihash].key == i) {
newi = table[ihash].index-1;
break;
}
}
uint vhash = v%tableSize;
while (table[vhash].index) {
if (table[vhash].key == v) {
newv = table[vhash].index-1;
table[vhash].index = newi+1;
goto done;
}
vhash = (vhash+1)%tableSize;
}
table[vhash].key = v;
table[vhash].index = newi+1;
done:
result[i] = newv;
}
return result;
}
Still a few places to optimise, and I think the compiler
optimisation should be able to give a decent speed up as well.
Would be interested to see how it compares in your benchmark!
