Быстрый фильтр массива по отношению к другому

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]
    ]

Записи B, содержащие некоторое значение A, равны 2 и 4. Поэтому функция, которую я бы сделал, должна быть:

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

Теперь с помощью грубой петли, циклически повторяющей записи B, сложность будет O(nm), где n - это #B, а m - это размер самой длинной строки в B. Есть более умные решения?

Answer 1

Edit # 2:

Перемещая все значения для сравнения с ключевыми позициями, php может более чем удвоить эффективность (по метрике системного времени моего демо).

Кроме того, если у вас естьповторяющиеся значения в ваших подмножествах, вызов array_flip() уменьшит размер, запретив дублирующиеся ключи.

Код: ( Демо )

$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/

Рассмотрим эту подготовку ...

Код: ( Демо )

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 в качестве новых значений подмассивов.
• array_intersect_key() проверяет ключи, которые php делает намного быстрее, чем проверка значений.(см. первую статью с гиперссылками)
• Затем array_merge(...) объединяет подмассивы в один массив размером 1 дим.
• Наконец, array_flip() и array_keys() удаляют дубликаты и повторно индексируют результаты.

---

Я не знаю точно, как array_intersect() использует свое волшебство с точки зрения эффективности, но, вероятно, я бы так и поступил:

Код:( Демонстрация )

$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,
)

---

Полагаю, что при использовании * 1059 есть "обратная сторона", это будетон потрудится сделать несколько совпадений, когда требуется только одно совпадение на строку.По этой причине цикл array_search() или break может иметь преимущества.

Код: ( Демо )

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