php - 阵列相对于另一个的快速过滤器

Question

假设我有一个索引数组A。假设我有一个数组 B，其中每个键都是一个包含一些索引或数字的数组。我会知道 B 中的哪些条目包含出现在 A 中的一些索引。例如(php 风格):

A = [3,45,67,8]
B = [ 1 => [1,6,81],
      2 => [5,67,3,4,5,66,6],
      3 => [55,56,57,58],
      4 => [45,80,81,82]
    ]

包含 A 的某些值的 B 的条目是 2 和 4。所以我要做的功能应该是:

function solution = filter(A,B) // solution = [2,4]

现在，用一个粗暴的循环，遍历 B 的条目，复杂度将是O(nm)，其中n是#B，m是B中最长行的大小。有更智能的解决方案吗？

Answer 1

编辑#2:

通过移动所有值与关键位置进行比较，php 可以提高一倍以上的效率(根据我的演示的系统时间指标)。

此外，如果您的子集中有重复值，调用 array_flip() 将通过禁止重复键来减小大小。

代码:(Demo)

$A = array_flip($A);  // prepare for key comparisons    
$result = [];
foreach ($B as $key => $haystack) {
    if (array_intersect_key(array_flip($haystack), $A)) {
        $result[] = $key;
    }
}
var_export($result);

---

编辑:

每当您想使用 php 优化数组搜索时，通常最好尝试以一种允许 php 利用其哈希表优势的方式准备数据。 https://codedmemes.com/lib/best-performance-array-intersection/

考虑这个准备...

代码:(Demo)

foreach ($B as $key => $haystack) {
    foreach ($haystack as $hay) {
        $C[$hay][] = $key;
    }
}

var_export(array_keys(array_flip((array_merge(...array_intersect_key($C, array_flip($A)))))));

输出:

array (
  0 => 1,
  1 => 2,
  2 => 4,
)

• 嵌套的 foreach() 循环生成子数组的集合，这些子数组具有来自 B 的子数组的唯一值作为键和 $B' s 原始键作为新的子数组值。
• array_intersect_key() 检查 php 执行的键比检查值快得多。 (见第一篇超链接文章)
• 然后 array_merge(...) 将子数组展平为单个 1-dim 数组。
• 最后 array_flip() 和 array_keys() 删除重复项并重新索引结果。

---

我不确切地知道 array_intersect() 是如何在效率方面发挥其魔力的，但这可能是我的处理方式:

代码:(Demo)

$A = [3,45,67,8];
$B = [ 1 => [1,6,8],
      2 => [5,67,3,4,5,66,6],
      3 => [55,56,57,58],
      4 => [45,80,81,82]
    ];

$result = [];
foreach ($B as $key => $haystack) {
    if (array_intersect($haystack, $A)) {  // generate an array with co-existing values
        $result[] = $key;  // add key if array_intersect makes a non-empty array
    }
}
var_export($result);

输出:

array (
  0 => 1,
  1 => 2,
  2 => 4,
)

---

我想如果使用 array_intersect() 有一个“缺点”，那就是当每行只需要一个匹配时，它会很麻烦地进行多次匹配。因此，array_search() 或 breaking 循环可能具有优势。

代码:(Demo)

$result = [];
foreach ($B as $key => $haystack) {
    foreach ($haystack as $hay) {
        if (in_array($hay, $A)) {
            $result[] = $key;
            break;
        }
    }
}
var_export($result);  // same result