Replacing duplicates in a randomly generated array

[Ether]

Originally Posted by Ether

Simple (and very fast) TP7 implementation

Add the following header:

{$APPTYPE CONSOLE}
USES Windows;

... and change "word" to "dword" (4 places), and you've got a 32-bit Delphi console app which will select 100 non-duplicate random values from a pool of one million in less than 0.004 seconds on an 8-year-old desktop PC.

[Zholl]

Originally Posted by Ether

Add the following header:

{$APPTYPE CONSOLE}
USES Windows;

... and change "word" to "dword" (4 places), and you've got a 32-bit Delphi console app which will select 100 non-duplicate random values from a pool of one million in less than 0.004 seconds on an 8-year-old desktop PC.

I'm afraid I don't understand what you're getting at. I can follow your code, but I don't recognize the language, nor do I see the purpose of your header

[Ether]

@Zholl:

The algorithm I posted works very fast for very large sample spaces. It does not require the overhead of removing samples from the array, nor does it require the overhead of shuffling the entire sample space.

The header is to allow 16-bit TP7 code to be compiled by Delphi into a 32-bit app that can run natively under Windows. You can code the algorithm in your language of choice.

[JesseK]

I'll note that I've used Greg McKaskle's last solutions in several simulation and test applications in Java by using something similar to this:

LinkedList<Object> someList = getList();
Collections.rotate(someList, (int)(Math.random()*(someList.size() - 1)));
Object randomObject = someList.remove();

• Rotating is usually much faster than shuffling
• Removing the element from the queue ensures lack of duplicates

If you want a good lesson in C, you could try implementing a basic generic rotate function and a basic generic LinkedList object. This isn't the most efficient way in Java since the Collections class doesn't know about the Queue implementation of the LinkedList (thus it could save time by manipulating indices rather than doing a rotation), but implementing your own solution would give you that flexibility.

[EricVanWyk]

You may use an obscure programming language when it isn't mentioned for the first 6 pages of google results...

[Ether]

I'll just call it pseudo-code from now on :-)

I just re-ran it with a larger sample space.

On an 8-year-old desktop PC running XP Pro, it took a little over 1 millisecond to select 10 thousand non-dup random samples from a 100 million sample space (neglecting the time required to populate the sample space).

[ebarker]

A note about random number generation. My understanding.....

Back in the day, over 15 or 20 years ago most 'random' numbers were software algorithms that were not that random. If you knew the algorithm, seeding and such you could predict the next 'random' number.

People that really needed random numbers built external circuits that essentially measured the kTb voltage across a resistor. Basically naturally occurring resistor noise.

Then about 15 years ago Intel basically embedded this circuit into the Pentium processor. Starting with a particular revision processor, you could read a register in the processor that would give you a random number, that was based on thermal noise, not a mathematical pseudorandom generator.

So now I'm curious. Does anyone know how to get to this function from Window or linux ?

edit: more on the topic is here http://http://en.wikipedia.org/wiki/...mber_generator

[Ether]

...