快速算法计算出的两个列表

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}