Эффективно "отменяя" операции в списке

Question

У меня есть список новых действий, которые были запрошены для выполнения.Есть только два типа, подписаться и отписаться, или + и - действия.К каждому действию прикреплен id.По определенным причинам могут быть два действия, которые фактически отменяют друг друга в этом списке - действие + и -, оба с одинаковым идентификатором, отменяют - и поскольку каждое действие несколько дорого, яне хочу выполнять больше, чем необходимо.Поэтому я хочу найти в списке и отменить противоположности.Это звучит как достаточно простая проблема, и это так, но в данном списке может быть большое количество действий (300).Не такая уж большая проблема, но я пытался найти алгоритм, который нашел бы место между эффективностью и чистотой, и я не знаю конкретных терминов для такого рода проблем, поэтому я не могу найти ничего существенного, ища вокруг.

Конечно, некоторый базовый код будет работать отлично.Например, в Python (хотя этот вопрос не относится конкретно к Python):

def perform_actions(actions_list):
    new_subscriptions = []
    new_unsubscriptions = []

    for action in actions_list:
        id_ = action.id_

        if isSubscribeType(action): # stand-in for some real check
            if id_ in new_unsubscriptions:
                new_unsubscriptions.remove(id_)
                continue

            new_unsubscriptions.append(id_)
        else:
            if id_ in new_subscriptions:
                new_subscriptions.remove(id_)
                continue

            new_unsubscriptions.append(id_)

    for action in new_subscriptions:
        # do subscription

    for action in new_unsubscriptions:
        # do unsubscription

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

Итак, по сути, как я могу сделать эту функцию более понятной и эффективной, не выполняя слишком много дорогих действий в конце?

Answer 1

Вам необходимо использовать хеш-таблицу (также известную как отображения или словари) для отслеживания подписок и отписок, где ключом является идентификатор действия. Хеш-таблицы дают O (1) постоянный поиск времени, поэтому тестирование, чтобы увидеть, был ли обработан идентификатор действия до того, дешево. В Python тип dict является такой хеш-таблицей. С помощью хеш-таблицы вы можете обработать ваши действия за O (N) времени за N действий, то есть за линейное время.

Использование списка Python, с другой стороны, неэффективно, поскольку списки (массивы, последовательности) требуют полного сканирования для проверки членства. Это означает, что они тратят O (N) времени, чтобы проверить, был ли идентификатор действия уже виден ранее, и ваш алгоритм замедляется по мере добавления новых действий, а ваш код выполняет O (N ^ 2) (N раз N) шагов для обработки все N действий. Поскольку ваш список действий увеличивается в размере, его обработка занимает квадратичное время.

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

Итак, чтобы реализовать это в Python, используйте тип dict. Чтобы упростить тестирование, если идентификатор действия уже обработан для напротив изменения , вы создаете кортеж с двумя словарями . Эти подписки карты и отписки от подписки. К кортежу обращаются по индексу для «отписаться» (0) и «подписаться» (1), и вы можете тривиально откорректировать этот индекс, чтобы посмотреть в «противоположный» сегмент, вычитая из 1. Так что если действие А подписавшись (индекс 1), вы регистрируете 1 - 1> item 0 в кортеже и наоборот.

Я предполагаю, что action.change - это строковое значение, установленное в 'subscribe' или 'unsubscribe', и эту строку можно использовать для сопоставления с индексами с дополнительным словарем:

changes = ({}, {})  # unsub, sub
changemap = {'unsubscribe': 0, 'subscribe': 1}
for action in action_list:
    change = changemap[action.change]  # unsubscribe / subscribe -> 0 or 1
    if action.id_ in changes[1 - change]:  # 0 becomes 1, 1 becomes 0
        # action is listed twice for both subscribe and unsubscribe
        # cancel opposite and skip this action
        del changes[1 - change][action.id_]
        continue

    changes[change][action.id_] = action

Теперь у вас есть два словаря с отписками и подписками, которые можно обрабатывать отдельно:

for action in changes[0].values():
    # unsubscribe action

for action in changes[1].values():
    # subscribe action

Если вы используете Python 3.6 или новее, словари производят свои ключи и значения в порядке вставки, поэтому вышеописанное будет обрабатывать все отписки в том же относительном порядке, в котором они были перечислены в actions_list, и то же самое относится к подпискам.

Если вам только нужен атрибут action.id_ для подписки или отмены подписки на действие, вы можете заменить словари наборами и сохранить только идентификаторы действий. Наборы не помнят порядок вставки, однако.

Если действия должны быть отброшены в целом , если они перечислены как минимум два раза с конфликтующими изменениями (например, две подписки и одна отмена подписки), то вам также нужен отдельный набор "отмена", отслеживающий удаленные вами идентификаторы от рассмотрения:

changes = ({}, {})  # unsub, sub
changemap = {'unsubscribe': 0, 'subscribe': 1}
cancelled = set()
for action in action_list:
    if action.id_ in cancelled:
        # this action.id_ has been observed to both subscribe and unsubscribe
        # and has been cancelled altogether.
        continue

    change = changemap[action.change]  # unsubscribe / subscribe -> 0 or 1)
    if action.id_ in changes[1 - change]:
        # action is listed twice for both subscribe and unsubscribe
        # cancel opposite and ignore all further references to this action id
        del changes[1 - change][action.id_]
        cancelled.add(action.id_)
        continue

    changes[change][action.id_] = action

Answer 2

Самым простым способом было бы использовать одну хэш-карту, считая +1 для подписок и -1 для отписок, а затем соответственно подписываясь / отписываясь.Это можно сделать очень легко, используя Python dict, defaultdict или Counter.Каждый из них имеет поиск O (1) для общей сложности O (n) для n действий.Вы говорите, что порядок не имеет значения, но в Python 3.6 и более поздних версиях словарь фактически сохранит элементы в том же порядке, в котором они были впервые вставлены.

Я не знаю, как именно представлены ваши действиятак что я просто буду использовать строки типа "+1" для «подписки пользователя 1».Должно быть легко приспособить это к вашей модели действия.

actions = ["+1", "-1", "+2", "+1", "+3", "+4", "-2", "-5"]

# get final (un)subscriptions
from collections import defaultdict
remaining = defaultdict(int)
for what, who in actions:
    remaining[who] += +1 if what == "+" else -1
print(remaining) # {'1': 1, '2': 0, '3': 1, '4': 1, '5': -1})

Если не может быть никаких «недействительных» действий (например, отмена подписки уже отписавшегося пользователя), тогда dict никогда не может содержать другие значения, кроме +1 (подписаться), -1 (отписаться) или 0 (отменено).Если может быть недействительной (не) подпиской, было бы легко проверить текущее значение и соответственно отменить действие, например, просто ограничив новое значение до max(-1, min(value, +1)).

Тогдапросто переберите значения в словаре и напечатайте те, которые остались, с +1 или -1:

# print remaining (un)subscriptions
for k, v in remaining.items():
    if v == +1:
        print("subscribe", k)
    elif v == -1:
        print("unsubscribe", k)

Вывод:

subscribe 1
subscribe 3
subscribe 4
unsubscribe 5