1

Lets assume i have a function that takes 32bit integer in, and returns random 32bit integer out.

Now, i want to see how many and which duplicate values this function will return on all possible input values from 0 to 2^32-1. I could make this easy if i had more than 4gigs free ram, but i dont have more than 1gig ram.

I tried to map the calculated values on disk, using 4gig file where one byte represented how many duplicates it had got, but i noticed the approximated finishing time will be 25 days in the future with my HDD speeds! (i had to use SSD in fear of breaking my HDD...)

So, now the next step is to calculate this all in RAM and not use disk at all, but i ran at wall when thinking how to solve this elegantly. The only method i could think of was to loop (2^32)*(2^32) times the function, but this is obviously even slower than my HDD method.

What i need now is some nasty ideas to speed this up!

Edit: The function isnt really a random function, but similar to a random function, but the fact is you dont need to know anything about the function, its not the problem here. I want to see all the duplicates by my bare eyes, not just some mathematical guessing how many there could be. Why im doing this? Out of curiosity :)

Rookie
  • 119
  • 4
  • When you say duplicate, do you mean that you are looking for cases where `in(5) => 5`, or cases where `in(5) => 10 && in(6) => 10`? – aroth May 17 '11 at 00:57
  • 1
    By 'random', I presume you mean 'deterministic'. – Nick Johnson May 17 '11 at 04:15
  • @aroth, by duplicate i mean that the return value of two (or more) given numbers will return the same "random" number. @Nick, i guess i mean 'deterministic' (its not really a random function for its purpose, but output is very close to random values) – Rookie May 17 '11 at 10:54

2 Answers2

6

To check for 2^32 possible duplicates you only need 4 gigabits which is 512MB, since you need only a single bit per value. The first hit of a zero bit sets it to 1 and on every hit of a 1 bit you know you have a duplicate and can print it out or do whatever you want to do with it.

I.e. you can do something like this: 

int value = nextValue(...);
static int bits[] = new int[ 0x08000000 ]();

unsigned int idx = value >> 5, bit = 1 << ( value & 31 );
if( bits[ idx ] & bit )
   // duplicate
else
    bits[ idx ] |= bit;

in response to your comments

Yes, putting the duplicates into a map is a good idea if there are not too many and not to many different duplicates. The worst case here is 2^31 entries if every 2nd value appears exactly twice. If the map becomes too large to be held in in memory at once you can partition it, i.e. by only allowing values in the certain range, i.e. a quarter of the entire number space. This would make the map have only 1/4th of the size of the entire map if the duplicates are distributed rather equally. You would of course need to run the program 4 times for each quarter to find all duplicates.

To find also the 1st duplicate you can run it in two passes: In the first pass you use the bitmap to find the duplicates and put them into the map. In the 2nd pass you skip the bitmap and add the values into the map if there is already a entry in the map and the value is not yet there.

No, there is no good reason for a int over a unsigned int array. you can as well use unsigned int which would actually be more appropriate here.

x4u
  • 13,877
  • 6
  • 48
  • 58
  • Yes - and if the OP doesn't have as much as 2^32 bits there is an obvious time-memory tradeoff better than the one suggested above. If you have space for 1/K of the bitmap, loop K times through the 2^32 possibility, each time throwing away the output values that do not live in the current 1 of K regions. 25 days sounds a long time - is it seeking all over the place. One way to get an optimised disk based solution would be to write out 2^32 values sequentially and then use an existing optimised on disk sort routine, then read sequentially. – mcdowella May 17 '11 at 04:26
  • hmm... bitmap is a good idea, but what if there are 3 hits on same value? maybe impossible, but i wanted to know it too... well, i cant get everything, i guess, ill try this method and see how many duplicates it gets. 512megs is perfect, since its what i can use max! – Rookie May 17 '11 at 10:57
  • @mcdowella, yeah i thought that idea of making it into chunks, but thats where i ran into wall, i dont really know how it would work any faster than looping all (2^32)*(2^32). while struggling on this, i learnt to seek/read/write the values in sorted order, and then seeking, made it 50 times faster (and hella lot silent), but still not fast enough :/ – Rookie May 17 '11 at 10:59
  • Actually, this bitmap thing is just perfect here: i decided to store the found duplicates into a std::map (since i bet there wont be many of them), and if i ran into the same number many times, i just increment the std::map value, and here i get the full list of duplicates of any amount, plus i can easily track which input values it had. – Rookie May 17 '11 at 11:14
  • OH wait a second, unfortunately i will lose the first record from the other part of the duplicate, so i will only know which was the SECOND (or third etc) duplicate input value. I want to solve this, ideas? – Rookie May 17 '11 at 11:40
  • @x4u, is there some good reason you are using `int` array instead of `unsigned int` array? – Rookie May 17 '11 at 13:31
  • oh and what does those brackets do in the end of `new` () ? – Rookie May 17 '11 at 13:42
  • see my update above for answers... The `()` after the `new` is supposed to initialize the entire array with zeros (C++ 03). See http://stackoverflow.com/questions/2204176/how-to-initialise-memory-with-new-operator-in-c – x4u May 17 '11 at 13:49
  • thanks! good idea with two pass, i will try that. i think there is a bug in your code: `val >> 3` shouldnt that be `val >> 5` since its 32bit chunks ? (also the variable name should be `value` instead) – Rookie May 17 '11 at 14:13
  • Yes you are right, I corrected it! I had it with a char[] at first and made it a int[] later but forgot to change the 3 into a 5. – x4u May 17 '11 at 14:20
0

The unaskable question: Why?. what are you trying to achieve?

Is this some kind of Monte-Carlo experiment?

If not, just look up the implementation algorithn of your (P)RNG and it will tell you exactly what the distribution of values is going to be.

Have a look at Boost.Random for more choices than you can fathom, and it will have e.g. uniform_int<> and variate generators that can limit your output range while still having well-defined guarantees on distribution of values across the output domain

sehe
  • 374,641
  • 47
  • 450
  • 633
  • why: i am just curious how many "collisions" there will be from this function. i dont know what Monte-Carlo is. the point isnt about knowing the distribution, but to see how many duplicates it will return. also the function isnt really a random function, but the output is very similar to a random function. – Rookie May 17 '11 at 11:03
  • @Rookie: have fun then. "very similar to a random function" is a interesting notion :) – sehe May 17 '11 at 11:33