快速算法計算出的兩個列表

Question

三角洲我的專輯名稱的兩個列表，通過一些分值排序。

albums_today = ['album1', 'album2', 'album3'] 
albums_yesterday = ['album2', 'album1', 'album3'] 

如何計算列表順序的變化，並得到類似

{'album1':1, 'album2':-1, 'album3':0} 

Answer 1

D = dict((title, rank) for rank, title in enumerate(albums_yesterday)) 
for rank, title in enumerate(albums_today): 
    D[title] = D[title] - rank 

Answer 2

好，取決於你的列表的大小，也有一些不同的方法。不知道你的數據集有多大，我建議最簡單的（也許是不必要的優化）方法是這樣的：

albums_yesterday_lookup = new HashMap(); 
differences = new HashMap(); 
foreach(albums_yesterday as position => album_title) 
    albums_yesterday_lookup.put(album_title,position); 

foreach(albums_today as position => album_title) 
    differences.put(album_title, albums_yesterday_lookup.get(album_title) - position); 

它運行爲O（N）。

Answer 3

這個怎麼樣：

def delta(a, b): 
    rank_a = dict((k, v) for v, k in enumerate(a)) 
    rank_b = enumerate(b) 
    return dict((k, rank_a[k]-i) for i, k in rank_b) 

只創建一個單一的字典看東西進去。

好，只要兩個列表中的每個條目都存在正是每一次，那麼我們知道，一旦我們的rank_a集合中查找的關鍵了，我們不需要它了。我們可以刪除它。另外，爲了節省空間，我們不必在收集特定密鑰之前填充該集合。

class LookupOnce: 
    def __init__(self, seq): 
     self.cache = {} 
     self.seq = iter(seq) 
    def get(self, key): 
     if key in self.cache: 
      value = self.cache[key] 
      del self.cache[key] 
      return value 
     for v,k in self.seq: 
      if k == key: 
       return v 
      self.cache[k] = v 
     raise KeyError 


def delta(a, b): 
    rank_a = LookupOnce(enumerate(a)) 
    rank_b = enumerate(b) 
    result = {} 
    for i, k in rank_b: 
     result[k] = i - rank_a.get(k) 
    return result 

Answer 4

新的和改進的，而不是爲O（n ）：但仍慢於另外兩個答案。

這種解決方案的唯一優點是存儲器的節省。它避免了建立一個大字典，而是隻存儲當時的必要條件。 TokenMacGuy的第二種解決方案也可以做到這一點，但速度稍快。

def get_deltas_aas(today, yesterday): 
    deltas = {} 
    for (new_rank, new_album), (old_rank, old_album) in \ 
      itertools.izip(enumerate(today), enumerate(yesterday)): 
     if old_album in deltas: 
      #Believe it or not, this is faster than deltas.pop(old_album) + old_rank 
      yield (old_album, deltas[old_album] + old_rank) 
      del deltas[old_album]  
     else: 
      deltas[old_album] = old_rank 

     if new_album in deltas: 
      yield (new_album, deltas[new_album] - new_rank) 
      del deltas[new_album] 
     else: 
      deltas[new_album] = -new_rank 

下面是這裏的大部分答案的一些時序結果（所有在Python中的人，除非我錯過了什麼）。 dict排序有效。如果有人希望我以任何方式更改他們的代碼，只需ping我即可。

get_deltas_token1: 1.08131885529 msecs 
get_deltas_gnibbler: 1.06443881989 msecs 
get_deltas_tyler: 1.61993408203 msecs 
get_deltas_token2: 1.52525019646 msecs 
get_deltas_hughdbrown: 3.27240777016 msecs 
get_deltas_aas: 1.39379096031 msecs 

我用來做定時的代碼是here。我很高興與時間框架上我一起投入的時間框架。在重構運行測試的代碼之後，在未來應該很有用。

Answer 5

你也可以使用相同的算法，因爲我上面寫的，只使用一個單一的HashMap中。

def findDelta1(today,yesterday): 
results = {} 
ypos = 0 
for i,title in enumerate(today): 
     if title in results: 
      results[title] = results[title] - i 
     else: 
      for ypos in xrange(ypos,len(yesterday)): 
       if yesterday[ypos] == title: 
        results[title] = ypos - i 
        ypos = ypos + 1 
        break 
       else: 
        results[yesterday[ypos]] = ypos 
return results 

仍然O（N），可能比我上面的版本更快和更少的RAM。

Answer 6

>>> def transform(albums): 
...  return dict((album, i) for i, album in enumerate(albums)) 
... 
>>> def show_diffs(album1, album2): 
...  album_dict1, album_dict2 = transform(album1), transform(album2) 
...  for k, v in sorted(album_dict1.iteritems()): 
...   print k, album_dict2[k] - v 
... 
>>> albums_today = ['album1', 'album2', 'album3'] 
>>> albums_yesterday = ['album2', 'album1', 'album3'] 
>>> show_diffs(albums_today, albums_yesterday) 
album1 1 
album2 -1 
album3 0 

Answer 7

>>> albums_today = ['album1', 'album2', 'album3'] 
>>> albums_yesterday = ['album2', 'album1', 'album3'] 
>>> D = dict((k,v) for v,k in enumerate(albums_yesterday)) 
>>> dict((k,D[k]-v) for v,k in enumerate(albums_today)) 
{'album1': 1, 'album3': 0, 'album2': -1} 

在Python2.7或Python3它甚至可以更簡單地寫成

>>> albums_today = ['album1', 'album2', 'album3'] 
>>> albums_yesterday = ['album2', 'album1', 'album3'] 
>>> D = {k:v for v,k in enumerate(albums_yesterday)} 
>>> {k:D[k]-v for v,k in enumerate(albums_today)} 
{'album1': 1, 'album3': 0, 'album2': -1}