2

我有一份要求执行的新操作的列表。只有两种类型，订阅和取消订阅，或 + 和 - 操作。每个动作都有一个id附加的。由于某些原因，在此列表中可能有两个动作有效地相互抵消 - 一个 + 和一个 - 动作，两者使用相同的 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

这行得通，但逻辑上有相当多的重复，对于这样一个简单的事情来说，感觉机器太多了。更不用说它的效率很低了。

那么，本质上，我怎样才能使这个功能更加清晰和高效，而不需要在最后执行太多昂贵的操作呢？

4

2 回答 2

2

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

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

哈希表的附加优点是仅列出用于订阅或取消订阅（而不是两者）的操作将被重复数据删除。被列为订阅两次的操作 A 最终只会被订阅一次。

因此，要在 Python 中实现这一点，请使用dict类型。为了更容易测试是否已经针对相反的更改处理了操作 id，您可以创建一个包含两个字典的元组。这些映射每个 id 的订阅和取消订阅。元组由“取消订阅”（0）和“订阅”（1）的索引来处理，您可以通过从 1 中减去来轻松调整此索引以查看“相反”存储桶。因此，如果正在订阅操作 A（索引 1）然后您在元组中签入1 - 1> item 0，反之亦然。

我在这里假设这action.change是一个设置为'subscribe'or的字符串值'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

现在你有两个带有 unsubscribes 和 subscribes 的字典，可以分别处理：

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

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

如果您使用的是 Python 3.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
于 2019-06-12T08:18:21.403 回答
1

最简单的方法是使用单个哈希映射，将 +1 用于订阅，将 -1 用于取消订阅，然后相应地订阅/取消订阅。这可以使用 Python dict、defaultdict或Counter. 每一个都有 O(1) 的查找，对于 n 个动作的总复杂度为 O(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)).

然后，只需迭代字典中的值并打印那些带有+1or的值-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
于 2019-06-12T08:44:05.413 回答