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 的日记 (日文)
@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
的用法...
先前回了一楼,后来发现错了。
我觉得 bsearch 很不直观,暂且不说它的两种使用模式;仅就 find-minimum mode 而言,文档中说要找到 i 元素,要求
但是在使用中,
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 不同是肯定的了!
#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
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]
哇~ 终于可以对 2.0 有一个较全面了解了。
非常感谢~
说起 ko1, 原来他就是写 YARI 那个?? 他的 github 页面刚刚发布了一个基于 ruby2.0 debug API 的 debugger2