выводя изменения из списков назначений оборудования с течением времени

Question

В моей маленькой задаче у меня n пользователей и m оборудований (m и n ~ 50000). Один пользователь может использовать одно и только одно оборудование одновременно.

У меня есть список записей в этом формате [ u, e, t ], с t (время), отсортированными по возрастанию. Каждая запись означает, что пользователь u использует оборудование e во время t . Количество записей составляет около 500 миллионов. Предположим, что две ближайшие записи с одинаковыми u и e означают, что u постоянно использует e . Например:

1, 2, 1  
3, 4, 1    
1, 2, 3
1, 2, 4 
1, 2, 5 
2, 6, 6
3, 2, 6  
3, 2, 8 

будет означать, что пользователь 1 использует оборудование 2 от 1 до 5.

Что я хочу сделать, это из этого списка, вывести время смены в следующем формате: [ u, e, st, et ], что означает, что пользователь u использует оборудование e от времени начала st до времени окончания et .

Результат для данных выборки будет:

1, 2, 0, 5  
3, 4, 0, 6  
3, 2, 6, 8

(при условии, что время начинается с 0 и заканчивается в max (t), и когда пара (u, e) впервые видна, u уже начал использовать e с начала времени 0. Аналогично для последних записей. )

Учитывая большой список (500 миллионов записей), но достаточно маленький m и n, как я могу сделать это наиболее эффективно?

@ Редактировать: Возможные несоответствия данных:
1: Если в данных выборки есть только 1 запись (поэтому нет времени окончания), например, случай [2, 6, 6]:
--- Если это единственный раз, когда пользователь 2 и оборудование 6 появляются в наборе данных, игнорируйте точку данных.
--- Если после этой записи пользователь 2 использует другое оборудование, скажем, 7 на 10, то 2 использует 6 от 6 до 10.
--- Если после этой записи оборудование 6 используется другим пользователем, скажем, 10 в 11, то 2 использует 6 от 6 до 11.

Answer 1

Определите две структуры (я знаю, что это Java, но давайте предположим универсальный алгоритм):

struct user_record {
    int machine_idx;
    int start_time;
}

struct machine_record {
    int user_idx;
    int start_time;
}

Учитывая, что пользователь не может использовать более одного оборудования одновременно, вы можетесоздайте массив / вектор user_record s, по одному для каждого пользователя (вы сказали, что это ~ 50k, так что это должно быть отслеживаемо), и массив / вектор machine_record s, по одному для каждой машины.Инициализируйте элементы idx всех элементов в -1 (чтобы указать, что в данный момент они не активны).

Затем каждый раз, когда вы сталкиваетесь с входной записью, проверяйте состояние соответствующих полей idx в user_record иmachine_record массивы.Существует три варианта:

1. Оба имеют значение -1. ​​ Это начальная точка, поэтому установите эти элементы так, чтобы они были "направлены" друг на друга, и запишите start_time в каждомone.
2. И то, и другое не равно -1, и согласовано. Это конечная точка, поэтому просто создайте выходную запись и сбросьте поля idx этих элементов обратно в -1.
3. По крайней мере, один не равен -1, но они несовместимы. Вам потребуется создать две выходные записи, перезаписать элементы новыми значениями, а также установить соответствующий старый компьютер./ пользовательские индексы равны -1.

Это O (N) время (где N - количество входных записей).

Примечание. Выходные данные будут отсортированы по времени окончания.

Answer 2

@ Оли-Чарльзуорт находится на правильном пути, но с недостаточной детализацией.

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

Инициализируйте все так, чтобыкаждый пользователь указывает на -1 (без компьютера), а каждый компьютер указывает на -1 (без пользователя).Вот псевдокод для обработки ваших записей:

for (user, machine, time) in records:
    # By user.machine I mean look up the machine the user currently points at
    if user.machine <> machine:
        output_record_and_clear(user)
        if machine.user <> user:
            output_record_and_clear(machine.user)
        user.machine = machine
        machine.user = user
        user.start_time = time
    user.end_time = time

def output_record_and_clear (user):
    if -1 <> user.machine and user.start_time < user.end_time:
        emit(user, user.machine, user.start_time, user.end_time)
    user.machine.user = -1
    user.machine = -1

Answer 3

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

Вы также можете делать это в памяти построчно, сохраняя хэш-таблицу используемых машин и время их последнего использования, когда вы снова видите машину, выводите использованное время и обновляете таблицу. , Только с 50 000 машин это должно работать нормально.