python - 列表中的高效 "cancelling out"操作

Question

我有一个已请求执行的新操作列表。只有两种类型，订阅和取消订阅，或 + 和 - 操作。每个操作都有一个 id 附加到它。由于某些原因，可能有两个 Action 在这个列表中有效地相互抵消 - 一个 + 和一个 - Action ，两者 具有相同的 id，抵消 - 由于每个 Action 都有些昂贵，我不想做超出必要的事情。所以我想搜索列表并取消对立面。这听起来像是一个足够简单的问题，而且确实如此，但是给定列表中可能有大量(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

您需要使用 hash table (也称为映射或字典)，用于跟踪订阅和取消订阅，其中键是操作 ID。哈希表为您提供 O(1) 常数时间查找，因此测试以查看操作 ID 之前是否已被处理是便宜的。在Python中，dict类型就是这样一个哈希表。使用哈希表，您可以在 O(N) 时间内处理 N 个操作的操作，因此在线性时间内。

另一方面，您对 Python 列表的使用效率不高，因为列表(数组、序列)需要完整扫描 来测试成员资格。这意味着他们需要 O(N) 时间来测试之前是否已经看到一个 Action ID，并且随着您添加更多 Action ，您的算法会变慢，并且您的代码需要 O(N^2)(N 乘以 N)步骤来处理所有 N 个 Action 。随着您的操作列表大小的增长，处理列表需要 二次 时间。

哈希表的额外优势在于，仅列出用于订阅或取消订阅(而不是两者)的操作将被删除重复。被列为订阅两次的 Action A 最终只会被订阅一次。

因此，要在 Python 中实现它，请使用 dict 类型。为了更容易地测试是否已经为相反 更改处理了操作 ID，您可以创建一个包含两个字典 的元组。这些 map 订阅和取消订阅每个 ID。该元组由“取消订阅”(0) 和“订阅”(1) 的索引寻址，您可以简单地调整此索引以查看“相反”存储桶通过从 1 中减去。因此，如果正在订阅操作 A(索引 1)，那么您将 checkin 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

如果您使用的是 Python 3.6 或更新版本，字典会按插入顺序生成它们的键和值，因此以上将按照它们在 actions_list 中列出的相同相对顺序处理所有取消订阅，并且这同样适用于订阅。

如果您只需要action.id_ 属性来订阅或取消订阅一个 Action ，那么您可以用集合替换字典并只存储 Action 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