Доброго времени суток, уважаемые форумчане.
Вот уже довольно долго пытаюсь побороть такую проблему - максимально быстро находить кластеры для заданной системы хаотично расположенных сфер (причём система полидисперсна). Впрочем, вид системы особой роли-то не играет. Собственно, есть ряд проблем и связанных с ними вопросов.
На данный момент я использую, по сути, классический алгоритм
Хошена-Копельмана, суть которого сводится к следующему:
1. Изначально всем элементам ставится значение кластерной метки "0". Задаём
2. Затем мы начинаем методично пробегать по всем элементам. Для каждого элемента просматриваем его ближайшее окружение (потенциальные соседи могут находиться только в пределах
).
3. Если два элемента соединены и не принадлежат ни одному из кластеров, они образуют новый кластер с меткой k. После этого это увеличиваем k на единицу.
4. Если один из элементов уже принадлежит какому-либо кластеру, а другой - нет, то элемент без кластера присоединяется к кластеру другого.
5. Если же оба элемента принадлежат каким-либо кластерам, то происходит объединение кластеров.
В общем, алгоритм прост, как апельсин. При этом, что хорошо, для этого алгоритма нет необходимости изначально выделять память для кластеров, что критично, так как априорно неизвестно, сколько кластеров будет вообще и каких они будут размеров (хотя бы максимально).
А теперь о том, что плохо. Алгоритм работает медленно (в смысле недостаточно для меня быстро). Для ускорения процесса по совету, взятому
отсюда, перед перемаркировкой я начал проверять размеры систем, перемаркировка которых требуется, чтобы потом изменять поменьше значений. Практика показывает, что это ни черта не помогает, поскольку основной вклад по времени в эту операцию входит именно опознавание элементов с определённой меткой (в fortran за это отвечает, например, оператор where(...)), которая от числа опознаваемых элементов особо не зависит (по итогу даже медленнее выходит из-за проверки). В MATLAB я пытался пойти немного по-другому: сделать сначала массив ячеек под массивы (поскольку массив одномерный, то памяти должно заведомо хватать), а потом туда "засовывать" элементы. Слияние двух кластеров тогда есть просто объединение двух ячеек, что гораздо быстрее. Однако MATLAB в целом довольно медленная штука, поэтому всё равно не хватает полученной скорости.
Опять же, например,
здесь и
здесь предлагается для ускорения работать по "древовидной" схеме. То есть вместо маркировки кластерной меткой использовать систему "родитель(родитель(...(корень)))". Но вот как это реализуется и как потом это "распутывается" (чтобы в итоге иметь на руках именно что кластеры), я не совсем понимаю. Был бы очень благодарен, если бы кто-нибудь всё это дело "разжевал".
Лишний раз обращу внимание, что меня интересует именно что полное описание системы. То есть интересует, какому кластеру каждый элемент принадлежит. В принципе, достаточно было бы и знания того, какие элементы принадлежат перколяционному кластеру, но первое всё же лучше.
Короче говоря, хотелось бы узнать, как реализуется "древовидный" метод, а также возможность его распараллеливания, послушать какие-нибудь общие рекомендации по вопросу.
P.S. Кроме того, хотелось бы узнать мнение на счёт следующего вопроса. Предположим, у нас есть перколяционный кластер хаотично расположенных сфер. И пусть мы убираем одну из сфер. Пересматривать после этого весь кластер по новой, чтобы понять, "порвался" ли кластер большого желания нет. С другой стороны, как я понимаю, рассмотрения ближайшего окружения не хватит для однозначного ответа на вопрос. Да и вообще любого окружения не хватит в общем случае. В принципе, понятно, что при этом можно, исходя из рассмотрения окружения некоторого порядка (скажем, ближайшие соседи и их соседи; или разбить всё пространство на кубики размером
и в качестве окружения брать 2 ближайших клетки) выдвинуть некоторую гипотезу. Можно ли при этом как-нибудь оценить в среднем, насколько часто мы будем при этом ошибаться? Если кто-нибудь сможет подсказать по этому поводу или скинь статью, где подобный вопрос обсуждается, то я был бы безмерно благодарен.
