Project1

标题: 请教关于Hash值的问题 [打印本页]

作者: 赛露休斯 时间: 2010-12-10 01:13
标题: 请教关于Hash值的问题
例如
a = {"阿尔西斯"=>2004, "艾力克斯"=>2000, "杰克"=>2003, "拉尔夫"=>2007}
我想获取以字符串的形式返回里面第二大的值及它所对应的主键名

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

作者: 苏小脉 时间: 2010-12-10 02:15

a = {"阿尔西斯"=>2004, "艾力克斯"=>2000, "杰克"=>2003, "拉尔夫"=>2007}
lrgt = [ nil, -1.0 / 0 ]
sec_lrgt = [ nil, nil ]
a.each do |k, v|
if v > lrgt[1]
sec_lrgt.replace(lrgt)
lrgt = k, v
end
end
p sec_lrgt

复制代码

作者: 六祈 时间: 2010-12-10 03:27
max2_value = a.values.sort[-2]
max2_value_str = max2_value.to_s
max2_value_index = a.index(max2_value).to_s

作者: 苏小脉 时间: 2010-12-10 04:09
本帖最后由苏小脉于 2010-12-10 04:10 编辑

回复六祈的帖子

排序的主要问题是有额外的不容忽视的开销：
如果 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:

作者: 六祈 时间: 2010-12-10 11:11
回复苏小脉的帖子

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

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

作者: 苏小脉 时间: 2010-12-10 11:46
回复六祈的帖子

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

作者: 六祈 时间: 2010-12-10 11:57
本帖最后由六祈于 2010-12-10 12:00 编辑

回复苏小脉的帖子

def time_1000
start=Time.now
1000.times do
yield
end
stop = Time.now
puts stop - start
end
a=*1..10000

复制代码

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

作者: 苏小脉 时间: 2010-12-10 21:25
回复六祈的帖子

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

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

CASES = 10000
arr = [ ]
CASES.times do
arr << rand(CASES)
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) 的级别。

作者: 赛露休斯 时间: 2010-12-11 22:54
两个方法都能实现，最后使用的是六祈的比较简单
两位打了那么多字也挺辛苦，就都认可一下吧

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