在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

你在那裏缺少爲log N細節。

此外，似乎是一個緊密匹配您的需求。

在我們分配N個條目之後，只要N從不增長，賦值爲O（1）。但是，對於創建新條目的每個分配，它將分攤到O（log N）。每超過一次Python，分配就會加倍。如果你要繼續添加和刪除而不增加N，那麼賦值就是O（1）。

addTicker()可能有條件地del，然後無條件地做最後兩條語句，因爲它們在任何情況下都是相同的。

O（N）註釋應該是O（N log N），因爲這是排序需要多長時間，並且沒有理由相信所有條目已經排序。