В настоящее время мне поручено реализовать алгоритм CCL в системе баз данных (написан на C++). Этот алгоритм назначил метку всем значениям заданного многомерного массива, которые превышают пороговое значение, а соседние помеченные значения будут иметь одну и ту же метку.
Кодирование базового алгоритма CCL не было затруднительным, но в моем домене входной массив случайным образом разбивается на несколько экземпляров базы данных. Когда вызывается мой оператор CCL, каждый экземпляр выполняет операцию над куском данных, за которые отвечает и возвращает свой локальный результат CCL. Эти локальные результаты затем объединяются для получения конечного результата.
Во время выполнения я не знаю, какой экземпляр отвечает за любую данную часть массива, а экземпляры не могут связываться друг с другом до последнего шага слияния.
- = - = - = -
В настоящее время я работаю, выполняя следующие действия:
Каждый экземпляр создает массив логических значений размера, равного количеству элементов в массиве, и устанавливает все значения в FALSE.
Каждый экземпляр проходит через значения, за которые он отвечает, и проверяет, находятся ли эти значения выше порогового значения; если они есть, они меняют соответствующие логические значения в их локальном массиве на TRUE.
Все экземпляры отправляют свои массивы координатору, который объединяет результаты с использованием OR для создания конечного булева вектора.
Координатор проходит через каждое значение в массиве, пропуская значения, которые уже помечены. Если значение не помечено, а логическое значение, соответствующее этому значению, истинно, оно присваивает ему новую метку и рекурсивно присваивает всем своим соседям (и соседям соседи и т.д.) Одну и ту же метку.
Возвращается вектор меток.
Вышеупомянутый алгоритм работает, но единственное, что использует множественные экземпляры, - это пороговые вычисления. Поскольку эта реализация просто собирает все и проверяет ее на координаторе, она скорее поражает точку использования нескольких экземпляров в первую очередь.
- = - = - = -
По сути, этот алгоритм автоматически превращается в алгоритм "разделяй и властвуй", но деления полностью и неконтролируемо случайны.
Мы хотим воспользоваться этим разделением, выполнив как развертки CCL для каждого экземпляра, так и объединив эти локальные результаты CCL у координатора; то есть, если два экземпляра создают группы ярлыков, которые соседствуют друг с другом, мы хотим объединить эти две метки без повторного сканирования каждого значения. Этот курсивный момент - это то, что дает нам наибольшую проблему, и мы скорее теряемся в том, как действовать дальше. Если у кого-то есть предложения либо для алгоритмов, либо для структуры данных, которые были бы хороши для изучения, это было бы высоко оценено.
Соединительные компоненты (в отличие от связанных с графом компонентов) требуют проверки набора всех пар соседних (смежных пикселей).
То есть,
{ ((x1, y1), (x2, y2)) }
для которых (abs(x2 - x1) + abs(y2 - y1)) <= 1
и (x1 != x2 && y1 != y2)
max(abs(x2 - x1), abs(y2 - y1)) <= 1
и (x1 != x2 && y1 != y2)
Следующий шаг понимания требует знания отношения эквивалентности. Примечательно, что он должен удовлетворять:
От этих трех требований есть интересное:
Следует принять во внимание, что интерфейс алгоритма "Disjoint-Set", который будет обсуждаться ниже, является в точности списком отношений эквивалентности. Таким образом, можно обрабатывать этот список отношений эквивалентности по-разному и все равно получить тот же результат.
Чтобы представить и описать алгоритмы, которые вычисляют и обрабатывают связанные компоненты, следует изучить Disjoint-Set.
Нужно изучить фактическую реализацию Disjoint-Set, а также узнать, как он фактически используется (вызывается) из алгоритма связанных компонентов.
После этого следует поднять уровень понимания абстракции - абстрактную концепцию (интерфейс алгоритма) Disjoint-Set. Изучив эту абстракцию, вы сможете нереализовать Disjoint-Set необычными способами.
Union
.Find
используется только внутри функции " Union
.Union( (x1, y1), (x2, y2) )
.Union
, потому что не будет проверки того, являются ли два узла уже одной и той же меткой перед вызовом очереди. Этот вопрос будет рассмотрен в следующей части. Теперь мы представим способ планирования этих сообщений Union
для обработки.
Предположим, что узлы распределены на разные машины.
{ ((x1, y1), (x2, y2)) }
следующим образом: Чтобы обрабатывать Union-Find на разных машинах, один просто * Генерирует сообщения Union
из набора одинаковых пар пар соседних пикселей * Затем фильтруйте сообщения Union
для удаления избыточных. * Генерирует сообщения Union
из набора пар разных пар соседних пикселей. * Выполнять сообщения разных машин по результатам сообщений с одинаковой машиной.
Этот ответ написан чрезмерно абстрактным образом, потому что более конкретный ответ потребует более подробной информации о проблеме, особенно о "полностью и неуправляемо случайном разбиении".