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

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

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

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)

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

Итак, мне нужен алгоритм для поиска оптимального раздела.

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

Спасибо.


hadoop partition partitioning hadoop-partitioning data-partitioning
person Tim    schedule 08.02.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

person Ben Watson    schedule 08.02.2015
comment
Хотя я согласен с тем, что вы говорите, вопрос (отчасти) подразумевает, что ОП не доволен разделителем по умолчанию, поэтому я не думаю, что рекомендовать его — полезный ответ. - person Costi Ciudatu; 08.02.2015
comment
Он думает, что несчастлив. Это не влияет на правильность моего ответа или нет. - person Ben Watson; 08.02.2015
comment
Я думаю, стоит добавить, что слепое применение hashCode() ко всему ключу полезно не для всех сценариев, это нормально для простых текстовых ключей, таких как приведенные в примере. - person Ben Watson; 08.02.2015
comment
У вас есть мой голос за ваше предложение, хотя оно справедливо только в том случае, если ожидается, что количество ключей будет расти с размером набора данных. Что, если ключи - это континенты? - person Costi Ciudatu; 08.02.2015
comment
да, я также могу отсортировать все ключи по количеству записей, а затем использовать для этого жадную стратегию. В большинстве случаев она будет стремиться к равномерному распределению. Я хотел бы знать, существует ли алгоритм для получения теоретического оптимального решения. Может быть, какой-то алгоритм для плана распределения, но я не уверен. так что прошу помощи - person Tim; 08.02.2015
comment
О сортировке @Tim по количеству записей не может быть и речи, если вы имеете в виду количество записей в текущем вычислении; это проблема курицы и яйца, поэтому вы можете полагаться только на предыдущие результаты. - person Costi Ciudatu; 08.02.2015

arrow_upward
1
arrow_downward

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

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

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

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

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

person Costi Ciudatu    schedule 08.02.2015