Re: Probabilistic Data Structure

From: Amey Samant (ameyas7_at_yahoo.com)
Date: 10/04/03 

Date: 3 Oct 2003 22:24:08 -0700

hi Steve
its great to discuss & clear things up ....

> There will always be restriction of psuedo-random numbers never trully
> being random (unless you use some exotic external generator) when using
> computers. This method will guarantee an even distribution over the
> number of iterations required, you just need to ensure you shuffle
> sufficiently to give the 'appearance' of being genuinely random.

i tried this code

import java.util.*;
class TestRandom
{
        public static void main(String[] args)
        {
                Random ran =new Random(10);
                for(int i=0;i<10;i++)
                        System.out.println(i+" - "+ran.nextInt(10));
        }
}

this should generate 10 random numbers. i goes from 0 - 9 & random
number bounds are 0 - 9 as well .

& the results were as follows
OUTPUT :

0 - 3
1 - 0
2 - 3
3 - 0
4 - 6
5 - 6
6 - 7
7 - 8
8 - 1
9 - 4

is this evenly distributed ?
how would you shuffle such that you always get HIT or at least try to
maximize HITs ?

> No, I don't think the complexity changes at all. The actual data
> retrieval would be very fast, but you would pay a time cost when
> shuffling depending on the distribution, number of elements required and
> iterations used. Then again, shuffling data around is what computers are
> all about ;)

swapping has always been an expensive task especiaaly when it comes
inside nested loop.
here is a joke (my own creation) "swapping = three variables , three
instructions to swap two values " ;)

> I think it all boils down to the exact requirements and constraints. For
> instance, the original poster's example would only require 4 elements.
> You could even factor this up to 40000 elements to defer the shuffling,
> depending on the frequency of calls, memory available, etc.

no, i agree that requirements play role but what when number of values
is known only at runtime?
even if you know that there are 4 elements today, do you assume that
there will not be more than 100 elements in your next version/upgrade
;) ?
this way your entire logic would change with change in quantity which
may not be desirable.
when the no. of elements are FIXED then it is ok to choose by this
way.

regards
amey

Relevant Pages

  • Re: Probabilistic Data Structure
    ... > first case then again in your answer you are talking about shuffling ... This method will guarantee an even distribution over the ... but you would pay a time cost when ...
    (comp.lang.java)
  • Checking fairness of a shuffling algorithm numerically
    ... Suppose you have a shuffling algorithm on n cards. ... test whether k shuffles randomizes the deck sufficiently. ... distribution and actual distribution is less than epsilon. ...
    (sci.math)
  • Re: Probabilistic Data Structure
    ... it does rely on the random number generator producing an even spread. ... > If you need guarantee an even distribution then what about shuffling the ...
    (comp.lang.java)