("Distinctify" may be semantically better, but doesn't sound right)
Here's a challenge: Given a list in L1, output in L2 the list with all distinct elements, whose elements are in order of their first occurrence in L1. For example, {3,1,4,1,5,9,2,6,5,3,5} becomes {3,1,4,5,9,2,6}. Do this as fast as possible. I'll be measuring any programs I write on 2.55MP.
L1 will have exactly 256 elements, all of which are integers in [1,10^6]. The distribution of L1 will be such that there are about 128 total repetitions. The generation algorithm for L1 is the following:
* Generate one random number in [1,10^6]
* Repeat the following 255 times:
* With probability 1/2, generate a number in [1,10^6] different from all numbers already in the list.
* Otherwise, pick a random number from the unique numbers in the list so far. That is, if the list so far is {6,6,6,4}, a 4 is as likely to be picked as a 6 for the next element.
* Append that number to the list.
* Finally, shuffle the list.
You will not need to generate L1, only uniquify it placing the result in L2. Other average numbers of duplicates (or an in-place uniquify algorithm) may also be interesting, but let's try this one first.
Here's a challenge: Given a list in L1, output in L2 the list with all distinct elements, whose elements are in order of their first occurrence in L1. For example, {3,1,4,1,5,9,2,6,5,3,5} becomes {3,1,4,5,9,2,6}. Do this as fast as possible. I'll be measuring any programs I write on 2.55MP.
L1 will have exactly 256 elements, all of which are integers in [1,10^6]. The distribution of L1 will be such that there are about 128 total repetitions. The generation algorithm for L1 is the following:
* Generate one random number in [1,10^6]
* Repeat the following 255 times:
* With probability 1/2, generate a number in [1,10^6] different from all numbers already in the list.
* Otherwise, pick a random number from the unique numbers in the list so far. That is, if the list so far is {6,6,6,4}, a 4 is as likely to be picked as a 6 for the next element.
* Append that number to the list.
* Finally, shuffle the list.
You will not need to generate L1, only uniquify it placing the result in L2. Other average numbers of duplicates (or an in-place uniquify algorithm) may also be interesting, but let's try this one first.
