Кто-нибудь знает алгоритм или структуру данных, относящихся к выбору элементов, с вероятностью их выбора пропорционально некоторому приложенному значению? Другими словами: http://en.wikipedia.org/wiki/Sampling_%28statistics%29#Probability_proportional_to_size_sampling
Контекст здесь представляет собой децентрализованную систему репутации, и поэтому приложенное значение - это значение доверия, которое один пользователь оказывает другому. В этой системе все узлы либо начинаются как друзья, которым полностью доверяют, либо неизвестные, которым полностью не доверяют. Это само по себе бесполезно в большой сети P2P, потому что будет гораздо больше узлов, чем у вас есть друзья, и вам нужно знать, кому можно доверять в большой группе пользователей, которые не являются вашими прямыми друзьями, поэтому я реализовал динамическая система доверия, в которой неизвестные могут завоевать доверие посредством отношений друг-друг.
Время от времени каждый пользователь выбирает фиксированное число (ради скорости и пропускной способности) целевых узлов, чтобы пересчитать их доверие на основе того, насколько доверяет им другое выбранное фиксированное количество промежуточных узлов. Вероятность выбора целевого узла для пересчета будет обратно пропорциональна его текущему доверию, так что неизвестные имеют хороший шанс стать более известным. Промежуточные узлы будут выбраны таким же образом, за исключением того, что вероятность выбора посредника пропорциональна его текущему доверию.
Я сам написал простое решение, но оно довольно медленное, и я хотел бы найти библиотеку C ++, чтобы справиться с этим аспектом для меня. Конечно, я сделал свой собственный поиск, и мне удалось найти TRSL, который я сейчас копаю. Поскольку это кажется довольно простой и, возможно, распространенной проблемой, я ожидаю, что для этого будет гораздо больше библиотек C ++, поэтому я задаю этот вопрос в надежде, что кто-то здесь сможет пролить свет на это.