2つのリストのデルタを計算する高速アルゴリズム

Question

私はいくつかのスコアで順序付けられたアルバム名の2つのリストを持っています。

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

のようなものを取得します。 O（N）として実行されます

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); 

：あなたのデータセットはどのように大きな知らなくても、私は最も簡単な（多分不必要に最適化された）メソッドのようなものであることをお勧めしたいです。だけに物事を見て、単一の辞書を作成し

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) 

：どのようにこの程度

Answer 3

。

両方のリストのすべてのエントリがそれぞれ正確に1回存在する限り、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は）：しかし、まだ他の回答のより遅い2。

このソリューションの唯一の利点は、メモリの節約です。それは大きな辞書を構築することを避け、その時に必要なものだけを保存します。 TokenMacGuyの2番目の解決策も同様ですが、これはやや速いです。

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

私は上記と同じアルゴリズムを使用して、単一のハッシュマップを使用することもできます。

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が少ない可能性があります。 Python2.7かのpython3で

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} 

それはこれは私が現在使用しているアルゴリズムであっても、より簡単に

>>> 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}