Cross-Implementation Deterministic Array#shuffle

2019-05-31 00:20发布

It is possible to pass a random number generator to Array#shuffle that makes the shuffle deterministic.

For example, in MRI 1.9.3p327:

[1, 2, 3, 4].shuffle(random: Random.new(0)) # => [1, 2, 4, 3]
[1, 2, 3, 4].shuffle(random: Random.new(0)) # => [1, 2, 4, 3]

However, the random number generator implementation of Random isn't specified. Because of this, other implementations of Ruby have different results.

In Rubinius 2.0.0rc1 (1.9.3 release 2012-11-02 JI):

[1, 2, 3, 4].shuffle(random: Random.new(0)) # => [1, 3, 2, 4]
[1, 2, 3, 4].shuffle(random: Random.new(0)) # => [1, 3, 2, 4]

Incidentally, jruby-1.7.1 uses the same random number generator as MRI 1.9.3p327, but this is just by chance, not guaranteed.

In order to have consistent-across-implementation deterministic shuffle, I would like to pass a custom random number generator into Array#shuffle. I thought this would be trivial to do, but it turns out to be quite complicated.

Here is what I tried first, in MRI:

class NotRandom; end
[1, 2, 3, 4].shuffle(random: NotRandom.new) # => [4, 3, 2, 1]
[1, 2, 3, 4].shuffle(random: NotRandom.new) # => [4, 2, 1, 3]

I expected a NoMethodError telling me the interface I needed to implement.

Any insights?


UPDATE:

As @glebm points out, NotRandom inherited Kernel#rand, which is the interface needed. This is easily worked around, but unfortunately does not offer a solution.

class NotRandom
  def rand(*args)
    0
  end
end

In RBX:

[1, 2, 3, 4].shuffle(random: NotRandom.new) # => [1, 2, 3, 4]

In MRI:

[1, 2, 3, 4].shuffle(random: NotRandom.new) # => [2, 3, 4, 1]

1条回答
我想做一个坏孩纸
2楼-- · 2019-05-31 00:54

For me, the solution was a combination of two things:

  1. Figure out the Random API. It's just rand.

  2. Implement my own shuffle, because different Ruby implementations aren't consistent.

I used my_array.sort_by { @random_generator.rand }.

查看更多
登录 后发表回答