o(1)的算法也许并不是最优化的……脚本语言太神奇了

SailCat

ruby的1.81没有Array#sample

正在开发的插件，要大量的运用到sample操作，没办法，自己写一个

第一个版本：
[pre lang="ruby"]class Array
  # Implement sample for Ruby 1.9+
  def sample1(n=1)
    return self[rand(size)] if n == 1
    t = clone; n = [[n, size].min, 0].max; a = []
    n.times { a.push(t.slice!(rand(t.size)))}
    a
  end
end[/pre]
复杂度o(n!)

写出来就觉得slice!太粗暴了，o(n!)就是因为它，想改改

第二个版本：
[pre lang="ruby"]class Array
  # Implement sample for Ruby 1.9+
  def sample2(n=1)
    n == 1 ? self[rand(size)] : sort_by{rand(0)}[0...([[n, size].min, 0].max)]
  end
end[/pre]

这是个o(1)的算法，而且写法最简单，一行搞定
顺便说一下 sort_by{rand(0)}是我从sql的写法中得到的灵感，ruby1.81也没有shuffle，我用这个方法实现了shuffle

一般写成o(1)就觉得很好了，但我觉得哪怕取两个数也要把整个数组重排一遍太小题大作了

第三个版本：
每取一个数，就把最后一个数挪过来
[pre lang="ruby"]class Array
  # Implement sample for Ruby 1.9+
  def sample3(n=1)
    return self[rand(size)] if n == 1
    t = clone; n = [[n, size].min, 0].max; a = []
    n.times {|i| d = rand(size-i); a.push(t[d]); t[d] = t[size-1]}
    a
  end
end[/pre]

差不多了，但还是对push心有余悸，我不知道ruby的解释器是怎么实现变长数组的，但是还是想扔掉push

第四个版本：
取前n个数，随机和后面的数交换
[pre lang="ruby"]class Array
  # Implement sample for Ruby 1.9+
  def sample4(n=1)
    return self[rand(size)] if n == 1
    t = clone; n = [[n, size].min, 0].max
    n.times {|i| d = i + rand(size - i); tmp = t; t = t[d]; t[d] = t}
    t[0...n]
  end
end[/pre]

你们觉得哪个最优化？测试的结果可能和你们想的不一样哦。

测试代码和结果

[pre lang="ruby"]a = (1..100000).to_a
n = 100
t0 = Time.now
a.sample1(n)
t1 = Time.now
a.sample2(n)
t2 = Time.now
a.sample3(n)
t3 = Time.now
a.sample4(n)
t4 = Time.now
[/pre]

n	sample1	sample2	sample3	sample4
100	0.003	0.171	0.001	0.000
1000	0.034	0.174	0.001	0.000
10000	0.301	0.175	0.007	0.006
50000	1.036	0.167	0.032	0.028
99999	1.558	0.161	0.065	0.060

chd114

這4種裏，1.9用的是哪一種···

RaidenInfinity

大佬，你是不是完全无视了sort_by本身的复杂度和运行效率啊？

summer92

机器码是最快的了，代码运行中全部都翻译成0和1，最底层的最快，对于C来说是这样的，鬼知道rm进行了什么奇怪的处理

shitake

最优化的当然是jeff的O(1/n)啦 越多越快

不死鸟之翼

复杂度不是这么看的...