Написать пост

Алгоритм, демонстрирующий круг знакомств человека для социальных сетей

Аватар Типичный программист

Обложка поста Алгоритм, демонстрирующий круг знакомств человека для социальных сетей

Предположим, что нам требуется разработать алгоритм, демонстрирующий связи человека с человеком, но при условии, что база очень большая. Например, для использования в 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, представляющий отдельную машину. У обоих классов есть хэш-таблицы, обеспечивающие эффективный поиск данных.

			public class Server {
	HashMap<Integer, Machine) machines = new HashMap<Integer, Machine>();
	HashMap<Integer, Integer) personToMachineMap = new HashMap<Integer, Integer>();
	public Machine getMachineWithId(int machinelD) {
		return machines.get(machineID);
	}

	public int getMachineIDForUser(int personID) {
		Integer machinelD = personToMachineMap.get(personID);
		return machineID == null ? -1 : machineID;
	}

	public Person getPersonWithID(int personID) {
		Integer machineID = personToMachineMap.get(personID);
		if (machineID == null)
			return null;
		Machine machine = getMachineWithId(machineID);
		if (machine == null) return null;
		return machine.getPersonWithID(personID);
	}
}
public class Person {
	private ArrayList<Integer> friendIDs;
	private int personID;
	public Person(int id) { this.personID = id; }

	public int getID() { return personID; }

	public void addFriend(int id) { friends.add(id); }
}
public class Machine {
	public HashMap<Integer, Person> persons = new HashMap<Integer, Person>();
	public int machinelD;
	public Person getPersonWithID(int personID) {
		return persons.get(personID);
	}
}
		

Существует несколько направлений оптимизации и дополнительные вопросы, которые следует обсудить.

Оптимизация: сократите количество переходов между компьютерами

«Путешествие» с одной машины на другую — дорогая операция (с точки зрения системных ресурсов). Вместо перехода с машины на машину в произвольном порядке работайте в пакетном режиме. Например, если пять друзей «живут» на одной машине, сначала получите информацию о них.

Оптимизация: разумное «деление» людей и машин

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

Вопрос: при поиске в ширину необходимо помечать посещенные узлы. Как это сделать?

При поиске в ширину мы устанавливаем флаг visited для посещенных узлов и храним его в классе узла. В нашем случае так поступать нельзя. Поскольку одновременно выполняется множество запросов, данный подход помешает редактировать данные. Вместо этого можно имитировать маркировку узлов с помощью хэш-таблицы, в которой будет храниться id узла и отметка, посещен он или нет.

Другие насущные вопросы:

  • В реальном мире происходят сбои серверов. Как это повлияет на проект?
  • Как можно использовать кэширование?
  • Вы производите поиск до конца графа? (Граф может быть бесконечным.) Когда нужно остановиться?
  • Некоторые люди имеют больше друзей, чем другие, следовательно, более вероятно, что таким образом можно найти связь между вами и кем-то еще. Как использовать эти данные, чтобы выбрать место, где начинать обход графа?

Это всего лишь некоторые из множества вопросов, которые могут возникнуть у вас при реализации такого алгоритма.

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).

Следите за новыми постами
Следите за новыми постами по любимым темам
11К открытий11К показов