Быстрый алгоритм расчета дельты двух списков

Question

У меня есть два списка названий альбомов, упорядоченных по некоторой оценке.

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

Как я могу рассчитать изменение порядка списка и получить что-то вроде

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

Answer 1

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

Answer 2

Вы также можете использовать тот же алгоритм, который я написал выше, и просто использовать одну хэш-карту.

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), потенциально быстрее и меньше оперативной памяти, чем моя версия выше.

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

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

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

Answer 6

Новое и улучшенное, а не 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 порядок действует.Если кто-то хочет, чтобы я как-то изменил их код, просто пингуйте меня.

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

Код, который я использовал для определения времени: здесь .Я доволен временной структурой, которую я подбросил вместе для этого.Должно быть полезно в будущем после рефакторинга кода для запуска тестов.

Answer 7

Ну, в зависимости от размеров ваших списков, существует ряд различных подходов.не зная, насколько велики ваши наборы данных, я бы предположил, что самый простой (возможно, излишне оптимизированный) метод это что-то вроде:

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