Python中常量时间更新字典

Question

考虑一个由4个字符串组成的大列表。在

例如：['P0BH'、'LF3J'、'MA1Y'、'STSM'、'8Y74'、'JWBD']

我想按以下精确方式添加新字符串：

如果给定列表中已存在新字符串，请从列表中删除旧值，并在列表前面添加新字符串。例如，如果添加了字符串“MA1Y”，则输出列表如下所示： ['MA1Y'、'P0BH'、'LF3J'、'STSM'、'8Y74'、'JWBD']。如果列表中不存在新字符串，则只需将新字符串放在前面。例如，如果添加了字符串“FSH7”，那么输出列表将如下所示：['FSH7'、'P0BH'、'LF3J'、'MA1Y'、'STSM'、'8Y74'、'JWBD']。在

还有一个警告：算法必须以恒定的时间复杂度运行。我不在乎空间的复杂性。

当然，我已经实现了一个解决方案，如下所示。我相信它在持续的时间复杂性中运行，但我希望我们改进它或重新设计更好的东西。我的理解是一个映射有持续的时间删除、成员资格测试和分配。**在

我的tickerMap类中的addTicker方法是否以固定时间运行？

class tickersMap:
    def __init__(self, tickersList):
        self.Map = {t:i for i, t in enumerate(tickersList)}
        self.firstIndex = 0

    def addTicker(self, newTicker):
        if newTicker in self.Map:
            print('exists')
            del self.Map[newTicker]
            self.Map[newTicker] = self.firstIndex - 1
            self.firstIndex -= 1
        else:
            self.Map[newTicker] = self.firstIndex - 1
            self.firstIndex -= 1

    def listTickers(self):
        # This is O(nlog(n)) but is only required for printing 
        return sorted(self.Map, key=self.Map.get)

Answer 1

你少了一个日志细节。在

而且，OrderedDict似乎非常符合您的需要。在

在我们分配了N个条目之后，赋值是O（1），只要N在此之后不再增长。但是，对于创建一个新条目的每个赋值，它被摊销为O（logn）。Python每次超过分配量就会加倍。如果继续添加和删除而不增加N，那么赋值将是O（1）。在

addTicker()可以有条件地del，然后无条件地执行最后两个语句，因为它们在任何一种情况下都是相同的。在

O（N）注释应该是O（nlogn），因为这是排序所需的时间，没有理由相信所有条目都已经按排序顺序排列了。在