быстрое сравнение данных в python

Question

Я хочу сравнить большой набор данных в виде 2 словарей различной длины. (Редактирование)

post = {0: [0.96180319786071777, 0.37529754638671875], 
        10: [0.20612385869026184, 0.17849941551685333],
        20: [0.20612400770187378, 0.17510984838008881],...}

pre = {0: [0.96180319786071777, 0.37529754638671875],
       1: [0.20612385869026184, 0.17849941551685333],
       2: [0.20612400770187378, 0.17510984838008881],
       5065: [0.80861318111419678, 0.76381617784500122],...}

Ответ, который нам нужно получить, - 5065: [0.80861318111419678, 0.76381617784500122]. Это основано на том факте, что мы сравниваем только значения, а не индексы вообще.

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

Код, который я использую, очень прост ..

new = {}
found = []

for i in range(0, len(post)): 
    found= []
    for j in range(0, len(pre)): 
        if post[i] not in pre.values():
            if post[i] not in new:
                new[i] = post[i]
                found.append(j)             
                break
    if found:
        for f in found: pre.pop(f)

new {} содержит элементы, которые мне нужны. Проблема, с которой я сталкиваюсь, заключается в том, что этот процесс слишком медленный. Иногда это занимает больше часа, чтобы обработать. Данные могут быть намного больше в разы. Мне нужно, чтобы это было быстрее.

Есть ли эффективный способ сделать то, чего я пытаюсь достичь? Мне бы хотелось, чтобы мы не зависели от внешних пакетов, кроме тех, которые связаны с Python 2.5 (64-битная версия), за исключением случаев, когда это абсолютно необходимо.

Спасибо всем.

Answer 1

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

post_set = set(tuple(x) for x in post.itervalues())
pre_set = set(tuple(x) for x in pre.itervalues())

items_in_only_one_set = post_set ^ pre_set

Для получения дополнительной информации о set с: http://docs.python.org/library/stdtypes.html#set

Комуполучить исходные индексы после того, как вы вычислили различия; вам, вероятно, понадобится сгенерировать таблицы обратного просмотра:

post_indices = dict((tuple(v),k) for k,v in post.iteritems())
pre_indices = dict((tuple(v),k) for k,v in pre.iteritems())

Затем вы можете просто взять данный кортеж и посмотреть его индекс через словари.:

index = post_indices.get(a_tuple, pre_indices.get(a_tuple))

Answer 2

Вероятно, ваша проблема связана с вложенными циклами for в сочетании с использованием range(), который каждый раз создает новый list, который может быть медленным.Скорее всего, вы получите автоматическое ускорение, выполнив итерации pre и post напрямую, и не будете делать это вложенным способом.

post = {0: [0.96180319786071777, 0.37529754638671875],
       10: [0.20612385869026184, 0.17849941551685333],
       20: [0.20612400770187378, 0.17510984838008881]}

pre = {0: [0.96180319786071777, 0.37529754638671875],
       1: [0.20612385869026184, 0.17849941551685333],
       2: [0.20612400770187378, 0.17510984838008881],
    5065: [0.80861318111419678, 0.76381617784500122]}

'''Create sets of values, independent of dict key for O(1) lookup'''
post_set=set(map(tuple, post.values()))
pre_set=set(map(tuple, pre.values()))

'''Iterate through each structure only once, filtering items that are found in
   the sets we created earlier, updating new_diff'''
from itertools import ifilterfalse

new_diff=dict(ifilterfalse(lambda x: tuple(x[1]) in pre_set, post.items()))
new_diff.update(ifilterfalse(lambda x: tuple(x[1]) in post_set, pre.items()))

new_diff теперь dict, так что каждое значениене найдено ни в post, ни в pre, с сохранением исходного индекса.

>>> print new_diff
{5065: [0.80861318111419678, 0.76381617784500122]}