查找重复/冲突时的数组循环性能

Question

这段代码通过一个事件数组循环，每个事件都有一个开始和结束时间.并简单地设置一个“匹配”键来表示它已经匹配了另一个事件(即冲突来解决)：

<?php

$results = array(
        array('from' => 1, 'to' => 3),
        array('from' => 3, 'to' => 6),
        array('from' => 7, 'to' => 9),
        array('from' => 4, 'to' => 8),
    );

$k = 0;

foreach ($results as $p_id => $p_result) {

    foreach ($results as $c_id => $c_result) {
        if ($p_id == $c_id) {
            continue;
        }
        $k++;
        if ($p_result['from'] < $c_result['to'] && $p_result['to'] > $c_result['from']) {
            $results[$p_id]['match'] = $c_id;
            break;
        }
    }

}

print_r($results);
echo $k;

?>

这本身并不一定是缓慢的，但可能是当成千上万的事件被检查时.例如，对事件使用DateTime对象或UNIX时间戳。

在我的电脑上尝试3000个随机事件需要大约1秒的“中断”时间和3秒的时间。

往返碰撞检查本身是由：Comparing date ranges激发的。

我看到的主要问题是，一旦事件1被检查为事件2-4，那么事件2-4实际上不需要对照1来检查自己：

$results[$p_id]['match'] = $c_id;
$results[$c_id]['match'] = $p_id;

但是，我想不出一种优雅的工作方式，尽管这样做并不会使代码更难阅读。

一种可能的方法是为那些“通过”检查的事件创建一个新的数组，但我怀疑在数组中添加/删除元素的内存管理远远超过执行简单的整数检查。

Answer 1

与使用foreach不同，您可以在那里使用两个数字循环。然后，您的“内循环”可以从当前的outer value+1开始，您将不会处理任何双重组合。

$cachedCount = count($array);
for ($outer = 0; $outer < $cachedCount; $outer++){
  for ($inner = $outer+1; $inner< $cachedCount; $inner++){
    // process entries. no duplicates here. Only the ones that are dupplicates, 
    // but shouldn't be.
  }
}

即假设数组

0 -> "a"
1 -> "b"
2 -> "c"
3 -> "d"

它将采取以下步骤：

outer = 0; inner = 1; //a-b
outer = 0; inner = 2; //a-c
outer = 0; inner = 3; //a-d

outer = 1; inner = 2; //b-c
outer = 1; inner = 3; //b-d

outer = 2; inner = 3; //c-d

因此，检查所有组合，但不处理重复(a-c和c-a)或普通组合(a-a，b-b)。显然，对于两个元素，它将开始和结束比较0-1。(与执行2×2迭代的4次比较(1-1、1-2、2-1、2-2)相比，这是一次比较。

Answer 2

可以使用索引来调整循环的大小：

<?php
$arr = array( '1', '2', '3', '4' );
for($a=0; $a<count($arr); $a++){
    for($b=0; $b<$a; $b++){
        echo "compare: ".$arr[$a]." ".$arr[$b].",\n";
    }
}

//Ouput
//compare: 2 1,
//compare: 3 1,
//compare: 3 2,
//compare: 4 1,
//compare: 4 2,
//compare: 4 3,

http://codepad.org/BdxzvTvj

请注意，虽然这是一个很好的解决方案，它只会提供50%的速度。有些算法上的变化可能会使这些收益相形见绌。

Answer 3

也许是这样的：

foreach ($results as $p_id => $p_result) {
    foreach (array_slice($results, $p_id+1, NULL, true) as $c_id => $c_result) {
        if ($p_result['from'] < $c_result['to'] && $p_result['to'] > $c_result['from']) {
            $results[$p_id]['match'] = $c_id;
            break;
        }
    }

}