Здравствуйте, avpavlov, Вы писали:
A>>> for (int j=0; j<base.fullMap.length && mergedLength <= stopAtLength; j++) { A>>> mergedLength += Long.bitCount(base.fullMap[j]|other.fullMap[j]); A>>Это место можно ещё улучшить, если сначала проверять бит в quickMap, что там не нули, это позволит пропускать 16 элементов массива без проверки. A>Что ускоряет ещё в 3 раза (ну почти )
Учитывая, что большинство множеств в этом наборе имеют менее 5 элементов и они уже отсортированы, этот цикл можно выбросить и сделать просто один проход по паре множеств (a-ля mergesort).
Но ведь это только начало. Одна такая итерация покажет, какие у множеств есть "похожие". Но если есть десяток множеств, попарно похожих друг на друга, мы не можем объединить их все в одно, надо еще выбрать какие из них объединять.
Вот за демонстрацию того, что сравнение границ и уменьшенных битсетов позволяет так сильно ускорить перебор, спасибо. Обнадеживает.
Здравствуйте, D. Mon, Вы писали:
DM>Здравствуйте, Аноним, Вы писали:
А>>Я бы сначала определил меру похожести множеств, а затем какой алгоритм кластеризации (их море и разных) заюзал. А после, как по кластерам распихалось, уже объединял бы в кластерах.
DM>А при этом можно обойтись без вычисления этой меры для всех пар множеств? А то это уже больно много операций получается.
LSH идеально подойдет для такой задачи, можете воспользуоваться уже существующими реализациями.
Просто большую часть множеств небольшого размера сравниваете с помощью хешей , LSH не гарантирует попадания , но статистически дает очень хороший результат на поиск похожих соседей.
Остается только подумать как организовывать множества на вход (отсортировывать, заполнять нулями те что не дотянули по размеру и т.д.)
Здравствуйте, D. Mon, Вы писали:
DM>Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
Какой подход в итоге выбрал? Удалось получить желаемый результат?
Здравствуйте, Kernan, Вы писали:
K>Какой подход в итоге выбрал? Удалось получить желаемый результат?
Благодаря подсказанным avpavlov оптимизациям (сделал для каждого множества min, max и миникарту из 128 бит, с их помощью быстро отсекал заведомо непересекающиеся множества), получилось сравнить попарно все потенциально пересекающиеся мн-ва. При каждом сравнении вычислялась оценка выигрыша от возможного объединения, для каждого мн-ва запоминались до 100 лучших вариантов. Получился ориентированный граф из 65к вершин и до 100 граней из каждой вершины, который, с учетом симметрии оценочной функции, потом превращался в неориентированный с до 200 граней на вершину, у каждой грани свой "вес" — оценка выигрыша от объединения. В этом графе жадным образом (навроде градиентного спуска) искались самые выгодные грани (не соприкасающиеся), и множества на их концах объединялись. Потом весь процесс повторялся, пока не устаканится: с каждой итерацией число таких пар множеств, которые выгодно объединить, быстро падало. Итераций потребовалось всего несколько штук, все посчиталось довольно быстро (точно не помню, но заметно меньше часа).
)
