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

SailCat

ruby的1.81没有Array#sample

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

第一个版本：

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

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

复杂度o(n!)

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

第二个版本：

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

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

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

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

第三个版本：
每取一个数，就把最后一个数挪过来

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

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

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

第四个版本：
取前n个数，随机和后面的数交换

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[i]; t[i] = t[d]; t[d] = t[i]}
    t[0...n]
  end
end

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[i]; t[i] = t[d]; t[d] = t[i]}


    t[0...n]


  end


end

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

测试代码和结果

chd114

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

RaidenInfinity

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

summer92

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

shitake

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

不死鸟之翼

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