3

Nothing too complicated, basically I just want to pick an element from the array as if I were making coin tosses for each index and and choosing the index when I first get a head. Also no heads means I choose the last bin.

I came up with the following and was wondering if there was a better/more efficient way of doing this.

def coin_toss(size)
  random_number = rand(2**size)
  if random_number == 0
    return size-1
  else
    return (0..size-1).detect { |n| random_number[n] == 1 }
  end
end
paarshad
  • 295
  • 2
  • 7
  • 2
    shouldn't be the index (0..index-1)? index size is out of bounds. Also, why do you pass the size of the array and not the array itself (and then return the value a[i] and not i) – tokland May 14 '11 at 20:55
  • Fixed, thanks. Just passed the size because I was timing various methods and actually having an array didn't matter. – paarshad May 15 '11 at 01:52

2 Answers2

7

First guess...pick a random number between 1 and 2**size, find the log base 2 of that, and pick the number that many elements from the end.

Forgive my horrible ruby skillz.

return a[-((Math.log(rand(2**size-1)+1) / Math.log(2)).floor) - 1]

if rand returns 0, the last element should be chosen. 1 or 2, the next to last. 3, 4, 5, or 6, third from the end. Etc. Assuming an even distribution of random numbers, each element has twice as much chance of being picked as the one after it.

Edit: Actually, it seems there's a log2 function, so we don't have to do the log/log(2) thing.

return a[-(Math.log2(rand(2**size - 1)+1).floor) - 1]

You may be able to get rid of those log calls altogether like

return a[-((rand(2**size-1)+1).to_s(2).length)]

But you're creating an extra String. Not sure whether that's better than complicated math. :)

Edit: Actually, if you're going to go the string route, you can get rid of the +1 and -1 altogether. It'd make the probabilities more accurate, as the last two elements should have an equal chance of being chosen. (If the next-to-last value isn't chosen, the last value would always be.)

Edit: We could also turn the ** into a bit shift, which should be a little faster (unless Ruby was smart enough to do that already).

return a[-(rand(1<<size).to_s(2).length)]
cHao
  • 84,970
  • 20
  • 145
  • 172
  • The math is a bit complicated...i'd love to see it simpler. Updated with an additional, simpler (but messier) way. – cHao May 14 '11 at 20:26
  • Very interesting way to do this. I benchmarked it with size = 20 (actually most common value for me) and your method took half the time of mine, but unfortunately half the time it just failed with, "Errno::EDOM: Numerical argument out of domain - log" – paarshad May 14 '11 at 21:57
  • 1
    Kinda odd. The +1 should nudge `rand`'s return value into the domain of the log function. (log(1) is zero; log(0) is either undefined or -infinity, i forget) – cHao May 14 '11 at 22:17
  • ah I missed the + 1 when typing it into irb. Sorry about that. – paarshad May 14 '11 at 23:58
  • to_s(2).length is winning with 70% of the log version's time, nice! – paarshad May 15 '11 at 01:38
  • I'm not even trying to read the mathematics code, but I'm in favor of separating the numeric function from the actual getting of an element. – Andrew Grimm May 15 '11 at 23:42
  • It wouldn't be too hard to separate -- just instead of `a[-...]`, you could return `size - ... `. But the return value would be rather intimately related to `size`, so separating them didn't make too much sense to me. The function wouldn't be but so useful outside of the context of getting an element. – cHao May 16 '11 at 00:00
  • @cHao: I believe there _is_ sense in separating the math part. I guess what you are doing here is getting a random number between 0 and N, just not uniformly distributed (not sure what the distribution would be called though, skipped some classes :), perhaps logarithmic, or Poisson?) – Mladen Jablanović May 16 '11 at 06:10
  • @Mladen: It's definitely some kind of logarithmic selection, considering i'm using logs to figure out which one to grab. Not sure if there's a special name for it, though, as i never went to any classes. :) – cHao May 16 '11 at 08:00
  • fyi: the 1< – paarshad May 17 '11 at 13:27
5

A non-smart, simple way is:

def coin_toss( arr )
  arr.detect{ rand(2) == 0 } || arr.last
end
steenslag
  • 79,051
  • 16
  • 138
  • 171