基于另一个数组从一个数组中删除值的最快方法

Question

我正在 Rails 应用程序中进行一些数据处理，我正在尝试处理性能痛点。我有 2 个数组 x_data 和 y_data，每个数组如下所示（当然具有不同的值）：

[
  { 'timestamp_value' => '2017-01-01 12:00', 'value' => '432' },
  { 'timestamp_value' => '2017-01-01 12:01', 'value' => '421' },
  ...
]

每个数组最多可能有 25k 个项目。我需要准备这些数据以进行进一步的 x-y 回归分析。

现在，x_data 或 y_data 中的某些值可以是 nil。如果 either x_data 或 y_data 在该时间戳处具有 nil 值，我需要从两个数组中删除值。然后我只需要 return 两个数组的值。

在我目前的方法中，我首先从值不为 nil 的两个数组中提取时间戳，然后对时间戳执行集合交集以生成最终的时间戳数组。然后我使用最后的时间戳数组 select 值。这是代码：

def values_for_regression(x_data, y_data)
  x_timestamps = timestamps_for(x_data)
  y_timestamps = timestamps_for(y_data)

  # Get final timestamps as the intersection of the two
  timestamps = x_timestamps.intersection(y_timestamps)

  x_values = values_for(x_data, timestamps)
  y_values = values_for(y_data, timestamps)

  [x_values, y_values]
end

def timestamps_for(data)
  Set.new data.reject { |row| row['value'].nil? }.
              map { |row| row['timestamp_value'] }
end

def values_for(data, timestamps)
  data.select { |row| timestamps.include?(row['timestamp_value']) }.
      map { |row| row['value'] }
end

这种方法的性能不是很好，我需要快速连续地对几组数据执行此操作。多个循环的开销加起来。必须有一种方法至少可以减少必要的循环次数。

如有任何想法或建议，我们将不胜感激。

Answer 1

您正在执行大量冗余迭代并创建大量中间数据数组。

你的timestamps_for 和 values_for 都执行 select，然后执行 map。 select 创建一个中间数组；由于您的数组最多包含 25,000 个项目，因此这可能是一个相同大小的中间一次性数组。您这样做四次，一次用于 x 和 y 时间戳，一次用于 x 和 y 值。您通过取两组时间戳的交集来生成另一个中间数组。您还对 nils 的两个数组进行了两次完整扫描，一次是为了查找具有非零值的时间戳，然后再次将您刚刚提取的时间戳映射到它们的值。

虽然从函数上转换输入数组肯定更具可读性，但您可以通过组合各种迭代和转换来显着减少内存使用和执行时间。

所有迭代都可以合并到一个数据集上的单个循环中（以及为第二个数据集生成时间戳-> 值查找哈希的设置时间）。第一组中不存在的任何时间戳都会使第二组中的时间戳无论如何都被忽略，因此没有理由在 both 组中找到所有时间戳，然后才找到它们的交集。

def values_for_regression(x_data, y_data)
  x_values = []
  y_values = []

  y_map = y_data.each_with_object({}) { |data, hash| hash[data['timestamp-value']] = data['value'] }

  x_data.each do |data|
    next unless x_value = data['value']
    next unless y_value = y_map[data['timestamp-value']]
    x_values << x_value
    y_values << y_value
  end

  [x_values, y_values]
end

我认为这在功能上是相同的，并且 quick benchmark 显示运行时间减少了约 70%：

                 user     system      total        real
yours        9.640000   0.150000   9.790000 (  9.858914)
mine         2.780000   0.060000   2.840000 (  2.845621)

基于另一个数组从一个数组中删除值的最快方法

Fastest way to remove values from one array based on another array

ruby-on-rails

ruby

data-analysis

data-processing