ruby-on-rails - 在 Ruby 中初始化具有高索引的空数组是否昂贵？

Question

我想通过创建 3d 数组来在 ruby​​ 中保存 year-month-day 以进行查找 O(1):

dates = [Date.new(2014,2,15), Date.new(2015, 8, 27), Date.new(2014, 7, 4), ...]
res = []
dates.each do |d|
    # Init year if DNE
    if res[d.year].nil?
        res[d.year] = []
    end
    # Init month if DNE
    if res[d.year][d.month].nil?
        res[d.year][d.month] = []
    end
    # Set the [year][month][day] = 1
    res[d.year][d.month][d.day] = 1
end

# Use case
def date_in_array?(date)
    !res[self.year].nil? && !res[self.year][self.month].nil? && !res[self.year][self.month][self.day].nil?
end

date_in_array?(Date.new(2014, 2, 15))
=> true

date_in_array?(Date.new(2014, 9, 21))
=> false

另一种方法是使用哈希来保存日期，但它在内存方面可能会变得昂贵。

所以我的问题是，ruby 如何管理数组索引超出范围？

我想确保通过执行 res[2015] = []，ruby 不会初始化 res[0..2014] 集，这是在这种情况下确实是一种存储数据的好方法。

Answer 1

I want to make sure that by doing res[2015] = [], ruby doesn't initialize the res[0..2014] set and this is indeed a good way to store data in this case.

没有。确实如此。此代码段占用了大部分 RAM，只是使我的系统无响应。确凿的证据。

@a = []
@a[1_000_000_000] = 1

如何存储数据取决于您期望什么值作为键。

根据定义，数组是一大块连续的存储单元，每个单元存储一个值。实现恒定访问时间是因为对于任何已知索引，它需要一次算术运算(基数+索引)来计算所需单元的内存地址。如果键是非顺序的，那么您一开始就不应该使用数组。

磁盘不用于阵列存储，仅用于虚拟 RAM(可以配置为使用交换空间，但不要指望它)。

如果键是连续的但不是从 0 开始(即 1990 年及以后)，您可以为内置数组创建一个包装器，其中包含一个内部数组和一个用于计算“该数组中的真实索引”。实现 [] 和 []=，您将获得类似数组的访问。

class ShiftedArray
  def initialize(lower_bound)
    @lower_bound = lower_bound
    @storage     = []
  end

  def []=(key, value)
    @storage[key - @lower_bound] = value
  end

  def [](key)
    @storage[key - @lower_bound]
  end
end

ShiftedArray.new(1) 实际上是 1 索引数组。

当然，这远非理想，它不允许写入低于构造时设置的边界的值。您可以实现它，但这超出了本答案的范围。

如果键是高度分散的数字，您最好使用 Hash 或搜索树作为数据结构。