randomShuffle

[Diggory]

On Monday, 3 June 2013 at 21:24:50 UTC, Joseph Rushton Wakeling 
wrote:
> On 06/03/2013 08:28 PM, Diggory wrote:
>> I'd guess that the heavy use of floating point arithmetic to 
>> calculate the step
>> sizes means that algorithm has a fairly large constant 
>> overhead even though the
>> complexity is smaller.
>
> Yes, I agree.  There might be some optimizations that could be 
> done there.

Well I've come up with this new algorithm:


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;
		rndGen.popFront();

		uint vhash = v%tableSize;

		while (table[vhash].index) {
			if (table[vhash].key == v) {
				newv = table[vhash].index-1;
				table[vhash].index = i+1;
				goto done;
			}

			vhash = (vhash+1)%tableSize;
		}

		table[vhash].key = v;
		table[vhash].index = i+1;

done:
		result[i] = newv;
	}

	return result;
}


It's O(N) rather than O(N²). Conceptually it works by randomly 
shuffling the first N items in an array of size M which takes 
O(N) time but requires an array of size O(M), so to avoid this it 
uses a simple hash table to store just the items which have been 
swapped. Since only O(N) items are being shuffled there can only 
be O(N) swaps and so the hash table can be O(N) in size while 
still offering constant time look-up.