Как сбалансировать хеш-таблицу на основе частоты слов, когда частота слов сильно отличается

Question

Есть N машин, и мне нужно распределить список слов по этим машинам. Одно и то же слово должно попадать на одну и ту же машину, поэтому я решил вычислить значение хеш-функции для каждого слова, а затем mod N и использовать полученное значение для распределения. Проблема в том, что если частоты слов не являются однородными, что делает распределение неравномерным, есть ли способ сбалансировать нагрузку на машины? Вопрос просит меня показать функцию отображения, которая будет использоваться. Заранее спасибо

Answer 1

Аннотация проблема: у вас есть набор чисел (частот слов), который вы хотите разделить на N подмножеств, так что суммы подмножеств "сбалансированы".

Во-первых, вы не определили "сбалансированный". Во многих парадигмах это просто минимизация максимальной суммы. В других это сводит к минимуму диапазон сумм (самый высокий минус самый низкий). Более того, это может быть MSE (среднеквадратическая ошибка) сумм. Учитывая отсутствие спецификации, мне придется оставить эту настройку для вас.

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

Оптимальным решением было бы иметь каждое значение деления на среднее значение: total_word_count / N. Существует два популярных инструмента, которые можно применять для решений «быстрого удара».

1. Сумма к цели: вычислите среднее значение (давайте просто назовем его mean), а затем применим алгоритм подмножества суммы N-1 раз. По мере нахождения каждого решения удаляйте эти элементы из набора чисел.
2. «Выбирай команды». Это жадное решение. Сортировать числа в порядке убывания. Инициализируйте N пустые подсписки. Выполните итерацию по этому отсортированному набору, выделяя каждое число подсписку, который имеет наименьшую сумму на данный момент.

Практически в любом приложении на реальном языке частоты будут следовать распределению с большим количеством малоиспользуемых слов. В результате вторая атака даст вам оптимальное решение в O (n log n) время - O (n log n) , за которым следует O (N) пропуск.