У меня есть набор пар идентификаторов, таких как
(123;1765)
(1212;8977)...
Мне нужно разделить эти пары на n групп с индивидуальным размером (количеством пар) в каждой. Эти наборы должны иметь минимальное количество элементов (= в каждой группе должно быть как можно меньше разных идентификаторов). Существуют ли какие-либо существующие алгоритмы, решающие эту проблему? Не знаю где/как искать. Это необходимо, потому что в настоящее время я работаю над балансировкой нагрузки одного из своих проектов, и каждый узел должен загружать как можно меньше идентификаторов из-за ограниченного объема оперативной памяти (каждый идентификатор подключен к большему набору данных).
Изменить:
Немного предыстории: разные узлы в кластере должны сравнивать наборы данных, идентифицированные идентификаторами. Каждое сравнение представляет собой пару идентификаторов (сравните набор данных ID1 с ID2). Каждый узел получает набор пар, чтобы узнать, какие идентификаторы он должен сравнивать, и загружает соответствующие наборы данных в ОЗУ. Главный узел делит большую группу пар на более мелкие группы и распределяет их по подчиненным узлам. Поскольку каждый узел может хранить только ограниченное количество наборов данных, эти меньшие группы должны содержать как можно меньше разных идентификаторов. Но узлы имеют разный объем оперативной памяти, поэтому группы с минимальной кардинальностью должны иметь разный размер. Сравнение является симметричным, поэтому сравнение (ID1, ID2) совпадает с сравнением (ID2, ID1), поэтому каждая пара уникальна. Какие наборы данных необходимо сравнивать, определяет клиент, который отправляет эти задания мастеру в виде набора пар идентификаторов.
Пример: клиент хочет сравнить набор данных (1;2), (7;9), (9;105), (7;105), (2;4), (4;1) (обычно здесь должно быть намного больше сравнений, поэтому обычно миллионы) Клиент отправляет эти пары мастеру, у которого есть два зарегистрированных ведомых. Теперь мастеру нужно разделить этот стек работы на две группы, но чем больше разных идентификаторов входит в каждую группу, тем больше наборов данных нужно загрузить подчиненным (ID соответствует конкретному набору данных, помните?).
Таким образом, в идеале мастер должен создать группу вроде ((1;2), (2;4), (4;1)) (содержит только 3 разных идентификатора, поэтому подчиненному устройству нужно загрузить только 3 набора данных) и ((7;9), (9;105), (7; 105)) (опять же только три идентификатора) вместо: ((1;2), (9;105)...) и ((2;4), (7;105)...). Здесь обоим подчиненным необходимо загрузить 4 идентификатора и более, и, например. обоим ведомым устройствам необходимо загрузить наборы данных нет. 2 и 105. Это надо как-то оптимизировать..
