提高列表Rem的时间效率

Question

有什么更快的方法可以“删除”我已经添加到序列中的项目，这样我就不会再遇到它们了？在我的实际代码中，我有更大的单词序列，因此使用.remove(word)在时间上是非常昂贵的。你知道吗

我目前的想法：

• 将单词存储在heapq中，而不是列表中，并按照我使用的启发式方法对它们进行排序。（这里的问题是，我需要在从序列中删除一个单词后更新启发值，因此我不认为它有助于提高时间复杂度）

• 使用哈希映射检查单词是否在序列中。在这种情况下，时间复杂性如何？

我有以下代码（为了简单起见，我使用了random.choice，因为我实际上是在使用启发式来选择下一个单词）：

import random
d = {'b': ['bob', 'bun', 'bom'], 'd': ['dob', 'don'], 'm': ['mox']}

print(d)
seq = []
current = 'bob'
seq.append(current)
d[current[:1]].remove(current)
while current[-1:] in d and d[current[-1:]]:
    next_ = random.choice(d[current[-1:]])
    current = next_
    seq.append(current)
    d[current[:1]].remove(current)

print(d)
print(seq)

输出示例：

{'b': ['bob', 'bun', 'bom'], 'd': ['dob', 'don'], 'm': ['mox']}
{'b': ['bun'], 'd': ['dob', 'don'], 'm': []}
['bob', 'bom', 'mox']

Answer 1

如果您想保持列表的完整性，但项目的顺序无关紧要，则需要执行以下操作。如果不需要将列表与其所有项一起保留，那么将要删除的项与最后一个项L[-1], L[idx] = L[idx], L[-1]交换并调用L.pop()会更简单。你知道吗

---

不要移除任何东西。为每个列表保留一个计数，并将该元素与要删除并减少计数的元素交换：

所以[0, []]是空列表，[3, [1,2,3]]是删除前的列表1，[2, [3,2,1]]是删除后的列表。你知道吗

这使得移除项目的效果与Knuth shuffle步骤相同。然后，要选取一个随机项，您将生成一个介于0和剩余计数之间的数字，然后将该索引与剩余计数减1的项交换。你知道吗

生成一个：[len(L)+1, L]

要随机选取项目：

remaining_count, L = cL
idx = random.randrange(0, remaining_count)
value = L[idx]
L[remaining_count - 1], L[idx] = L[idx], L[remaining_count - 1]
cL[0] = remaining_count - 1

你知道吗random.randrange随机范围将在remaining_count为-1时引发ValueError，此时列表已耗尽。你知道吗

结果是在O（1）时间内删除项。您可以通过cL[0] = len(cL[1])在O（1）中按无序顺序将列表还原为其原始项。你知道吗

如果需要修剪已删除的图元，可以使用一个：

del cL[1][cL[0]-1:]

它将删除剩余的\u count减1之后的元素，由于此操作发生在列表的末尾，因此成本较低。你知道吗