0

人们想要存储对象,允许通过数字键检索它们。这些键的范围可以从 0 到任意大小(例如,~100K),但不是范围内的每个自然数都有对应的对象。

一个人可能有以下几点:

structure[0] => some_obj_a
structure[3] => some_obj_b
structure[7] => some_obj_c
...
structure[100103] => some_obj_z

但是所有其他键(1、2、4、5、6、...)都没有关联的对象。数字键用于检索,因此提供“ID”以返回与该 ID 关联的对象:

ID = get_input_id
my_obj = structure[ID]

Ruby 中这种场景最有效的数据结构是什么?出于什么原因?(到目前为止,我可以看到它是一个散列或一个数组。)

我将“高效”定义为:

  • 使用最少的内存
  • 最快的查找时间
  • 最快的条目创建/更新(任意键)

此结构的初始化可能是

hsh = Hash.new # or Array.new
hsh[0] = {:id => 0, :var => "a", :count => 45}
hsh[3] = {:id => 3, :var => "k", :count => 32}
hsh[7] = {:id => 7, :var => "e", :count => 2}
4

1 回答 1

4

您基本上已经描述了稀疏数组或散列。

散列很快,只使用他们必须使用的内存。它们还具有内存效率。没有“神奇”的数据结构可以更快。使用哈希。

于 2012-11-28T23:56:52.093 回答