Ruby Ruby 2.0 in Detail

luikore · 2013年03月13日 · 最后由 hiveer 回复于 2014年10月17日 · 6834 次阅读

本帖已被管理员设置为精华贴

http://globaldev.co.uk/2013/03/ruby-2-0-0-in-detail/

这篇长博客还列出了包括 stdlib 的好多细节改进, 例如现在你可以:

gem install --file Gemfile

可以用 markdown 写 rdoc 了!

rdoc --markup markdown

就是新加的 __callee__ 两个下划线和 caller 命名不太一致, __dir__ 和 __FILE__ 命名也不太一致...

2013.3.15 补充:

rubyist 杂志也发了一个 2.0 特辑, 特别列出了一些要注意的地方 http://jp.rubyist.net/magazine/?Ruby200SpecialEn-note

例如基础数值对象都 freeze 了 (BigDecimal, Rational, Complex 不在此列), 不能对 1 或者 0.5 设实例变量了 (方便以后做数值运算相关的优化).

但是 Fixnum, Integer, Float... 等相关 class 没有 freeze, 可以继续加方法, 但是方法中注意不要访问或者添加实例变量.

ko1 的关于 ruby vm internal 的日记 (日文)

http://www.atdot.net/~ko1/diary/201212.html

24 个赞

i5ting #2 2013年03月13日

补充一个，http://ruby-china.org/topics/9215

fsword #3 2013年03月13日

不错，不过那个 bsearch 没看懂，似乎比 select 方便些，但是感觉没有特别大的价值

hooopo #4 2013年03月13日

#2 楼 @fsword bsearch 是针对排序好的进行二分查找吧？

i5ting #5 2013年03月13日

#3 楼 @hooopo 是不是 util.c 里的 c 的二分查找啊？

skandhas #6 2013年03月13日

#2 楼 @fsword 主要价值是性能的提升，对于有序序列，二分查找的平均性能要好的多。

hooopo #7 2013年03月13日

#4 楼 @i5ting 我也不知道哇..........

jjym #8 2013年03月13日

不知道这两个命名有何深意啊

luikore #9 2013年03月13日

@fsword @hooopo @i5ting @skandhas

是要预先排好序

查找最快还是 Hash, 但是消耗空间比较大, 数组消耗的空间就小很多

二分查找时间复杂度是 O(log(n)), 和 Java 的 TreeMap, C++ 的 std::map 一样. 和 Hash 的 O(1) 相差不大了.

另外二分查找可以用比较条件, Hash 查找只能严格匹配. 而 select 要遍历全部元素, O(n) 的复杂度对于大数组 (>100k 之类的) 就显得慢了, 小数组的话速度区别不大.

二分查找因为有序性限制了两种使用模式, select 就没有限制

模式 1 是 block 返回 true / false / nil 可以用于查找大于 / 大于等于 N 的 (最小) 值, 例如查找 x >= 5:

a.bsearch{|x| x >= 5 }

模式 2 是通用的模式, block 返回正/负/0

可以用于查找区间内的值, 例如查找 4 <= x <= 8:

a.bsearch{|x|
  if x < 4
    1  # x 太小了, 返回正数, 告诉 bsearch 我们需要更大的
  elsif x > 8
    -1 # x 太大了, 返回负数, 告诉 bsearch 我们需要小一些的
  else
    0 # 枚举的 x 在区间内, 返回 0, 查找结束
  end
}

也可以用于查找小于 / 小于等于 N 的值, 例如查找 -∞ < x < 5:

a.bsearch{|x|
  if x >= 5
    -1
  else
    0
  end
}

模式 2 在查找范围值时返回符合条件 (block 返回 0) 的第一个结果, 和值的位置有关, 没有保证的... 模式 2 用 N <=> x 可以做严格匹配的查找

和 libc 的 bsearch 相似 (man bsearch), 和 C++ 的二分查找区别比较大... C++ 的二分查找的核心是重新定义 <, 然后有 lower_bound, upper_bound 的用法...

5 个赞

10 楼已删除

donnior #11 2013年03月13日

先前回了一楼，后来发现错了。

我觉得 bsearch 很不直观，暂且不说它的两种使用模式；仅就 find-minimum mode 而言，文档中说要找到 i 元素，要求

所有索引小于 i 的元素要使得 block 返回 false
所有索引等于或大于 i 的元素要使得 block 返回 true

但是在使用中，

arr = [1,4,7,8,9,13,14,15]

arr.bsearch {|x| x > 3} #=> 4 # 正确

但是如果如下使用就很诡异了

arr = [1,4,7,8,9,13] arr.bsearch {|x| x%5 > 3} #=> nil ??

arr = [1,4,7,8,9,13,14,15] arr.bsearch {|x| x%5 > 3} #=> 9 ??

这里 15 似乎不满足条件 2 啊

继续，如果

arr = [1,4,7,8,9,13,15] arr.bsearch {|x| x%5 > 3} #=> nil ??

只是去掉了 14 这个元素，结果就为nil了

太诡异了，难道说 block 里面只能使用>而不能使用%之类的么？

不过这个 bsearch 和 select 不同是肯定的了！

fsword #12 2013年03月13日

#10 楼 @donnior ~~二叉树查找，不是遍历，所以只能用值和范围来约束，不能对值进行进一步处理~~ 楼下说的更准确，自宫一下 #8 楼 @luikore 疑惑的就是这个 “已排序”，试验了一下，果然是必要条件啊

2.1.0dev :009 > array = [2, 4, 8, 16, 32].shuffle
 => [32, 2, 8, 4, 16] 
2.1.0dev :010 > array.bsearch {|x| x >= 4}       #=> 4
 => 8 
2.1.0dev :011 > array.bsearch {|x| x >= 7}       #=> 8
 => 8 
2.1.0dev :012 > array.bsearch {|x| x >= 9}       #=> 16
 => 16 
2.1.0dev :013 > array.bsearch {|x| x >= 0}       #=> 2
 => 32 
2.1.0dev :014 > array.bsearch {|x| x >= 33}      #=> nil
 => nil

luikore #13 2013年03月13日

#10 楼 @donnior

x 在 arr 中是升序的, 但 x%5 不是升序的, 所以二分查找的条件就不对了

arr = [1,4,7,8,9,13,15]
arr = arr.map{|x| [(x%5), x] }.sort
arr.bsearch {|(x, y)| x > 3}[1]

luikore #14 2013年03月13日

#10 楼 @donnior 另外用单调函数 + 比较是没问题的

# 单调增
def f x
  x * 2
end
# 单调降
def g x
  -x
end
arr.bsearch {|x| f(x) > 6 }
arr.bsearch {|x| g(x) < -3 }

donnior #15 2013年03月13日

#11 楼 @fsword #13 楼 @luikore Thanks, 明白了

zw963 #16 2013年03月16日

哇~ 终于可以对 2.0 有一个较全面了解了.

非常感谢~

说起 ko1, 原来他就是写 YARI 那个?? 他的 github 页面刚刚发布了一个基于 ruby2.0 debug API 的 debugger2

https://github.com/ko1/debugger2

hiveer #17 2014年10月17日

#11 楼 @fsword 你测试的例子不太好，没有测出来，其实应该是充分条件。 array = [2, 4, 8, 16, 32].shuffle => [8, 32, 2, 16, 4]

pry(main)> array.bsearch { |x| x > 17 } => nil

需要登录后方可回复, 如果你还没有账号请注册新账号