У меня есть довольно уникальная проблема, которую я хочу решить, и я надеюсь, что кто-то здесь может дать мне некоторое представление о том, как лучше всего ее решить.
Проблема: Предположим, что список из N номеров распределяется среди набора участников таким образом, что ни один участник не знает ни одного из номеров, которые они разделяют. Все участники знают N (размер списка чисел) и сумму всех чисел в списке, но ничего более априори.
Работая вместе, можно сравнить два общих числа a и b таким образом, чтобы участники узнали, верно ли утверждение «a <b», но не более того. Однако это чрезвычайно дорогое занятие (читай: на завершение отдельного сравнения может потребоваться много секунд, возможно, даже минут). Смотрите в конце этого поста немного больше информации о том, как это возможно.
В конце дня стороны хотят, чтобы индексы в списке соответствовали «верхним K процентам» (K%, который является наибольшим) общими номерами в списке. Это, конечно, можно сделать путем сортировки или использования алгоритма выбора «top K». Тем не менее, они, как правило, используют очень много сравнений, которых следует избегать. (Это либо O (n log n), либо O (n) с довольно большими скрытыми константами.)
Другой альтернативой является «угадать» число X, для которого (1-K)% меньше, чем X, а K% больше. Затем вы можете сравнить каждый элемент с X и увидеть, сколько их больше, а сколько меньше. Если ваше предположение было неверным, пересмотрите его, используя что-то вроде бинарного поиска, пока не найдете правильное решение. Это займет гораздо меньше сравнений, если ваше предположение хорошо.
Итак, мой вопрос,
Учитывая только N и сумму, каков наилучший способ «предсказать» X?
Конечно, это будет зависеть от основного распределения. Для разных вариантов использования базовое распределение, вероятно, будет другим, но будет известно, поэтому я заинтересован в хороших решениях для всех общих (нормальных, равномерных, экспоненциальных, возможно, некоторых других). Я также хотел бы услышать предложения о том, как лучше всего выполнить «бинарный» поиск, чтобы минимизировать количество шагов с учетом предположения о базовом распределении.
, Учитывая эту долю, участник не имеет информации (в теоретико-информационном смысле) о числе; на самом деле, ни одна надлежащая группа участников не может объединить знания, чтобы узнать какую-либо информацию об общих номерах. Однако, используя сложную безопасную технику многопартийных вычислений, можно определить, меньше ли одно общее значение, чем другое, не раскрывая больше информации. Этот метод вовлекает всех участников сотрудничества, поэтому это так дорого и должно быть сделано как можно меньше раз.
Ответы:
Вы, кажется, задаете два связанных вопроса:
Это может потребовать очень разных чисел парных сравнений.
Другим аспектом, который может оказать существенное влияние, является то, какая информация передается. Каждый знает номер, который он получил, знает сумму и результаты «да / нет» сравнений, в которых они принимали участие. Однако вы также говорите, что «стороны хотят выводить, какие индексы в списке соответствуют верхним», поэтому вы предлагаете что некоторая информация об индексах будет передана. В зависимости от того, чем именно вы делитесь, вы снова можете получить очень разные решения.
источник