Инициализирует пустой массив с высокими индексами в Ruby?

Question

Я хочу, чтобы сохранить year-month-day в рубин, создавая 3D-массив, чтобы смотреть вверх 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 

В качестве альтернативы можно использовать хэш для сохранения даты, но он может получить дорогой с точки зрения памяти.

Так что мой вопрос в том, как рубин управляет индексом массива вне диапазона?

Я хочу убедиться, что при выполнении res[2015] = [] рубин не инициализирует набор res[0..2014], и это действительно хороший способ хранения данных в этом случае.

Answer 1

Я хочу, чтобы убедиться, что при этом res[2015] = [], рубин не инициализировать res[0..2014] множество, и это действительно хороший способ хранить данные в этом случае.

Nope. Оно делает. Этот фрагмент только оказал мою систему невосприимчивой, поедая большую часть ОЗУ. Твердое доказательство.

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

Как хранить данные зависит от того, какие значения вы ожидаете от числа клавиш.

Массив по определению представляет собой большой блок последовательных ячеек памяти, каждый из которых хранит значение. Постоянное время доступа достигается за счет того, что для любого известного индекса требуется одна арифметическая операция (base + index) для вычисления адреса памяти нужной ячейки. Если ключи не являются последовательными, вы не должны использовать массив в первую очередь.

Диски не используются для хранения массива, а только виртуальная оперативная память (которая может быть настроена на использование пространства подкачки, но не рассчитывает на нее).

Если ключи являются последовательными, но не начинаются близко к 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 или дерево поиска в качестве структуры данных.

Answer 2

Хеш, вероятно, будет намного дешевле трехслойной структуры массива. Накладные расходы для любого отдельного массива намного выше, чем для одной записи Хэш.

Не забывайте, что поиск хэшей технически O (1), постоянное время, поэтому здесь нет никакой проблемы с производительностью. Есть и другие варианты.

супер версия слабину этого используется множество, как гибрид между массивом и Hash:

require 'set' 
dates = Set.new([ Date.new(2014,2,15), Date.new(2015, 8, 27), Date.new(2014, 7, 4) ]) 

dates.include?(Date.new(2014,2,15)) 
# => true 
dates.include?(Date.new(2014,2,5)) 
# => false 

Вы можете приспособить это к Hash, где ключ является дата или строка. Вы часто найдете самое простое решение: достаточно быстро.

Answer 3

Инициализирует пустой массив с высокими индексами, дорогими в Ruby?

Да. Ruby будет выделять память для записей 0..2015 в вашем примере. В этом случае вы хотите хэшировать; хэш-поиски (как упоминается тадман) амортизируются O (1), поэтому скорость не должна вызывать беспокойства, а использование памяти также должно быть значительно улучшено по сравнению с разреженными массивами.

В качестве примера (MRI 2.2.2):

require 'objspace' 
res = []; ObjectSpace.memsize_of res       #=> 0 
res = []; res[100] = true; ObjectSpace.memsize_of res   # => 928 
res = []; res[2015] = true; ObjectSpace.memsize_of res  # => 16248 
res = {}; res[100] = true; ObjectSpace.memsize_of res   # => 192 
res = {}; res[2015] = true; ObjectSpace.memsize_of res  # => 192