1

私はこのような配列を持っています:

$a = array(
    array(2 => 1, 4 => 2, 9 => 3),
    array(3 => 7, 4 => 5, 7 => 3),
    array(1 => 6, 4 => 5),
    ...
);

そのため、配列には、整数キー => 整数値を持つ大量のサブ配列が含まれています。ここで、キーを共有しないサブ配列を見つけたい、またはキーを共有する場合、このキーの値は同じでなければなりません。

例: $a[1][4] == $a[2][4] であり、他のキーが一致しないため、$a[1] と $a[2] は一致します。しかし、$a[0][4] != $a[1][4] であるため、$a[0] と $a[1] は一致しません。

サブ配列の要素数は異なる場合があります。

これを行う効率的な方法はありますか？私が考えることができる唯一の方法は、O(n^2) になるネストされたループで可能な各ペアをチェックすることです。

誰かがより意味のあるタイトルのアイデアを持っている場合は、自由に編集してください。

多分コードはそれをより明確にします: (素朴な実装)

$pairs = array();
for($i = 0; $i < count($a); $i++)
    for($j = $i+1; $j < count($a); $j++)
        if(array_intersect_key($a[$i], $a[$j]) == array_intersect_assoc($a[$i], $a[$j]))
            $pairs[] = array($i, $j);

別：

$matching = array();
for($i = 0; $i < count($a); $i++)
    for($j = $i+1; $j < count($a); $j++)
        if(array_intersect_key($a[$i], $a[$j]) == array_intersect_assoc($a[$i], $a[$j]))
            list($matching[$i][], $matching[$j][]) = array($j, $i);
4

2 に答える 2

1

それを行う方法はあるかもしれませんが、一致する可能性が高いかどうか (またはデータの一般的な「一致性」) を知っているかどうかによって多少異なります。一致する数がそうでない場合よりも多い場合は、すべてが一致すると仮定して除外することから始める方がよい場合があります。

いずれにせよ、データを前処理できると思います。これがより速いかどうかはわかりません-それは本当にデータの分布に依存しますが、次のようなことを試すことから始めて、そこから作業します:

$a = array(
    array(2 => 1, 4 => 2, 9 => 3),
    array(3 => 7, 4 => 5, 7 => 3),
    array(1 => 6, 4 => 5),
    array(1 => 6, 4 => 5, 7 => 5),
    array(2 => 1, 4 => 2, 9 => 3)   
);
// 1 and 2 match, 2 and 3 match, 0 and 4 match

$keyData = array();
for ($i = 0; $i < count($a); $i++) {
    foreach($a[$i] as $k => $v) {
        if (!isset($keyData[$k])) { 
            $keyData[$k] = array();
        }
        if (!isset($keyData[$k][$v])) {
            $keyData[$k][$v] = array();   
        }
        $keyData[$k][$v][] = $i;
    }
}

$potentialMatches = array();
foreach ($keyData as $key => $values) {
    // Ignore single key/value pairs
    if (count($values) > 1) {
        foreach ($values as $value => $arrayIndices) {
            for ($i = 0; $i < count($arrayIndices); $i ++) {
                for ($j = $i + 1; $j < count($arrayIndices); $j ++) { 
                    $potentialMatches[] = array($arrayIndices[$i], $arrayIndices[$j]);
                }
            }
        }
    }
}

// You might need to do this ...
/*
foreach ($potentialMatches as &$m) {
    array_unique($m);
}
*/

$pairs = array();
foreach ($potentialMatches as $m) { 
     if(array_intersect_key($a[$m[0]], $a[$m[1]]) 
        == array_intersect_assoc($a[$m[0]], $a[$m[1]])) {
         $pairs[] = $m;
    }
}

print_r($pairs);

出力：

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 4
        )

    [1] => Array
        (
            [0] => 1
            [1] => 2
        )

    [2] => Array
        (
            [0] => 2
            [1] => 3
        )

)

編集

コメントで述べたように、キーを共有しない配列はキャッチされません。これは一致と見なされます。以下のコードはこれを行いますが、ネストされたソリューションよりも高速かどうかはわかりません (そして、大量のメモリを使用することになります)。

// New test data to cover the case I missed
$a = array(
    array(2 => 1, 4 => 2, 9 => 3),
    array(3 => 7, 4 => 5, 7 => 3),
    array(1 => 6, 4 => 5),
    array(1 => 6, 4 => 5, 7 => 5),
    array(2 => 1, 4 => 2, 9 => 3), 
    array(8 => 3)
);
// 1 and 2 match, 2 and 3 match, 0 and 4 match, 5 matches all

// First assume everything is a match, build an array of:
// indicies => array of potential matches
$potentialMatches = array_fill(0, count($a), array_keys($a));

// Build data about each key, the indicies that contain that key
// and the indicies for each value of that key
$keyData = array();
for ($i = 0; $i < count($a); $i++) {
    foreach($a[$i] as $k => $v) {
        if (!isset($keyData[$k])) { 
            $keyData[$k] = array();
        }
        if (!isset($keyData[$k][$v])) {
            $keyData[$k][$v] = array();   
        }
        $keyData[$k]['all'][] = $i;
        $keyData[$k][$v][] = $i;
    }
}

// print_r($keyData);

// Now go through the key data and eliminate indicies that 
// can't match
foreach ($keyData as $key => $values) {

    if (count($values) > 2) {  // Ignore single key/value pairs

        // Two indecies do not match if they appear in seperate value lists
        // First get the list of all indicies that have this key
        $all = array_unique($values['all']);
        unset($values['all']);

        // Now go through the value lists
        foreach ($values as $value => $arrayIndices) {

            // The indicies for this value cannot match the other 
            // indices in the system, i.e. this list
            $cantMatch = array_diff($all, $arrayIndices);

            // So remove the indicies that can't match from the potentials list            
            foreach ($arrayIndices as $index) {            
                $potentialMatches[$index] = array_diff($potentialMatches[$index], $cantMatch);    
            }
        }
    }
}

//print_r($potentialMatches);

// You said you didn't mind the output format, so that's probably enough 
// but that array contains (x,x) which is pointless and both (x,y) and (y,x)
// so we can do one final bit of processing to print it out in a nicer way

$pairs = array();
foreach ($potentialMatches as $x => $matches) { 
    foreach ($matches as $y) { 
        if ( ($x < $y) ) { 
            $pairs[] = array($x, $y);
        }
    }
}

print_r($pairs);

出力

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 4
        )

    [1] => Array
        (
            [0] => 0
            [1] => 5
        )

    [2] => Array
        (
            [0] => 1
            [1] => 2
        )

    [3] => Array
        (
            [0] => 1
            [1] => 5
        )

    [4] => Array
        (
            [0] => 2
            [1] => 3
        )

    [5] => Array
        (
            [0] => 2
            [1] => 5
        )

    [6] => Array
        (
            [0] => 3
            [1] => 5
        )

    [7] => Array
        (
            [0] => 4
            [1] => 5
        )

)
于 2013-09-04T13:13:55.637 に答える