重複した配列の抽出

Question

2つの文字列の組み合わせが複数あり、その中から重複しているもののみを抽出しようとしています。
組合せ順も同一のもののみを抽出します。

$target = array(array('100', '200'), array('100', '300'), 
                    array('200', '200'), array('100', '200'));
$checked = array();    // 確認済み組合せ
$overlapped = array(); // 重複した組合せ
foreach ($target as $data){
    if (!in_array($data, $checked)){
        $checked[] = $data;
    } else{
        $overlapped[] = $data;
    }
}
// 重複した組合せを一意にする
$overlapped = array_unique($overlapped, SORT_REGULAR);
// Array([0] => Array([0] => '100', [1] => '200'))

この書き方で順番も含む重複組合せの抽出自体は可能なことは確認したのですが、現在作成中の処理では、場合によっては100回以上、上記処理を実行する場合があります。
1回に比較する配列の組み合わせは多くて5つ程度なので単体でみれば速度は気にならないのですが、実行回数が増えた場合の速度が気になっています。

上記の書き方以外で、速度改善が見込める書き方はありますでしょうか。
発想力がなく、これ以外は思いつかなかった次第です。

皆様のご意見を頂けると嬉しいです。

Answer 1

$target = array(
        array('100', '200'),
        array('100', '300'),
        array('200', '200'),
        array('100', '200')
    );

$target_unique = array_unique($target);

/* 
 * $tatgetと$target_uniqueの差分の配列を求める
 * （重複していない要素はこれで除去されるはず・・・）
 */
/* 
 * 差分配列のarray_uniqueを求める
 * （unique値を差し引いても残った要素は、つまり重複していた要素なので・・・）
 */

これでいかがでしょうか？

Answer 2

既に解決済みのうえ、具体的な回答ではありませんが、、

---

実行するマシンの性能にもよりますが、

場合によっては100回以上

（中略）
1回に比較する配列の組み合わせは多くて5つ程度

であれば、気になるほど遅くなるようなことはないはずです。

ロブ・パイク曰く

ルール1: （中略）どこがボトルネックなのかをはっきりさせるまでは、推測を行ったり、スピードハックをしてはならない。

ルール2: 計測すべし。計測するまでは速度のための調整をしてはならない。コードの一部が残りを圧倒しないのであれば、なおさらである。

というわけで、以下のようなテストコードを書いて、実際、ご自分のコードがどの程度の速度で動くのか、確認してみてください。

<?
define('COUNT_OF_TARGET', 5); // $target の要素数
define('NUMBER_OF_TEST', 100); // 試行する回数

// 配列の組み合わせを乱数で生成
for($i = 0; $i < COUNT_OF_TARGET; $i++) {
    $target[] = array((string) mt_rand(0, 300), (string) mt_rand(0, 300));
}

$before = microtime(true);

for ($i = 0; $i < NUMBER_OF_TEST; $i++) {
    $overlapped = extractDuplicate($target);
}
echo (microtime(true) - $before) . "\n";

/**
 * 引数 $target から、重複した要素を抜き出す。
 */
function extractDuplicate(array $target) {
    $checked = array();    // 確認済み組合せ
    $overlapped = array(); // 重複した組合せ
    foreach ($target as $data){
        if (!in_array($data, $checked)){
            $checked[] = $data;
        } else{
            $overlapped[] = $data;
        }
    }
    // 重複した組合せを一意にする
    return array_unique($overlapped, SORT_REGULAR);
}

私の環境（※）では、0.0004秒程度でした。

ただし、$targetの要素数（上記コードのCOUNT_OF_TARGET）が大きなオーダーを持っているようで、
COUNT_OF_TARGETが 500 に近づく辺りから 1秒以上かかるようになりました。

※ Mac OSX v10.9, 1.7GHz Intel Core i7, 8GB mem

Answer 3

大量の場合ハッシュの方が早いかな。

<?php
$target = array(array('100', '200'), array('100', '300'),
                array('200', '200'), array('100', '200'));
$checkey = array();    // ハッシュKEY
$checked = array();    // 確認済み組合せ
$overlapped = array(); // 重複した組合せ
foreach ($target as $data){
    if (!array_key_exists(implode("",$data), $checkey)){
        $checkey[implode("",$data)] ="";
        $checked[] = $data;
    } else{
        $overlapped[] = $data;
    }
}
// 重複した組合せを一意にする
$overlapped = array_unique($overlapped, SORT_REGULAR);
// Array([0] => Array([0] => '100', [1] => '200'))

追伸、もし桁数が異なる場合は、デルミッタをセットしてください。implode("@",$data)

Comments

[tropfen]

ご回答ありがとうございます。

ハッシュを利用した書き方はほとんどしたことがなかったので勉強になります。
参考にさせていただきます。

Answer 4

同じ内容の配列が3つ以上あった場合どうするのでしょうか？

$target = [
  ['100', '200'],
  ['100', '300'],
  ['200', '200'],
  ['100', '200'],
  ['100', '200'],
  ];

Comments

[tropfen]

最終的には重複があった組合せの一覧（重複回数は問わない）を取得したいので、記載したコードでは「array_unique」を最後に実行しています。
ご記載いただいたパターンでも、質問に記載したコードの最後にコメントを入れている状態を目指しています。