Питонное повторяемое различие

Question

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

def differences(a_iter, b_iter):
    a_items, b_items = set(), set()

    def remove_or_add_if_none(a_item, b_item, a_set, b_set):
        if a_item is None:
            if b_item in a_set:
                a_set.remove(b_item)
            else:
                b_set.add(b)

    def remove_or_add(a_item, b_item, a_set, b_set):
        if a in b_set:
            b_set.remove(a)
            if b in a_set:
                a_set.remove(b)
            else:
                b_set.add(b)
            return True
        return False

    for a, b in itertools.izip_longest(a_iter, b_iter):
        if a is None or b is None:
            remove_or_add_if_none(a, b, a_items, b_items)
            remove_or_add_if_none(b, a, b_items, a_items)
            continue

        if a != b:
            if remove_or_add(a, b, a_items, b_items) or \
               remove_or_add(b, a, b_items, a_items):
                continue
            a_items.add(a)
            b_items.add(b)

    return a_items, b_items

Тем не менее, приведенный выше код не выглядит слишком питонным, поэтому я ищу альтернативы или предложения по улучшению.

Answer 1

Вот более питоническое решение:

a, b = set(a_iter), set(b_iter)

return a - b, b - a

Pythonic означает не быстрый, а скорее элегантный и читабельный.

Вот решение, которое может быть быстрее:

a, b = set(a_iter), set(b_iter)

# Get all the candidate return values
symdif = a.symmetric_difference(b)

# Since symdif has much fewer elements, these might be faster
return symdif - b, symdif - a

Теперь о написании пользовательских «быстрых» алгоритмов на Python вместо использования встроенных операций: это очень плохая идея.

Операторы множеств сильно оптимизированы и написаны на C, что, как правило, намного, намного быстрее, чем Python. Вы можете написать алгоритм на C (или Cython), но помните, что алгоритмы множеств Python были написаны и оптимизированы гениями мирового класса. Если вы не очень хороши в оптимизации, это, вероятно, не стоит усилий. С другой стороны, если вам удастся существенно ускорить процесс, поделитесь кодом; Могу поспорить, что у него будет шанс попасть в сам Python.

Для более реалистичного подхода попробуйте исключить вызовы кода Python. Например, если у ваших объектов есть пользовательский оператор равенства, найдите способ его удалить.

Но не надейтесь. Работа с миллионами фрагментов данных всегда займет много времени. Я не знаю, где вы это используете, но, может быть, лучше заняться компьютером на минуту, чем тратить время на оптимизацию алгоритмов набора?

Answer 2

Я бы подумал, что операции с наборами python будут наилучшей производительностью, которую вы можете получить из стандартной библиотеки.

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

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

Так, например, я использую NumPy , числовую библиотеку python, для таких задач:

# a, b are 'fake' index arrays of type boolean
import numpy as NP
a, b  = NP.random.randint(0, 2, 10), NP.random.randint(0, 2, 10)
a, b = NP.array(a, dtype=bool), NP.array(b, dtype=bool)

# items a and b have in common:
NP.sum(NP.logical_and(a, b))

# the converse (the differences)
NP.sum(NP.logical_or(a, b))

Answer 3

я думаю, что ваш код не работает - попробуйте его с [1,1] и [1,2], и вы получите, что 1 в одном наборе, но не в другом.

> print differences([1,1],[1,2])                                                   
(set([1]), set([2]))

Вы можете проследить это до результата теста if a != b (который предполагает что-то в отношении порядка, которого нет в простых различиях наборов).

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