配列内容の比較

質問

例えば10個の配列がある場合、すべての配列内容をそれぞれ比較したい場合、どのようにプログラムすればよろしいのでしょうか？

二個を例に出します。
（1,2,3,4)と（3,4,5,6)で共通要素を吐き出すと（3,4)。このような配列が10個ある場合です。

数学的には10！/２！回比較する必要があるようですが、プログラムでもっと簡単に設計できればと思います。

できればphpでアドバイスお願いしたいのですが、無理でしたら他の言語でも大丈夫です。

回答No.4

noname#244856 · ベストアンサー

【テストコード】

全角スペースでインデントしています

<?php

$arrays = array(
　　range(1, 20000),
　　range(15000, 30000),
　　range(28000, 60000),
　　range(10000, 200000)
);

function fast_array_intersect() {
　　if (func_num_args() < 2) {
　　　　return false;
　　}
　　$arrays = func_get_args();
　　$base = array_shift($arrays);
　　foreach ($arrays as $arr) {
　　　　$arr = array_flip($arr);
　　　　foreach ($base as $key => $value) {
　　　　　　if (!isset($arr[$value])) {
　　　　　　　　unset($base[$key]);
　　　　　　}
　　　　}
　　}
　　return $base;
}

function fast_array_diff() {
　　if (func_num_args() < 2) {
　　　　return false;
　　}
　　$arrays = func_get_args();
　　$base = array_shift($arrays);
　　foreach ($arrays as $arr) {
　　　　$arr = array_flip($arr);
　　　　foreach ($base as $key => $value) {
　　　　　　if (isset($arr[$value])) {
　　　　　　　　unset($base[$key]);
　　　　　　}
　　　　}
　　}
　　return $base;
}

$t1 = microtime(true);
$r1 = call_user_func_array('array_intersect', $arrays);
$t2 = microtime(true);
$r2 = call_user_func_array('array_diff', $arrays);
$t3 = microtime(true);
$r3 = call_user_func_array('fast_array_intersect', $arrays);
$t4 = microtime(true);
$r4 = call_user_func_array('fast_array_diff', $arrays);
$t5 = microtime(true);

echo
　　$r1 === $r3 && $r2 === $r4 ? "OK<br />\n" : "NG<br />\n",
　　sprintf("array_intersect: %f sec<br />\n", $t2 - $t1),
　　sprintf("array_diff: %f sec<br />\n", $t3 - $t2),
　　sprintf("fast_array_intersect: %f sec<br />\n", $t4 - $t3),
　　sprintf("fast_array_diff: %f sec<br />\n", $t5 - $t4)
;

【実行結果】

OK
array_intersect: 2.422139 sec
array_diff: 2.517144 sec
fast_array_intersect: 0.060003 sec
fast_array_diff: 0.062004 sec

4個で試してみましたが、やっぱりarray_flip+issetの方が速いみたいです。$arraysの取り方によって差が出てきそうな気はしますが・・・

回答No.3

noname#244856

少し訂正します。基本的にはC言語レベル実装の方が実行が速いのですが、array_intersect/array_diffなどの関数に関しては、一部の例外があるようです。少し制約はありますが、array_flip+issetが最速のようです。
http://www.php.net/manual/ja/function.array-diff.php#107928

今回のように3個以上を比較する際はそのまま関数を利用したほうが速そうな気はしますが・・・もし気になるならばご自分で試されてみることをオススメします。

回答No.2

noname#244856

$arr0, $arr1, ..., $arr9 まで10個ある場合

array_intersect($arr0, $arr1, ..., $arr9)

で取れます。また、

$arrays[0], $arrays[1], ..., $arrays[9]

のように配列の配列でセットされている場合は、2個以上セットされていることを確認した上で

call_user_func_array('array_intersect', $arrays)

で取れます。これらはPHP内部でC言語レベルで実装されているものを利用するので、自前でPHPのコードにて設計するよりもはるかに高速です。

マニュアル
http://php.net/manual/ja/function.array-intersect.php
http://php.net/manual/ja/function.call-user-func-array.php

回答No.1

maiko0318

プログラムで簡単に設計すると、個数nに対してn^2の比較が必要です。（バブルソート）
ロジック的に工夫すると、比較回数がグッと減ります。（シェルソート）

すでにこの分野はロジックを教える教材になっており、実際にプログラムすることは少なくなっています。

配列の要素と比較条件をセットすればソートできるようになっています。

お礼

ありがとうございます。参考にさせていただきます。