php - 配列内の行をマスクの配列に一致させる方法は?

Question

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

array('1224*', '543*', '321*' ...)これには、約 17,00 の「マスク」またはプレフィックスが含まれています。

私は2番目の配列を持っています:

array('123456789', '123456788', '987654321' ....)約 250,000 の数字が含まれています。

では、マスク/プレフィックスの配列を使用して、2 番目の配列のすべての数値を効率的に一致させるにはどうすればよいでしょうか?

[編集]

最初の配列には接頭辞のみが含まれ、すべてのエントリの最後には 1 つのみが含まれます*。

Answer 1

さて、ここに解決策があります：

準備手順:

1. 配列 1 を並べ替え、 を切り捨て*ます。

検索中:

1. 配列 2 の各数値について、
   1. number最初の文字が(二分探索)の文字と一致する、配列 1 の最初と最後のエントリを検索します。
   2. 2 番目の文字についても同じことを行います。今回は、配列全体ではなく、 と の間firstを検索しlastます (バイナリ検索)。
   3. 文字列が見つかるまで、n 番目の文字に対して 2 を繰り返します。

これはO(k*n*log(n))、n数値の平均長 (桁数) とk数値の数です。

---

基本的に、これは 1 次元の基数ツリーです。最適なパフォーマンスを得るには実装する必要がありますが、非常に難しい場合があります。

Answer 2

私の2セント....

$s = array('1234*', '543*', '321*');
$f = array('123456789', '123456788', '987654321');

foreach ($f as $haystack) {
    echo $haystack."<br>";
    foreach ($s as $needle) {
        $needle = str_replace("*","",$needle);
        echo $haystack "- ".$needle.": ".startsWith($haystack, $needle)."<br>";
    }
}

function startsWith($haystack, $needle) {
    $length = strlen($needle);
    return (substr($haystack, 0, $length) === $needle);
}

パフォーマンスを向上させるには、最初に両方の配列をソートし、内側のforeachループに終了句を追加することをお勧めします。

ちなみに、startWith関数は SO のこの素晴らしいソリューションからのものです: PHP の startsWith() および endWith() 関数

Answer 3

別のオプションは、ループで preg_grep を使用することです。

$masks = array('1224*', '543*', '321*' ...);
$data = array('123456789', '123456788', '987654321' ....);

$matches = array();
foreach($masks as $mask) {
    $mask = substr($mask, 0, strlen($masks) - 2); // strip off trailing *
    $matches[$mask] = preg_grep("/^$mask/", $data);
}

これがどれほど効率的かはわかりませんが、代替手段として提供するだけです。

Answer 4

PHP 関数 array_intersect_key を確認してください。