[ruby-dev:49959] [Ruby trunk Bug#13136] large_array.sample(11)が遅い

Issue #13136 has been updated by Nobuyoshi Nakada.


方針はいいと思います。
RAND_UPTO()はrandオブジェクトのメソッドを呼ぶ場合例外が起きる可能性があるので、st_free_table(table)をrb_ensureにするとか、RARRAY_PTR_USE()を使われないとかしたほうがいいでしょう。

----------------------------------------
Bug #13136: large_array.sample(11)が遅い
https://bugs.ruby-lang.org/issues/13136#change-62538

* Author: tomoya ishida
* Status: Open
* Priority: Normal
* Assignee: 
* Target version: 
* ruby -v: ruby 2.4.0p0 (2016-12-24 revision 57164) [x86_64-darwin16]
* Backport: 2.2: UNKNOWN, 2.3: UNKNOWN, 2.4: UNKNOWN
----------------------------------------
Array#sampleのパフォーマンスを改善したい

```ruby
require 'benchmark'
arr = 100000.times.to_a;
Benchmark.measure{100000.times{arr.sample 10}}.real #=> 0.07052100007422268 速い!
Benchmark.measure{100000.times{arr.sample 11}}.real #=> 37.8880900000222 遅い!!!
```

現状のArray#sample(n)

```
n<=3 → 個別場合分け
3<n<=10 → 2重ループ O(n^2)
# n < 適当な閾値 → O(n)のアルゴリズムを使いたい
n>10 → dupしてshuffle O(size) 巨大配列から少数sampleする時に遅い
```

アルゴリズム改善案について

```ruby
# n>10の時の現状のアルゴリズム O(size)
def sample arr, n
  arr = arr.dup
  n.times do |i|
    j = rand(arr.size - i) + i
    arr[i], arr[j] = arr[j], arr[i]
  end
  arr.take n
end

# dupをやめ、配列への代入を減らす(ただし元配列を破壊してしまう) O(n)
def sample arr, n
  n.times.map do |i|
    j = rand(arr.size - i) + i
    val = arr[j]
    arr[j] = arr[i]
    val
  end
end

# 配列を書き換える代わりに、どこを入れ替えたかhashに保存する(元配列を破壊しない) O(n)
def sample arr, n
  replace_table = {}
  n.times.map do |i|
    j = rand(arr.size - i) + i
    j2 = replace_table[j] || j
    replace_table[j] = replace_table[i] || i
    arr[j2]
  end
end
```

patch作りました

ベンチマーク

```
arr = 100000.times.to_a;
def measure;t=Time.now;yield;Time.now-t;end
p measure{10000.times{arr.sample 10}}
p measure{10000.times{arr.sample 11}}
p measure{10000.times{arr.sample 100}}
p measure{10000.times{arr.sample 1000}}
```

ruby 2.4.0p0

```
0.008185
3.938569
4.043285
4.142051
```

this patch

```
0.010408
0.016441
0.08861
0.684844
```


---Files--------------------------------
rb_ary_sample.patch (1.42 KB)


-- 
https://bugs.ruby-lang.org/