алгоритм алгоритма — элементы PHP быстрой кластеризации, хранящиеся в массиве
У меня есть массив, состоящий из 1,5 миллионов пар элементов (разделенных »):
$array {
[0] => "element1 element2"[1] => "element2 element3"[2] => "element8 element4"[3] => "element8 element5"[4] => "element4 element5"[5] => "element6 element7"[6] => ...
}
Каждая пара элементов уникальна, и элементы представляют собой строки длиной от 15 до 20 символов.
В моем конвейере этот массив означает [0] «element1 связан с element2», [1] «element2 связан с element3», …
Я хотел бы объединить все связанные элементы и получить вывод, похожий на:
$array_output {
[0] => "element1 element2 element3"[1] => "element8 element4 element5"[2] => "element6 element7"[3] => ...
}
Я полагаю, что это очень простое задание, и мне, вероятно, не хватает очевидного способа сделать это, но я не нашел быстрого способа кластеризации своих элементов (то есть от нескольких минут до нескольких часов).
Решение
У вас есть график, представленный в виде списка смежности, и вы хотите преобразовать его в список связанных компонентов графика. Лучший способ сделать это — создать наборы узлов, которые соединены, и объединять их для каждого ребра, пока у вас не останется ребер.
Чтобы сделать это в PHP:
- Преобразовать ваш ввод в многомерный массив (
[["element1", "element2"],["element2","element3"]]так далее.) - Инициализируйте список узлов в представлении карты, где каждый узел указывает на набор, содержащий только этот узел (например,
["element1" => ["element1"],"element2" => ["element2"]]так далее.) - Для каждой пары в массиве из (1) объедините наборы двух элементов в массиве из (2) и укажите оба элемента, а также любые другие элементы в наборе, на вновь объединенный набор
- Поместите все наборы из (3) в набор (наборов), чтобы вы получили каждый из них только один раз
- Преобразуйте каждый набор в желаемый формат вывода
Вы хотите использовать справочный оператор (&) для повторного использования тех же массивов в (3). Алгоритм было бы намного проще реализовать в Java или в чем-то еще с более очевидными хэш-картами и хеш-таблицами.
Другие решения
Других решений пока нет …