Социальные сети каждый день рекомендуют нам новых друзей или предлагают подписаться на новые группы. И чем больше у нас друзей и групп в подписках, тем чаще нам рекомендуют что-то новое. Как это работает? Почему из большого числа потенциальных знакомых выбираются именно те, которых мы видим в подборке?
Попробуем спроектировать такую систему. Первая мысль, которая приходит в голову - надо как-то использовать друзей наших друзей, потом их друзей и так далее. Получаем какую-то древовидную штуку, описывающую дружеские отношения между пользователями. Теперь подумаем как выбрать людей, дружба с которыми наиболее вероятна. Ведь если прикинуть, что у пользователей в среднем по 100 друзей, то через 3 перехода по дереву у нас будет 1 000 000 кандидатов, всех мы показать никак не сможем.
Такую проблему можно решить пересечением множеств друзей. Это значит, что мы возьмем всех друзей нашего условного друга А, всех друзей нашего условного друга Б и пересечем эти два множества. Те люди из этого множества, с которыми мы еще не дружим, вероятнее с нами подружатся, чем те, которые в пересечение не вошли. Теперь проделаем это со всеми друзьями, после пересечения множеств 10-15 друзей мы получим примерно столько же кандидатов. И скорее всего эти люди будут одноклассниками или одногруппниками нашего пользователя - магия.
Давайте развивать идею с деревьями и пересечениями. Можем не отбрасывать людей, не вошедших в итоговое множество, а каждому кандидату присваивать число - в сколько пересечений он вошел. Теперь будем каждый день показывать нашему пользователю топ 3-5 людей из еще не показанных.
Вот так с помощью деревьев и пересечений множеств мы на коленке спроектировали рекомендательный сервис. К слову, примерно такой алгоритм в Нетфликсе. Так что мы с вами сделали крутую штуку.