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

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