Комментарии 9
С таким алгоритмом сложность выбора одной реплики — O(N), сложность выбора K реплик — O(N + K lg N) ~ O(N lg N)..
Привет! Спасибо за статью.
А можете, пожалуйста, рассказать, как у вас получилась такая оценка? Не понял перехода от O(N + K lg N) к O(N lg N). при условии произвольности K.
Привет!
K <= N, что поэтому подставляем N вместо K. (N lg N) > N, поэтому оставляем под O большее слагаемое.
У меня есть неплохая ссылка, кстати :)
В этом случае сложность в худшем случае, когда придётся постоянно перестраивать дерево — O(N lg N), сложность в среднем — O(N), как и при использовании quickselect.
Придется пройтись по всем M документам, т.ч. сложность в среднем будет — O(M).
По первой задаче вопрос. Можете ли как-то доказать, что вероятности выбора каждой реплики будут пропорциональны w[i]? Мне кажется, ваше решение не работает совсем.
Допустим n=3, k=2, w={1, 2, 3}.
Тогда ваше решение с вероятностью 1/6 возьмет 1. Потом с 2/5 возьмет 2 или с 3/5 возьмет 3.
Или же с вероятностью 1/3 сначала возьмет реплику 2, потом с 1/4 — 1 или с 3/4 — 3.
Последний вариант с вероятностью 1/2 — 3, потом 1/3 — 1 или 2/3 — 2.
Если все перемножить, то 6 вариантов выбра двух реплик из трех будут:
{1, 2} — вероятность 1/15, {1,3} — 1/10, {2, 1} — 1/12, {2,3} — 1/4, {3,1} — 1/6 и {3,2} — 1/3.
Или если забить на порядок реплик:
{1, 2} — 9/60
{1, 3} — 16/60
{2, 3} — 35/60
Т.е. реплика 3 будет взята в 51/60 случаев, 2 в 44/60, а 1 в 25/60. Соотношения 1:2:3 тут нет.
Или совсем вырожденный пример: n=k, а веса не одинаковые. Тут решения, вообще говоря, нет. Ведь единственный вариант — это взять все реплики, и тогда каждая будет взята в 100% случаев. А если веса разные, то и вероятности не пропорциональны.
Или я не понял условие?
Можете ли как-то доказать, что вероятности выбора каждой реплики будут пропорциональны w[i]?
Илья, спасибо за комментарий! В рамках данной задачи я имел в виду, что для трёх реплик с весами {1; 2; 3} соотношение 1:2:3 будет выполняться для вероятности выбрать каждую из них в качестве первой, а не для вероятности, что реплика содержится в кортеже длины K.
Или я не понял условие?
Скорее, это я не смог сформулировать условие так, чтобы его можно было понять только безошибочно :)
Про первую задачу опять:
Именно этот алгоритм реализован в коде библиотеки ClusterClient из проекта «Восток». (Там дерево строится за O(N lg N), но на итоговую сложность алгоритма это не влияет.)
Я посмотрел код, там решается другая задача: Случайно перемешать реплики так, что одна реплика встречается раньше другой с вероятностью, пропорциональной весам. При этом всегда берутся все реплики, меняется лишь порядок:
/// <para>Represents a probabilistic ordering which orders replicas based on their weights.</para>
/// <para>A weight is a number in customizable <c>[min-weight; max-weight]</c> range where <c>min-weight >= 0</c>. </para>
/// <para>Weight for each replica is calculated by taking a constant initial value and modifying it with a chain of <see cref="IReplicaWeightModifier"/>s. Range limits are enforced after applying each modifier.</para>
/// <para>Weights are used to compute replica selection probabilities. A replica with weight = <c>1.0</c> is twice more likely to come first than a replica with weight = <c>0.5</c>.</para>
/// <para>If all replicas have same weight, the ordering essentially becomes random.</para>Тут решение с деревом отрезков и итеративным выбором реплики отлично работает.
В посте же задача — выбрать k реплик из n. При ее составлении, видимо, кто-то предположил, что вероятность войти в первые k у каждой реплики пропорциональна ее весу. Что не правда (опять же: n=k, все веса разные. Задача в посте вообще решения не имеет с такими входными данными). Или кто-то неверно вспомнил условие задачи на конференции или при написании поста.
Я так понимаю, это не было какое-то официальное соревнование с призами и грамотами, а просто обсуждение задачек для интереса? В противном случае, результаты конкурса стоит отменить и принести извинения участникам.
А задачу в посте было бы хорошо изменить или удалить совсем в любом случае. Потому что в таком виде я пока вижу только одно решение — назначить переменными вероятности каждого сочетания из k реплик, задать задачу линейного программирования, а потом прогнать симплекс метод до выбора первого не-фиктивного базиса. Потом выдать одну из n конфигураций с заданной вероятностью. Будет это все не то O(N^4), не то O(N^5).
Я посмотрел код, там решается другая задача
Это не совсем так. Надо обратить внимание на метод SelectReplicaFromTree, который реализует решение с деревом отрезков и итеративным выбором, а не на весь класс WeighedReplicaOrdering. (Я сделал ссылку в посте на конкретный метод, чтобы это было очевиднее.)
Я так понимаю, это не было какое-то официальное соревнование с призами и грамотами, а просто обсуждение задачек для интереса?
Именно так!
А задачу в посте было бы хорошо изменить… Потому что в таком виде я пока вижу только одно решение… Будет это все не то O(N^4), не то O(N^5).
Это было бы очень непрактично — боролись с квадратом, а напоролись на четвёртую степень :)
Как насчёт такой правки к условию? Меняем «a chance of being selected should be proportional to a node’s weight» на «a chance of being selected at every round of selection should be proportional to a node’s weight».
Разбор задач с конференции Hydra — балансировка нагрузки и in-memory хранилища