<p>您需要使用<a href="https://en.wikipedia.org/wiki/Hash_table" rel="nofollow noreferrer">hash table</a>(也称为映射或字典)来跟踪订阅和取消订阅,其中键是操作id。哈希表提供O(1)恒定的时间查找,因此测试一个操作id之前是否已被处理是很便宜的。在Python中,<code>dict</code>类型就是这样一个哈希表。使用哈希表,您可以在O(N)时间内处理N个操作,因此在<em>线性</em>时间内。你知道吗</p>
<p>另一方面,使用Python列表是没有效率的,因为列表(数组、序列)需要<em>完全扫描</em>来测试成员资格。这意味着他们要花费O(N)个时间来测试之前是否已经看到了一个动作id,并且当您添加更多的动作时,您的算法会变慢,代码需要O(N^2)(N乘以N)个步骤来处理所有N个动作。随着动作列表的增大,处理列表需要<em>时间。你知道吗</p>
<p>哈希表的另一个优点是,只列出用于订阅或取消订阅(而不是两者)的操作可以消除重复。被列为两次订阅的动作A最终只会被订阅一次。你知道吗</p>
<p>因此,要在Python中实现这一点,请使用<code>dict</code>类型。为了更容易测试是否已经为<em>相反的</em>更改处理了操作id,可以创建一个包含两个<em>字典</em>的元组。这些映射每个id的订阅和取消订阅。元组由“unsubscribe”(<code>0</code>)和“subscribe”(<code>1</code>)的索引寻址,您可以通过从1中减去来轻松地调整此索引以查看“相反”的存储桶。因此,如果动作A被订阅(索引1),那么您将签入元组中的<code>1 - 1</code>>;项<code>0</code>,反之亦然。你知道吗</p>
<p>我在这里假设<code>action.change</code>是一个设置为<code>'subscribe'</code>或<code>'unsubscribe'</code>的字符串值,该字符串可用于映射到具有额外字典的索引:</p>
<pre><code>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
</code></pre>
<p>现在,您有两个字典,其中包含“取消订阅”和“订阅”,可以分别处理:</p>
<pre><code>for action in changes[0].values():
# unsubscribe action
for action in changes[1].values():
# subscribe action
</code></pre>
<p>如果您使用的是python3.6或更高版本,那么字典将按插入顺序生成它们的键和值,因此上面的代码将按照它们在<code>actions_list</code>中列出的相同相对顺序处理所有取消订阅,并且同样的情况也适用于订阅。你知道吗</p>
<p>如果<em>仅</em>需要<code>action.id_</code>属性来订阅或取消订阅操作,则可以将字典替换为集合并仅存储操作ID。但是,集合不记得插入顺序。你知道吗</p>
<p>如果操作应全部删除<em></em>如果它们至少列出了两次且更改有冲突(例如,两次订阅和一次取消订阅),那么您也需要一个单独的“取消”集,跟踪从考虑中删除的ID:</p>
<pre><code>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
</code></pre>