Как найти значение, которое охватывает большинство точек данных в сочетании с допуском?

Question

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

a = [
  ["15:50:46", "15:50:47", "15:50:46", "15:50:47"],
  ["15:50:46", "15:50:46", "15:50:45", "15:50:45"],
  ["15:50:46", "15:50:46", "15:50:47", "15:50:47", "15:50:50", "15:50:49",
   "15:50:49", "15:50:48", "15:50:48", "15:50:50", "15:50:53", "15:50:52",
   "15:50:53", "15:50:51", "15:50:52", "15:50:51"],
  ["15:50:46", "15:50:46", "15:50:45", "15:50:45", "15:50:48", "15:50:48",
   "15:50:49", "15:50:49", "15:50:47", "15:50:47", "15:50:51", "15:50:52",
   "15:50:52", "15:50:51", "15:50:50", "15:50:50"],
  ["15:50:46", "15:50:47", "15:50:51", "15:50:47", "15:50:50", "15:50:51",
   "15:50:50", "15:50:46", "15:50:49", "15:50:48", "15:50:48", "15:50:44",
   "15:50:49", "15:50:44", "15:50:45", "15:50:45"],
  ["15:50:46", "15:50:46", "15:50:45", "15:50:45", "15:50:42", "15:50:43",
   "15:50:42", "15:50:44", "15:50:43", "15:50:48", "15:50:49", "15:50:49",
   "15:50:48", "15:50:44", "15:50:47", "15:50:47"],
  ["15:50:46", "15:50:47", "15:50:46", "15:50:43", "15:50:47", "15:50:45",
   "15:50:44", "15:50:44", "15:50:48", "15:50:48", "15:50:45", "15:50:41",
   "15:50:43", "15:50:42", "15:50:42"],
  ["15:50:46", "15:50:47", "15:50:47", "15:50:43", "15:50:43", "15:50:42",
   "15:50:46", "15:50:44", "15:50:45", "15:50:40", "15:50:40", "15:50:41",
   "15:50:45", "15:50:42", "15:50:44", "15:50:41"],
  ["15:50:29", "15:50:26", "15:50:29"]
] 

require 'time'

times = a.map { |b|
  b.map { |s| DateTime.strptime('2019-01-24 '+s, '%Y-%m-%d %H:%M:%S').to_time } }
  #=> [[2019-01-24 15:50:46 +0000, 2019-01-24 15:50:47 +0000,
  #     2019-01-24 15:50:46 +0000, 2019-01-24 15:50:47 +0000]
  #     ...
  #    [2019-01-24 15:50:29 +0000, 2019-01-24 15:50:26 +0000,
  #     2019-01-24 15:50:29 +0000]]

Каждый элемент в массиве верхнего уровня является точкой, каждая точка имеет несколько временных отметок, которые она оценивает. Однако для каждой точки может использоваться только одна временная метка. Цель состоит в том, чтобы найти значение, которое в сочетании с допуском (скажем, 3 секунды для этого примера) будет содержать наибольшее количество точек. Оптимальное значение на самом деле не может быть одной из точек, так же как прямая линия на графике не может касаться каких-либо точек.

Я подумал об использовании декартовой системы для определения среднего (среднего или среднего) и стандартного отклонения данных, но это может быть медленным и все же не дать мне правильный результат.

Заранее спасибо.

Answer 1

def max_hits(times, tolerance)
  coverage = times.map do |a|
    a.each_with_object({}) do |t,h|
      ((t-tolerance).to_i..(t+tolerance).to_i).each { |tt| h[Time.at(tt)] = t }
    end
  end
  min_secs, max_secs = times.flatten.minmax.map(&:to_i)
  min_secs += tolerance
  max_secs -= tolerance
  if min_secs > max_secs
    best = Time.at((min_secs+max_secs)/2)
  else
    best = Time.at((min_secs..max_secs).max_by do |n|
      t = Time.at(n)
      coverage.count { |h| h.key?(t) }
    end)
  end
  [best, coverage.map { |h| h[best] }]
end

[0, 1, 2, 8, 9, 13, 14].each do |tolerance|
  print "tolerance = #{tolerance} seconds, best = "
  best, a = max_hits(times, tolerance)
  puts "#{best}, count = #{a.compact.size}"
  puts "  #{a}"
end

tolerance = 0 seconds, best = 2019-01-24 15:50:46 +0000, count = 8
  [2019-01-24 15:50:46 +0000, 2019-01-24 15:50:46 +0000, 2019-01-24 15:50:46 +0000,
   2019-01-24 15:50:46 +0000, 2019-01-24 15:50:46 +0000, 2019-01-24 15:50:46 +0000,
   2019-01-24 15:50:46 +0000, 2019-01-24 15:50:46 +0000, nil]
tolerance = 1 seconds, best = 2019-01-24 15:50:45 +0000, count = 8
  [2019-01-24 15:50:46 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:46 +0000,
   2019-01-24 15:50:45 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:44 +0000,
   2019-01-24 15:50:45 +0000, 2019-01-24 15:50:44 +0000, nil]
tolerance = 2 seconds, best = 2019-01-24 15:50:44 +0000, count = 8
  [2019-01-24 15:50:46 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:46 +0000,
   2019-01-24 15:50:45 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:44 +0000,
   2019-01-24 15:50:42 +0000, 2019-01-24 15:50:44 +0000, nil]
tolerance = 8 seconds, best = 2019-01-24 15:50:38 +0000, count = 8
  [2019-01-24 15:50:46 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:46 +0000,
   2019-01-24 15:50:45 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:44 +0000,
   2019-01-24 15:50:42 +0000, 2019-01-24 15:50:41 +0000, nil]
tolerance = 9 seconds, best = 2019-01-24 15:50:37 +0000, count = 9
  [2019-01-24 15:50:46 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:46 +0000,
   2019-01-24 15:50:45 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:44 +0000,
   2019-01-24 15:50:42 +0000, 2019-01-24 15:50:41 +0000, 2019-01-24 15:50:29 +0000]   
tolerance = 13 seconds, best = 2019-01-24 15:50:39 +0000, count = 9
  [2019-01-24 15:50:47 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:51 +0000,
   2019-01-24 15:50:50 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:47 +0000,
   2019-01-24 15:50:42 +0000, 2019-01-24 15:50:41 +0000, 2019-01-24 15:50:29 +0000]
tolerance = 14 seconds, best = 2019-01-24 15:50:39 +0000, count = 9
  [2019-01-24 15:50:47 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:51 +0000,
   2019-01-24 15:50:50 +0000, 2019-01-24 15:50:45 +0000, 2019-01-24 15:50:47 +0000,
   2019-01-24 15:50:42 +0000, 2019-01-24 15:50:41 +0000, 2019-01-24 15:50:29 +0000]

Для tolerance, равного 0, мы видим, что все элементы (массивы) times, кроме последнего, содержат время 2019-01-24 15:50:46 и что не существует времен, для которых count равно times.size (9). Обратите внимание, что это значение best также оптимально для значений допуска между 1 и 8 (но они отличаются от значений, показанных как best), поэтому для этих значений допуска явно имеется несколько оптимальных значений.

Видно, что

times.size
  #=> 9 
min_secs, max_secs = times.flatten.minmax.map(&:to_i)
max_secs - min_secs
  #=> 27     

Следовательно, для каждого из 28-2*tolerance значений времени будет проверяться каждый из 9 элементов (хэшей) coverage. Если бы времена были в миллисекундах, это было бы 1000*(28-2*tolerance) значениями времени, легко управляемым числом. Конечно, если бы диапазон времени и размера times был больше (или tolerance был меньше), вычислительные усилия соответственно увеличились бы.

Нельзя перебирать Time объектов, поэтому я написал, например,

((t-tolerance).to_i..(t+tolerance).to_i).each { |tt| h[Time.at(tt)] = t }

вместо

  (t-tolerance..t+tolerance).each { |tt| h[tt] = t }