В настоящее время мне поручено реализовать алгоритм CCL в системе баз данных (написанной на C++). Этот алгоритм будет назначать метку всем значениям заданного многомерного массива, которые превышают пороговое значение, а соседние помеченные значения будут иметь одну и ту же метку.
Написание базового алгоритма CCL не составило труда, но в моем домене входной массив случайным образом разбивается на несколько экземпляров базы данных. Когда вызывается мой оператор CCL, каждый экземпляр выполняет операцию над блоком данных, за который он отвечает, и возвращает свой локальный результат CCL. Затем эти локальные результаты объединяются для получения окончательного результата.
Во время выполнения я не знаю, какой экземпляр отвечает за ту или иную часть массива, и экземпляры не могут взаимодействовать друг с другом до последнего шага слияния.
-=-=-=-
В настоящее время у меня это работает, делая следующее:
Каждый экземпляр создает массив логических значений размера, равного количеству элементов в массиве, и устанавливает для всех значений значение FALSE.
Каждый экземпляр просматривает значения, за которые он отвечает, и проверяет, не превышают ли эти значения пороговое значение; если это так, они изменяют соответствующее логическое значение в своем локальном массиве на TRUE.
Все экземпляры отправляют свои массивы координатору, который объединяет результаты с помощью оператора ИЛИ для создания окончательного логического вектора.
Координатор просматривает каждое значение в массиве, пропуская уже помеченные значения. Если значение не помечено и логическое значение, соответствующее этому значению, равно true, оно присваивает ему новую метку и рекурсивно присваивает всем своим соседям (и соседям соседей и т. д.) одну и ту же метку.
Возвращается вектор меток.
Алгоритм, описанный выше, работает, но единственное преимущество наличия нескольких экземпляров — это расчеты пороговых значений. Поскольку эта реализация просто собирает все и сканирует на координаторе, она, скорее, лишает смысла использование нескольких экземпляров.
-=-=-=-
По сути, этот алгоритм автоматически превращается в алгоритм «разделяй и властвуй», но деление происходит полностью и неконтролируемо случайно.
Мы хотим воспользоваться этим разделением, выполнив обе проверки CCL на каждом экземпляре, а затем объединив эти локальные результаты CCL на координаторе; то есть, если два экземпляра создают группы меток, которые соседствуют друг с другом, мы хотим объединить эти две метки без повторного сканирования каждого значения. Этот пункт, выделенный курсивом, доставляет нам больше всего проблем, и мы довольно потеряны относительно того, как продолжить. Если у кого-то есть предложения по алгоритмам или структурам данных, которые было бы полезно изучить, это было бы очень признательно.
