Эффективные алгоритмы слияния хэшей в разреженную матрицу

Question

У меня есть данные времени с нерегулярными интервалами, и мне нужно преобразовать их в разреженную матрицу для использования с библиотекой графиков.

В настоящее время данные имеют следующий формат:

{
  :series1 => [entry, entry, entry, entry, ...],
  :series2 => [entry, entry, entry, entry, ...]
}

где entry - это объект с двумя свойствами: timestamp (метка времени unix) и value (целое число). Мне нужно поместить его в этом формате как можно ближе к времени O (n).

{
   timestamp1 => [ value, value, nil ],
   timestamp2 => [ value, nil, value ],
   timestamp3 => [ value, value, value],
   ...
}

Здесь каждая строка представляет момент времени, для которого у меня есть запись.Каждый столбец представляет серию (линию на линейном графике).Вот почему очень важно представлять отсутствующие значения с помощью nil.

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

Answer 1

Меня слегка смущает, что вы просите O (n), поэтому не стесняйтесь меня поправлять, но, насколько я могу судить, O (n) легко возможно.

Сначала найдите длину вашего начального хэша (количество серий в данных). Это должно быть O (1), но не хуже, чем O (S) (где S не является последовательностью), а S <= O (n) (при условии, что нет ряда без значений), так что все равно O (n). </p>

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

matrix = Hash.new {|hsh,k| hsh[k] = Array.new(S)}

Затем просто просмотрите каждую серию по индексу. И для каждой записи установите подходящую ячейку в массиве для правильного значения.

Для каждой записи это O (1) (среднее) для поиска метки времени в хэше, затем O (1) для установки ячейки в массиве. Это случается n раз, давая вам O (n) там.

Также будет создание массива для каждой строки в матрице. Насколько мне известно, это O (1) для одного массива, поэтому O (T) (где T - количество временных меток) в целом. Поскольку мы не создаем пустые строки, в которых нет записей с этой отметкой времени, T должно быть <= n, так что это тоже O (n). </p>

Итак, в целом мы имеем O (n) + O (n) + O (n) = O (n). Вероятно, есть способы ускорить это в Ruby, но, насколько мне известно, это не только близко, но на самом деле O (n).

Answer 2

Примерно так:

num = series.count
timestamps = {}
series.each_with_index do |(k, entries), i|
  entries.each do |entry|
    timestamps[entry.timestamp] ||= Array.new(num)
    timestamps[entry.timestamp][i] = entry.value
  end
end

Не уверен, хотя в отношении начального упорядочения вашей серии, я думаю, что ваша реальная ситуация немного сложнее, чем представлено в вопросе.