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

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).

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

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).

Таким образом, мы имеем 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 

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