Topic: Ruby doesn't support "do while" loops?

Hey all,

In javascript, there are  cases where you have a variable called, let's say, old which contains 50 positions in an array. Now you want each position of the array to be unique. But at the same time, you want to generate random numbers for each item of the array:

var old = new array(20)
var new
do {
  new = Math.floor(Math.random()*100) + 1;
}
while (old[new]);

old[new] = true;

Is there a way to do a do while loop like this in Ruby?
Thanks for any suggestions.

Re: Ruby doesn't support "do while" loops?

Hi John,

Try:

begin
  ...
end while ...

Kevin

Re: Ruby doesn't support "do while" loops?

Something like this?

def unique_num
@unique_num ||=
  begin
   old = [75] #The old variable holds 75 indexes of an array.
   new = math.floor(math.random) * 100 + 1 #The new variable yields a random number from 1 to 100.
   begin
    old << new #We append the random number into the array.
   end while old[new] #We loop again if the number already exists, until we get another number in the position.
   old[new] = true #We set it to true since the number is now in the array.
  end

Re: Ruby doesn't support "do while" loops?

Can I just confirm what you are trying to do here? You want an array of (say) 75 unique integers in the range 1-100?

Re: Ruby doesn't support "do while" loops?

this

while old[new]

doesn't test whether the number is already in the array, it will just return the number with that index.  I would do it (ie generate n different random numbers between 1 and a limit) like this


n = 75
limit = 1000
arr = []
while arr.size < n
  x = rand(limit)+1
  arr << x unless arr.include?(x)
end

in irb

>> n = 75
=> 75
>> limit = 1000
=> 1000
>> arr = []
=> []
>> while arr.size < n
>>   x = rand(limit)+1
>>   arr << x unless arr.include?(x)
>> end
=> nil
>> arr.size
=> 75
>> arr.uniq.size
=> 75
>> arr
=> [852, 799, 438, 977, 264, 250, 396, 911, 951, 482, 535, 418, 550, 208, 462, 706, 26, 778, 104, 244, 608, 274, 28, 835, 401, 665, 562, 660, 763, 850, 744, 845, 86, 187, 332, 610, 618, 107, 51, 994, 519, 727, 259, 708, 18, 586, 818, 192, 445, 748, 185, 755, 470, 717, 441, 83, 640, 325, 466, 284, 582, 475, 322, 262, 285, 20, 920, 271, 388, 340, 953, 400, 597, 602, 589]
>> arr.max
=> 994
>> arr.min
=> 18

###########################################
#If i've helped you then please recommend me at Working With Rails:
#http://www.workingwithrails.com/person/ … i-williams

Re: Ruby doesn't support "do while" loops?

The following uses a hash to enforce uniqueness, rather than the Array#include method. It assumes that the random numbers are picked from a pool ten times the size of the requested array, but you could change this as you see fit.

def unique_list(size)
  h = {}
  h[rand(size * 10) + 1] = true while h.length < size
  h.keys
end

p unique_list(75)

It's probably more linear in its response times than Array#include for larger arrays, but I haven't benchmarked it...

Re: Ruby doesn't support "do while" loops?

Thanks for your responses.

Re: Ruby doesn't support "do while" loops?

Specious, you're right, yours p*sses on mine smile  I did a little experiment...

Array approach


def n_random_numbers(n, limit = nil)
  limit ||= n * 10
  arr = []
  while arr.size < n
    x = rand(limit)+1
    arr << x unless arr.include?(x)
  end
  arr
end

n = 128
while n < 1000000
  time = Time.now
  arr = n_random_numbers(n)
  puts "#{n} element array completed in #{Time.now - time} seconds"
  n *= 2
end

128 element array completed in 0.001347 seconds
256 element array completed in 0.012936 seconds
512 element array completed in 0.05813 seconds
1024 element array completed in 0.08663 seconds
2048 element array completed in 0.291903 seconds
4096 element array completed in 1.136999 seconds
8192 element array completed in 4.511054 seconds
16384 element array completed in 19.129743 seconds
32768 element array completed in 75.833733 seconds


...killed it at this point.

Your hash approach:


def unique_list(size)
  limit = size * 10
  h = {}
  h[rand(limit) + 1] = true while h.length < size
  h.keys
end

n = 128
while n < 1000000
  time = Time.now
  arr = unique_list(n)
  puts "#{n} element array completed in #{Time.now - time} seconds"
  n *= 2
end

128 element array completed in 0.000194 seconds
256 element array completed in 0.000377 seconds
512 element array completed in 0.000731 seconds
1024 element array completed in 0.010189 seconds
2048 element array completed in 0.003123 seconds
4096 element array completed in 0.008567 seconds
8192 element array completed in 0.019194 seconds
16384 element array completed in 0.041844 seconds
32768 element array completed in 0.069025 seconds
65536 element array completed in 0.121666 seconds
131072 element array completed in 0.296778 seconds
262144 element array completed in 0.682297 seconds
524288 element array completed in 1.43068 seconds

the array is exponentially slower.

You're right i think - the use of Array#include? is what kills the array approach.  Your approach is better because you let the uniqueness take care of itself and just look at the size of the hash, which is much faster.  I wonder if hashes store their size as an instance variable, to save having to calculate it every time?

Last edited by Max Williams (2010-01-18 11:29:19)

###########################################
#If i've helped you then please recommend me at Working With Rails:
#http://www.workingwithrails.com/person/ … i-williams

Re: Ruby doesn't support "do while" loops?

Array#include must examine every entry in the array, so the performance gets exponentially worse as the array gets bigger, whereas most implementations of hash use some kind of b-tree as an index into the hash, so the lookup is much faster. If it gets a duplicate, it just sets it to true anyway, so there is no conditional processing either. Don't know if a hash stores its size as an instance variable or not - I would hope yes, otherwise it would have to navigate the b-tree each time which would be almost as bad as examining every array entry...

Thanks for doing the legwork on the benchmarking though, quite an interesting* result.

* this probably indicates that I should get out more roll

Re: Ruby doesn't support "do while" loops?

specious wrote:

* this probably indicates that I should get out more roll

smile it was quite interesting as it was an almost perfect doubling of time for doubling of size in yours and almost perfect quadrupling of time for doubling of size in mine.  A nice illustration of N vs 2-to-the-N time smile

###########################################
#If i've helped you then please recommend me at Working With Rails:
#http://www.workingwithrails.com/person/ … i-williams