![[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 гига памяти и час процессорного времени.
no subject
Date: 2014-02-27 12:50 pm (UTC)sample data будет?
no subject
Date: 2014-02-27 01:19 pm (UTC)no subject
Date: 2014-02-27 01:21 pm (UTC)no subject
Date: 2014-02-27 02:37 pm (UTC)http://stuff.thedeemon.com/lj/sample.json.gz