php - 如何将数组中的行与掩码数组匹配？

Question

我有这样的数组：

array('1224*', '543*', '321*' ...)其中包含大约 17,00 个“掩码”或前缀。

我有第二个数组：

array('123456789', '123456788', '987654321' ....)其中包含大约 250,000 个数字。

现在，如何使用掩码/前缀数组有效地匹配第二个数组中的每个数字？

[编辑]

第一个数组只包含前缀，每个条目最后只有一个*。

Answer 1

好吧，这是一个解决方案：

初步步骤：

1. 对数组 1 进行排序，切断*'s。

搜索：

1. 对于数组 2 中的每个数字
   1. 在数组 1 中查找第一个和最后一个条目，其中第一个字符与number（二分查找）的字符匹配。
   2. 对第二个字符做同样的事情，这次不是搜索整个数组，而是在firstand之间last（二分搜索）。
   3. 对第 n 个字符重复 2，直到找到一个字符串。

这应该O(k*n*log(n))是n平均数字长度（以数字为单位）和k数字的数量。

---

基本上这是一维基数树，为了获得最佳性能，您应该实现它，但它可能非常困难。

Answer 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-function 来自 SO 中的这个很棒的解决方案：PHP 中的 startsWith() 和 endsWith() 函数

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

尽管正则表达式并不以快速而闻名，但我想知道preg_grep()如果将模式归结为最精简的形式并且只调用一次（而不是在循环中），它的性能如何。

通过去除被较短掩模覆盖的较长掩模，图案将大大减少。会减少多少？当然，我不能肯定地说，但有 17,000 个口罩，肯定会有相当数量的冗余。

代码：（演示）

$masks = ['1224*', '543*', '321*', '12245*', '5*', '122488*'];
sort($masks);
$needle = rtrim(array_shift($masks), '*');
$keep[] = $needle;
foreach ($masks as $mask) {
    if (strpos($mask, $needle) !== 0) {
        $needle = rtrim($mask, '*');
        $keep[] = $needle;
    }
}
// now $keep only contains: ['1224', '321', '5']

$numbers = ['122456789', '123456788', '321876543234567', '55555555555555555', '987654321'];

var_export(
    preg_grep('~^(?:' . implode('|', $keep) . ')~', $numbers)
);

输出：

array (
  0 => '122456789',
  2 => '321876543234567',
  3 => '55555555555555555',
)

Answer 5

查看 PHP 函数 array_intersect_key。