php - 在不规则间隔的大量数据中找到一段时间内最大的变化

Question

在我的情况下，我必须处理由日期组成的大型数据集，每个日期都有对应的数字。这些日期之间的间隔不是静态的，这意味着有些日期相隔几秒，而另一些则相隔几天。此数据具有以下格式:(以 PHP 数组转储格式给出)

Array[2000] {  
   Array[2] {  
      Date: 2014-7-7 7:07:07  
      Data: 29.2934  
   }
   Array[2] {  
      Date: 2014-7-7 7:08:13
      Data: 30.10203
   }
   Array[2] {
      Date: 2014-7-9 3:24:43
      Data: 30.10203
   }
   ...
}

我需要在某个时间限制内(例如一天、一周等)找到两个日期之间的最大数据增量。我一直在使用此 PHP 代码来完成此操作:

for ($i=0; $i<$numrows-1; $i++) {
    for($o=1; $o<($numrows-1)-$i; $o++) {
        if((strtotime($dataArray[$i+$o]['Date'])-strtotime($dataArray[$i]['Date']))<86400) { //86400 for constraint of one day
            $diffs[$i]['date'] = strtotime($dataArray[$i+$o]['Date']);
            $diffs[$i]['data'] = $dataArray[$i+$o]['data']-$dataArray[$i]['Data'];
        }
    }
}

这将返回一个数组，其中包含数据数组每个元素的边界内的最大结束日期以及它们之间的数量差异。然后我可以搜索 diffs 数组的最大数据元素以确定哪一天数据增加最多。这工作正常，但不幸的是，它涉及到将我的服务器的 CPU 置于 100% 的状态以处理某些数据集超过 20 秒，并导致它在此期间对其他请求无响应。

我想弄清楚的是如何以更有效的方式做到这一点；我做了一些研究，我认为这是在 O(n^2) 时间内，但是我似乎找不到使用更有效算法的方法。有没有什么方法可以使用更少的处理时间和系统资源来实现同样的目标？

Answer 1

有了数据库，实现起来就容易多了。无论如何...

我将添加一个按增量日期和增量数据排序的索引(这是一个保留对原始数据的引用的附加数组)。

Array[2000] {
   Array[2] {
      DeltaDate: 10
      DeltaData: 1.234
      Row: ???
   }
   Array[2] {
      DeltaDate: 66
      DeltaData: 0.80863
      Row: 1
   }
   Array[2] {
      Date: 160000
      Data: 0
      Row: 2
   }
   Array[2] {
      Date: 160000
      Data: 1
      Row: ???
   }
   Array[2] {
      Date: 160000
      Data: 234
      Row: ???
   }
   ...
}

之后，我将在该索引中查找满足时间限制的最高记录。鉴于索引是有序的，您可以使用二进制搜索 (O=log N)。

在 SQL 数据库中，这将用以下查询表示:

SELECT * FROM Array
    WHERE DeltaDate <= time constraint
    ORDER BY DeltaData DESC LIMIT 1