Project1

标题: o(1)的算法也许并不是最优化的……脚本语言太神奇了 [打印本页]

作者: SailCat 时间: 2018-1-16 14:59
标题: o(1)的算法也许并不是最优化的……脚本语言太神奇了
本帖最后由 SailCat 于 2018-1-16 15:12 编辑

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 时间: 2018-1-16 15:01
這4種裏，1.9用的是哪一種···

作者: RaidenInfinity 时间: 2018-1-16 15:19

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

作者: summer92 时间: 2018-1-16 18:59
机器码是最快的了，代码运行中全部都翻译成0和1，最底层的最快，对于C来说是这样的，鬼知道rm进行了什么奇怪的处理

作者: shitake 时间: 2018-1-17 09:05
最优化的当然是jeff的O(1/n)啦越多越快

作者: 不死鸟之翼 时间: 2018-1-19 04:00
复杂度不是这么看的...

欢迎光临 Project1 (https://rpg.blue/)