График Al go, чтобы найти ближайшее соединение

Question

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

Таблица содержит ~ 250 миллионов строк, 50 миллионов смен и 100 тысяч уникальных сотрудников. В качестве примера таблица начинается с:

+----------+--------+
| Shift ID | Emp ID |  
+----------+--------+
|        1 | A      |  
|        1 | B      |  
|        2 | A      |
|        2 | C      | 
|        3 | A      |  
|        3 | C      |
+----------+--------+

Сотрудник A работал с Сотрудником B один раз, но с сотрудником C дважды. Поэтому самым частым сотрудником сотрудника А является сотрудник C.

Какой алгоритм может найти наиболее часто встречающийся сотрудник каждого сотрудника? Наивно пытаться найти число попарно общих сдвигов было слишком медленно:

solution = {}
for e in employees:
    maxCommonShifts = 0
    for c in employees:
        if e != c:
            commonTrips = len(e.trips ∩ c.trips)
            if commonTrips > maxCommonShifts:
                maxCommonShifts = commonTrips
                solution[e] = c

Я полагаю, что решением здесь будет граф al go. В частности, эта проблема кажется аналогичной FB, пытающейся вычислить ближайшего друга человека в том смысле, что у него есть самые общие друзья. С точки зрения графика, будет один узел для каждой смены и один узел для каждого сотрудника. Каждый узел сотрудника связан с каждым рабочим узлом смены.

Answer 1

250M строк с 50M сменами дает в среднем 5 строк за смену, поэтому создание набора записей для каждой смены с указанием пар сотрудников в этой смене увеличит размер ваших данных примерно в 5 раз, что дорого, но не слишком ужасно. Таким образом, ваша первая смена, видя 1A и 1B, создаст две записи, записывающие пары AB и BA. Если бы у вас были 1A, 1B и 1 C, то вы бы создали записи AB, A C, BA, B C, CA, CB.

С помощью ввода в этом формате вы можете делать то, что Вы хотите использовать небольшие программы и утилиты сортировки (unix и windows обе имеют программы сортировки) или использовать SQL в базе данных. Сортировать список, возможно, 2000M пар, сгенерированных первым членом, а затем вторым членом. Затем обработайте этот список последовательно. Вы увидите записи, отсортированные по порядку, такие как AB AB AB A C A C AD AD AD AD AE AE ... и вы можете выбрать серии идентичных записей и сосчитать их, отслеживая самые длинные такие бегите за каждым первым элементом пары, когда вы сталкиваетесь с ним.