请教关于Hash值的问题

赛露休斯

例如
a = {"阿尔西斯"=>2004, "艾力克斯"=>2000, "杰克"=>2003, "拉尔夫"=>2007}
我想获取以字符串的形式返回里面第二大的值及它所对应的主键名

这里要返回的是
"2004"
"阿尔西斯"

苏小脉

1. a = {"阿尔西斯"=>2004, "艾力克斯"=>2000, "杰克"=>2003, "拉尔夫"=>2007}
   
2. 
   
3. lrgt = [ nil, -1.0 / 0 ]
   
4. sec_lrgt = [ nil, nil ]
   
5. 
   
6. a.each do |k, v|
   
7.         if v > lrgt[1]
   
8.                 sec_lrgt.replace(lrgt)
   
9.                 lrgt = k, v
   
10.         end
    
11. end
    
12. 
    
13. p sec_lrgt

复制代码

六祈

max2_value = a.values.sort[-2]
max2_value_str = max2_value.to_s
max2_value_index = a.index(max2_value).to_s

苏小脉

回复 六祈 的帖子

排序的主要问题是有额外的不容忽视的开销：
如果 m = 散列表桶的数量，n = 实际的元素（键值对）个数，那么二楼的方法需要 O(m) 时间，而三楼的方法却是 O(m)+O(n*log(n))，分别是 Hash#value 和 Array#sort 需要的时间，无论 m 是否大于 n，O(m)+O(n*log(n)) 都大于 O(m):victory:

六祈

回复 苏小脉 的帖子

如今论坛点评会吃进回复，于是只有回复了。
紫苏大人的方法诚然效率更高，不过愚者以为如果这个哈希表并不大的话，似乎应该不用在意。
另外求教下紫苏大人，愚者之前曾试过对一个上百万元素的数组使用sort[-1]取最大值和max取最大值，结果发现sort[-1]耗时极短，而max则比之至少慢了上百倍


六祈于2010-12-10 11:22补充以下内容：
点评他人会吃进自己的回复。。可怕

苏小脉

回复 六祈 的帖子

理论上不应该出现这么诡异的现象呀，虽说 Ruby 的 Array#sort 底层是一个高度优化的 quicksort 实现，但无论如何也是 O(n*log(n))，不可能比 max 的 O(n) 快，除非 max 带的块里面有什么糟糕物。能否提供再现问题的代码？

六祈

回复 苏小脉 的帖子

1. def time_1000
   
2. start=Time.now
   
3. 1000.times do
   
4. yield
   
5. end
   
6. stop = Time.now
   
7. puts stop - start
   
8. end
   
9. a=*1..10000
   
10. 
    

复制代码

好像没有上百倍那么夸张，不过目前是15倍左右的差距吧。诡异

苏小脉

回复 六祈 的帖子

简单分析了一下源代码，大概是这样：

quicksort 在不同的场合下性能不同，它的核心是分治法，分治用的枢轴（pivot）选择是决定时间效率的关键。最好的情况下，是每一次分治都能选到当前分区的中数作为枢轴，然后再分，这需要 O(n*log(n))。你给的例子中的数组，元素按严格的升序排列，这在底层的实现中是一个优化的机会，它能选到更好的枢轴。最坏的情况下，是选到当前分区的最小或最大的数，而如果每次分治都出现这种情况，quicksort 则需要 O(n^2) 的时间。所以如果用下面这样的乱序数组，Array#sort 耗时就比较高了：

1. CASES = 10000
   
2. 
   
3. arr = [ ]
   
4. CASES.times do
   
5.         arr << rand(CASES)
   
6. end

复制代码

至于 max，它确实很慢，因为它底层还是通过 rb_function_call 去调用了 Ruby 层面的 each 方法进行迭代，然后在里面又调用 Ruby 层面的比较方法（< 和 >），还不提中间的一堆其它杂项处理又封了不少层，其中就包括迭代器的处理，这些都是职业的效率杀手。Array#sort 则不同，一旦调用就全权交给 C 进行高效的排序，不会再回来调用 Ruby。想来也是出于设计上的限制，因为 max （还包括像另一帖讨论过的 inject 的不少函数）是给 Enumerable 模块定义的，它直接抽象为调用 Mixin 这个模块的类的相应函数（each、<=>、<、> 等）来实现枚举，所以和实现了 Enumerable 这个接口的类的细节无关。

理论上来讲，Enumerable#max 仍然是 O(n)，Array#sort 仍然是 O(n log n)，但真实世界中变数很多，往往和理论有所差异。话说回来，Big-O 毕竟只是一种初级的分析算法的标记法，高级的我也还没接触过，并不能真当成红宝书来用。就好比我有固定 n = 一百万的数据量，由于 n 是常量，所以理论上对数据的运算应该是 O(1) 内完成，但实际上数据量已经到了 O(n) 的级别。

赛露休斯

两个方法都能实现，最后使用的是六祈的比较简单
两位打了那么多字也挺辛苦，就都认可一下吧