Как получить наиболее однородные результаты разделения?

Question

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

Например: У меня есть набор данных должен быть разделен на две части:

key num_of_records 
k1 20 
k2 15 
k3 2 
k4 3 
k5 5 

Есть 2^5 видов разных перегородок. такие как

part1: k1 k3 k4 (total records: 25) 
part2: k2 k5 (total records 20) 

И еще один раздел является:

part1: k1 k4 (total records 23) 
part2: k2 k3 k5 (total revords 22) 

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

Итак, мне нужен algrithm, чтобы найти оптимальный раздел.

Может ли кто-нибудь дать мне несколько предложений по этой теме? Как я могу подойти к этой проблеме?

Спасибо.

Answer 1

Java-метод по умолчанию hashCode() подходит для этого. Очевидно, что с размером выборки 45 вы можете получить разницу в несколько, но при больших масштабах данных это не имеет значения и будет стремиться к равномерному распределению.

Answer 2

Если у вас есть какие-либо предварительные сведения о ожидаемой мощности для каждого ключа (на основе исторических результатов или чего-то еще), лучше придерживаться «случайной» схемы разбиения, такой как по умолчанию (на основе хэш-кода объекта) - - как указано в ответе @ benwatsondata.

Однако, если вы работаете с очень небольшим набором ключей (например, стран или континентов) и огромными различиями в мощности между ними (скажем, у вас есть миллионы ценностей для Европы или Северной Америки и только тысячи для Южной Америки), вам нужно придумать разделитель, основанный на ключевом «рейтинге».

Как простой пример, вы можете иметь разделитель, который просто сопоставляет каждый из ваших ключей с разделом и возвращается к значению hashcode по умолчанию для неизвестных ключей. Отображение настроенное для 3 восстановителей будет:

Europe -> P1 
North America -> P2 
Asia -> P3 
South America -> P3 
Australia -> P2 
Africa -> P1 
__default__ -> hashCode-based 

Умнее версия выше будет получить как количество переходников и ранжированный список в качестве параметров, и он будет выяснить сам оптимальную схему разделения.