在lis中高效地“取消”操作

Question

我有一个新的行动，已被要求执行的清单。只有两种类型，订阅和取消订阅，或+和-操作。每个动作都附带一个id。由于某些原因，在这个列表中可能有两个操作可以有效地相互抵消-a+和a-action，都具有相同的id，cancel out-由于每个操作都有些昂贵，我不想执行超出必要的操作。所以我想搜索列表并取消相反的。这听起来是一个足够简单的问题，的确如此，但是在给定的列表中可能有大量（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

最简单的方法是使用一个散列映射，订阅数为+1，取消订阅数为-1，然后相应地订阅/取消订阅。使用Python dict、defaultdict或Counter可以很容易地完成这一点。其中每一个都有O（1）的查找，对于n个操作，总复杂度为O（n）。您说顺序无关紧要，但是对于python3.6和更高版本，字典实际上会以它们第一次插入的相同顺序保留条目。你知道吗

我不知道您的操作是如何表示的，所以我只使用"+1"这样的字符串表示“subscribe user 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（取消订阅）以外的值。如果可以是无效（un）订阅，那么检查当前值并相应地放弃操作就很容易了，例如只需将新值限制为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

Answer 2

您需要使用hash table（也称为映射或字典）来跟踪订阅和取消订阅，其中键是操作id。哈希表提供O（1）恒定的时间查找，因此测试一个操作id之前是否已被处理是很便宜的。在Python中，dict类型就是这样一个哈希表。使用哈希表，您可以在O（N）时间内处理N个操作，因此在线性时间内。你知道吗

另一方面，使用Python列表是没有效率的，因为列表（数组、序列）需要完全扫描来测试成员资格。这意味着他们要花费O（N）个时间来测试之前是否已经看到了一个动作id，并且当您添加更多的动作时，您的算法会变慢，代码需要O（N^2）（N乘以N）个步骤来处理所有N个动作。随着动作列表的增大，处理列表需要时间。你知道吗

哈希表的另一个优点是，只列出用于订阅或取消订阅（而不是两者）的操作可以消除重复。被列为两次订阅的动作A最终只会被订阅一次。你知道吗

因此，要在Python中实现这一点，请使用dict类型。为了更容易测试是否已经为相反的更改处理了操作id，可以创建一个包含两个字典的元组。这些映射每个id的订阅和取消订阅。元组由“unsubscribe”（0）和“subscribe”（1）的索引寻址，您可以通过从1中减去来轻松地调整此索引以查看“相反”的存储桶。因此，如果动作A被订阅（索引1），那么您将签入元组中的1 - 1>；项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

如果您使用的是python3.6或更高版本，那么字典将按插入顺序生成它们的键和值，因此上面的代码将按照它们在actions_list中列出的相同相对顺序处理所有取消订阅，并且同样的情况也适用于订阅。你知道吗

如果仅需要action.id_属性来订阅或取消订阅操作，则可以将字典替换为集合并仅存储操作ID。但是，集合不记得插入顺序。你知道吗

如果操作应全部删除如果它们至少列出了两次且更改有冲突（例如，两次订阅和一次取消订阅），那么您也需要一个单独的“取消”集，跟踪从考虑中删除的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