множества

[thedeemon]

А вот задачка, может кто подскажет, как такие решаются.
Есть набор из 65000 множеств, в каждом множестве от 1 до 35000 элементов (элементы - 16-битные целые числа), причем распределение размеров весьма неравномерное: среднее число элементов около 50, медианное - 13, т.е. большая часть множеств имеет менее 20 элементов, но есть и содержащие десятки тысяч. Мне нужно уменьшить этот набор путем объединения "похожих" множеств так, чтобы минимизировать сумму размеров множеств, но с таким ограничением: объединение множеств A,В,С... в некое Х возможно лишь тогда, когда размер получающегося Х не более чем в К раз (скажем, К=4) больше, чем размер каждого из А,В,С... Т.е., например, нельзя объединять множество из 10 элементов с множеством из 100. Объединять непересекающиеся множества нет смысла, а чем сильнее множества пересекаются ("похожи"), тем выгоднее их объединить.

Самое оптимальное решение не требуется, можно предлагать эвристики. Наивные переборные решения многовато операций и/или памяти требуют. Желательно уложиться в 2 гига памяти и час процессорного времени.

Comments

[nivanych.livejournal.com]

Функция "похожести" множеств (или величина "невкусности" операции объединения) может быть сделана метрикой?
Если метрика, то можно сделать метрическое дерево.

[thedeemon.livejournal.com]

Ну вот d(A,B) = |A ⊖ B| = |A ∪ B - A ∩ B| вроде бы метрика. Как будет выглядеть такое дерево, что оно даст и сколько стоит его построение?

[nivanych.livejournal.com]

Видимо, ещё надо учитывать размер множеств — сильно разные размеры должны ещё дополнительно расстояния добавлять.
Метрическое дерево предназначено для поиска ближайшего соседа.
Даёшь элемент метрического пространства, оно быстро отыскивает ближайший или N ближайших по этой метрики.
Построение дерева — NlogN, поиск — logN.
Поиск K ближайших соседей — logN + K.
Есть B-подобная вариация (видел про это статью от того самого тов. Брина).
Ещё такое реализуется внутри постгреса (GiST).
http://en.wikipedia.org/wiki/Metric_tree
Позволит относительно несложно выбирать группки достаточно похожих множеств.
Взял элемент и выбрал по какому-то признаку похожие с ним. Хоть бы и тупо всё в таком-то радиусе. С остатком поступил как-то так же.
Можно и просто идти от корня дерева и компрессировать, добавляя диффы.

[wizzard]

крайне любопытная задача, да

sample data будет?

[sorhed.livejournal.com]

Можно сгенерировать в три секунды. Генерируешь число в power-law distribution, t = 1 / (random(0..1)^(1/α)) (альфу подобрать по вкусу), это будет размер множества. Заполняешь его случайными числами, можно тоже в power-law, чтобы было много похожих. Должно работать.

[wizzard]

Резонно, хотя не уверен что именно оно

[thedeemon.livejournal.com]

Вот прореженные в 8 раз данные:
http://stuff.thedeemon.com/lj/sample.json.gz

[wizzard]

так, а если мы обьединяем A,B,C в D, а потом D и E в F - то размер F все равно не может быть более K*min(|A|,|B|,|C|,|E|)?

[thedeemon.livejournal.com]

Да, именно так.

[os80.livejournal.com]

А какой "физический смысл" задачи? Я не математик и не понимаю, как можно решать эту (нечётко поставленную) задачу, не понимая цели?

[thedeemon.livejournal.com]

В общих чертах: есть множество сменяющих друг друга состояний, в которых возможны разные множества событий. Когда в некотором состоянии какое-то событие происходит первый раз, это "дорого", а если оно в этом состоянии уже происходило раньше, это "дешевле", причем чем меньше множество возможных событий в этом состоянии, тем "дешевле". Хочется объединить некоторые состояния, тем самым уменьшив число случаев, когда событие происходит впервые.

Подробнее не могу вдаваться, это секретный проект для ВМФ Монголии. :)

[wizzard]

Context mixing, поди

simhash ftr

[ygrek (from livejournal.com)]

По описанию попадает под область применения simhash

[sleepy-drago.livejournal.com]

интересно, но когда мозг задолбан овертаймами нечеткие условия почему-то плохо воспринимаются. примеры, требования ... хоть что-нибудь =)
а то пузомерки из этого в нынешнем виде не выйдет, а алгоритм разрабатывать слишком неблагодарное дело

[thedeemon.livejournal.com]

Пример 1:
На входе набор множеств 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, например.

[sleepy-drago.livejournal.com]

первые впечатления 0)поглотить все подмножества. Дальше локальный критерий который выбирает пару текущих на объединение. Ограничение (K) заданное на исходные выглядит весьма произвольно и таким образом может создавать локальные минимумы ... Надо бы тренироваться на кошках чтобы понять. Правда сейчас после пары месяцев овертаймов нам разрешили побыть дома и это явно не один день =)
В сторону в очередной раз скачал golang и его парсер json мне пожаловался на последнюю запятую. Рукалицо. К тому же они не могут разобрать неполный объект и когда весь датасет это один объект ... =)

[swizard.livejournal.com]

Если работа одноразовая, я бы, всё же, попробовал начать с брутфорса. 2014-ый год на дворе, 65k * 65k * 50 -- это всего порядка 200 млрд достаточно простых действий, современный компьютер за час вполне должен прожевать на четырёх ядрах. Опять же, есть видеокарта :)

[thedeemon.livejournal.com]

> 200 млрд достаточно простых действий

Это только на одну итерацию, коих может потребоваться множество. Что именно даст один проход по всем парам?

Но вообще, как мне на рсдн продемонстрировали, пара простых приемов этот перебор могут очень заметно ускорить, так что вероятно он будет задействован.