![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonА вот задачка, может кто подскажет, как такие решаются.
Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы - 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное - 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы - 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное - 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-02-27 01:48 pm (UTC)Метрическое дерево предназначено для поиска ближайшего соседа.
Даёшь элемент метрического пространства, оно быстро отыскивает ближайший или N ближайших по этой метрики.
Построение дерева — NlogN, поиск — logN.
Поиск K ближайших соседей — logN + K.
Есть B-подобная вариация (видел про это статью от того самого тов. Брина).
Ещё такое реализуется внутри постгреса (GiST).
http://en.wikipedia.org/wiki/Metric_tree
Позволит относительно несложно выбирать группки достаточно похожих множеств.
Взял элемент и выбрал по какому-то признаку похожие с ним. Хоть бы и тупо всё в таком-то радиусе. С остатком поступил как-то так же.
Можно и просто идти от корня дерева и компрессировать, добавляя диффы.