Круг Знакомств


Алгоритм, демонстрирующий круг знакомств человека для
Январь 28, 2016 – 19:05
Круг знакомств - Элитный Клуб

Предположим, что нам требуется разработать алгоритм, демонстрирующий связи человека с человеком, но при условии, что база очень большая. Например, для использования в Facebook или LinkedIn.

Хороший способ решить эту задачу — устранить ограничения и сначала разобраться с упрощенной версией.

Шаг 1. Упрощаем задачу — забудьте о миллионах пользователей

Прежде всего, давайте забудем, что имеем дело с миллионами пользователей. Найдем решение для простого случая.

Можно создать граф и рассматривать каждого человека как узел, а существование связи между двумя узлами говорит, что пользователи — друзья.

class Person {

Person friends;

// Другая информация

При необходимости нахождения связи между людьми, очевидно, стоит использовать всеми известный алгоритм поиска в ширину.

Почему не в глубину? Это очень неэффективно. Два пользователя могут быть «соседями», но нам придется просмотреть миллионы узлов в их поддеревьях, прежде чем связь обнаружится.

Шаг 2. Возвращаемся к миллионам пользователей

Когда мы имеем дело с огромными сервисами Linkedln или Facebook, то не можем хранить все данные на одном компьютере. Это означает, что простая структура данных Person не будет работать — наши друзья могут оказаться на разных компьютерах. Таким образом, нам нужно заменить списки друзей списками их ID и работать с ними следующим образом:

  1. Для каждого ID друга: int machine_index = getMachineIDForUser(personID).
  2. Переходим на компьютер #machine_index.
  3. На этом компьютере делаем: Person friend = getPersonWithID(person_id).

Приведенный далее код демонстрирует этот процесс. Мы определили класс Server, хранящий список всех компьютеров, и класс Machine, представляющий отдельную машину. У обоих классов есть хэш-таблицы, обеспечивающие эффективный поиск данных.

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

public class Server {

HashMap

Source: tproger.ru
Похожие публикации