Re: [ljc] A little Friday morning challenge for the group...

From: user 7.
Sent on: Monday, January 28, 2013 2:24 PM
From my tests, it still seems Michael's version is the winner. 

Yours is fast Bruno but there seems to be an unequal distribution, the highest and lowest values have approximately half the probability of being selected. 

Both of my methods suffer from issues, in both versions a rounding issue that prefers zero so a negative min will never be selected and zero is twice as likely to be selected. In my most recent attempt using the BigDecimal type is very slow taking about five times the amount of time to come up with the result. 

The other method mentioned simply using nextLong until it is in range can take a very long time for a small range in my tests I had to remove it because it wasn't completing in a reasonable time for smaller ranges.


On Mon, Jan 28, 2013 at 12:43 PM, Bruno Medeiros <[address removed]> wrote:
I think I've found a good solution to the problem. Note though, I was
approaching the problem as an algorithmic puzzle. If I needed to use
this in real code, I would just google the web for some premade
solution, that is certainly the best thing to from a software
development perspective. I wouldn't be spending time trying to roll my
own.
So this is what I got:
http://pastebin.com/n8fTjBzJ

It uses a random generator to generator a coin toss (either one or
zero). It basically looks at the range of numbers to generate, and
uses a coin toss to decide whether to generate a random number in the
lower half, or the upper half, and then continues recursively until
the range is small enough to be just one choice. It runs in
log2(max-min) complexity then, so that's good. Similar to a binary
search. In fact it was when I thought of binary searches that I took
inspiration for this idea (and a similar problem that I read on a book
once).

The only tricky thing is dealing with odd ranges. If a range is odd
(say min=2 max = 6), you can't split it in half neatly. If you just
assign the middle element to the same half you will break the uniform
distribution.
The solution was to make another coin toss to determine whether the
middle element would be included in the half to process or not (giving
it a 50% chance to be included, just like any other numbers).

I tested it a bit, but not extensively, so I don't know if there is
any minor bug or not. But the basic algorithm should work... @_@

On Fri, Jan 25, 2013 at 5:03 PM, Bruno Medeiros
<[address removed]> wrote:
> Interesting problem! I knew when I saw your original post that it must
> be trickier that what it looked at first.
>
> Any code that uses (max - min) where max and min are longs is broken
> because of the issue of long overflow. That could easily be solved
> though.
>
> But the hardest part is indeed what Michael pointed out: that the
> "double values between 0.0 and 1.0 is less than the number of long
> values between Long.MIN_VALUE and  Long.MAX_VALUE."
>
> I thought up of two solutions (both generally work by dividing the
> delta in two parts and calculating the random for of each part) which
> strictly speaking do work according to your requirements , but they
> are not good solutions because although they would generate within the
> correct range:
> * the first one is does not generate a uniform distribution. Values on
> the edges of the (max-min) delta would be more likely to be generated,
> potentially a lot more.
> * The second solution does generate a uniform distribution, but
> requires a potentially quite large number of retries to the random
> function call, having a non-deterministic performance...
>
> I'm still trying to think of something better, which is a problem
> because I have work to do, damn you!!
>


--
Bruno Medeiros




--
Please Note: If you hit "REPLY", your message will be sent to everyone on this mailing list ([address removed])
http://www.meetup.com/Londonjavacommunity/
This message was sent by Bruno Medeiros ([address removed]) from LJC - London Java Community.
To learn more about Bruno Medeiros, visit his/her member profile: http://www.meetup.com/Londonjavacommunity/members/14173275/
Set my mailing list to email me

As they are sent
http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=1

In one daily email
http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=2

Don't send me mailing list messages
http://www.meetup.com/Londonjavacommunity/list_prefs/?pref=0
Meetup, POB 4668 #37895 NY NY USA 10163 | [address removed]


Our Sponsors

  • Our Blog

    Read the latest news from the LJC

  • RecWorks Ltd

    Fixing Tech Recruitment using the Power of Community

  • jClarity

    Java/JVM Performance Analysis Tools & mentoring for Java related matters

  • LJC Aggrity

    Our LJC Aggrity site contains blog posts from our members

  • LJC Book Club

    Our Book club with book reviews from our members

  • Devoxx UK

    Java Community Conference, in collaboration with the LJC 12/13 Jun 14

  • SkillsMatter

    "Host, help organise, promote, film many of our meetings."

  • New Relic

    New Relic makes sense of billions of metrics a day in real time.

  • Hazelcast

    Hazelcast is the leader in operating in-memory computing.

  • Packt Publishing

    A publishing company specializing on specific technologies and solutions

  • Java.Net

    We are an official Java User Group recognised by Oracle's JUG program

  • JRebel

    Free 3 month J-Rebel license.

  • O'Reilly

    40% discount on printed books and 50% on e-books.

People in this
Meetup are also in:

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy