![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
множества
А вот задачка, может кто подскажет, как такие решаются.
Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы - 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное - 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы - 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное - 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.
Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.
no subject
Если метрика, то можно сделать метрическое дерево.
no subject
no subject
Метрическое дерево предназначено для поиска ближайшего соседа.
Даёшь элемент метрического пространства, оно быстро отыскивает ближайший или N ближайших по этой метрики.
Построение дерева — NlogN, поиск — logN.
Поиск K ближайших соседей — logN + K.
Есть B-подобная вариация (видел про это статью от того самого тов. Брина).
Ещё такое реализуется внутри постгреса (GiST).
http://en.wikipedia.org/wiki/Metric_tree
Позволит относительно несложно выбирать группки достаточно похожих множеств.
Взял элемент и выбрал по какому-то признаку похожие с ним. Хоть бы и тупо всё в таком-то радиусе. С остатком поступил как-то так же.
Можно и просто идти от корня дерева и компрессировать, добавляя диффы.
no subject
sample data будет?
no subject
no subject
no subject
http://stuff.thedeemon.com/lj/sample.json.gz
no subject
no subject
no subject
no subject
Подробнее не могу вдаваться, это секретный проект для ВМФ Монголии. :)
no subject
simhash ftr
no subject
а то пузомерки из этого в нынешнем виде не выйдет, а алгоритм разрабатывать слишком неблагодарное дело
no subject
На входе набор множеств A=[1,2,3], B=[1,3,5], C=[4]. Параметр К=4.
На выходе набор А'=[1,2,3,5], C=[4] и указание, что A'=A+B.
Пример 2:
http://stuff.thedeemon.com/lj/sample.json.gz
Требование: сказать, какие множества объединить, чтобы в получившемся наборе множеств сумма их размеров получилась минимальной. С ограничением для К=3, например.
no subject
В сторону в очередной раз скачал golang и его парсер json мне пожаловался на последнюю запятую. Рукалицо. К тому же они не могут разобрать неполный объект и когда весь датасет это один объект ... =)
no subject
no subject
Это только на одну итерацию, коих может потребоваться множество. Что именно даст один проход по всем парам?
Но вообще, как мне на рсдн продемонстрировали, пара простых приемов этот перебор могут очень заметно ускорить, так что вероятно он будет задействован.