Сравнение списка Python: может ли этот код работать быстрее?


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

Мое текущее решение работает, но не достаточно быстро. работает "питон-м cProfile" дает СТГ. как:

  ncalls    tottime  percall  cumtime  percall filename:lineno(function)
  2412505   13.335   0.000    23.633   0.000   common.py:38(<genexpr>)
  285000    5.434    0.000    29.067   0.000   common.py:37(to_dict)
  142500    3.392    0.000    35.948   0.000   common.py:3(compare_lists)

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

import itertools

def compare_lists(li1, li2, value_func1=None, value_func2=None):
    """ Compare *li1* and *li2*, return the results as a list in the following form:

    [[data seen in both lists], [data only seen in li1], [data only seen in li2]]

    and [data seen in both lists] contains 2 tuple: [(actual items in li1), (actual items in li2)]

    * *value_func1* callback function to li1, applied to each item in the list, returning the **logical** value for comparison
    * *value_func2* callback function to li2, similarly

    If not supplied, lists will be compared as it is.

    Usage::

        >>> compare_lists([1, 2, 3], [1, 3, 5])
        >>> ([(1, 3), (1, 3)], [2], [5])

    Or with callback functions specified::

        >>> f = lambda x: x['v']
        >>>
        >>> li1 = [{'v': 1}, {'v': 2}, {'v': 3}]
        >>> li2 = [1, 3, 5]
        >>>
        >>> compare_lists(li1, li2, value_func1=f)
        >>> ([({'v': 1}, {'v': 3}), (1, 3)], [{'v': 2}], [5])

    """

    if not value_func1:
        value_func1 = (lambda x:x)
    if not value_func2:
        value_func2 = (lambda x:x)

    def to_dict(li, vfunc):
        return dict((k, list(g)) for k, g in itertools.groupby(li, vfunc))

    def flatten(li):
        return reduce(list.__add__, li) if li else []

    d1 = to_dict(li1, value_func1)
    d2 = to_dict(li2, value_func2)

    if d1 == d2:
        return (li1, li2), [], []

    k1 = set(d1.keys())
    k2 = set(d2.keys())

    elems_left  = flatten([d1[k] for k in k1 - k2])
    elems_right = flatten([d2[k] for k in k2 - k1])

    common_keys = k1 & k2
    elems_both  = flatten([d1[k] for k in common_keys]), flatten([d2[k] for k in common_keys])

    return elems_both, elems_left, elems_right

Редактировать:

zeekay предлагает использовать набор, который является также то, что я делаю, за исключением того, что я делаю дикт для каждого списка, а затем сравнить ключей, используя набор, наконец, вернуть оригинальные элементы с помощью дикт. Я понял, что скорость на самом деле зависит от того, кто займет больше времени-функция обратного вызова, или метода groupBy. В моем случае, возможные функции обратного вызова в основном точка доступа на объектах, а протяженность списки могут быть большими вызывая groupBy на ристалище занимает больше времени.

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

def compare_lists(li1, li2, vf1=None, vf2=None):
    l1 = map(vf1, li1) if vf1 else li1
    l2 = map(vf2, li2) if vf2 else li2

    s1, s2 = set(l1), set(l2)
    both, left, right = s1 & s2, s1 - s2, s2 - s1

    orig_both = list((x for x in li1 if vf1(x) in both) if vf1 else both), list((x for x in li2 if vf2(x) in both) if vf2 else both)
    orig_left = list((x for x in li1 if vf1(x) in left) if vf1 else left)
    orig_right = list((x for x in li2 if vf2(x) in right) if vf2 else right)

    return orig_both, orig_left, orig_right


3214
5
задан 12 сентября 2011 в 08:09 Источник Поделиться
Комментарии
3 ответа

Так что, похоже, вы в первую очередь хотите использовать функции обратного вызова, чтобы вытащить значение, чтобы сравнить из объекта, если вы не против упрощения, как сравнивать предметы будут возвращены, быстрее и проще будет:

def simple_compare(li1, li2, value_func1=None, value_func2=None):
s1, s2 = set(map(value_func1, li1)), set(map(value_func2, li2))
common = s1.intersection(s2)
s1_diff, s2_diff = s1.difference(s2), s2.difference(s1)
return common, s1_diff, s2_diff

>>> simple_compare(li1, li2, value_func1=f)
<<< (set([1, 3]), set([2]), set([5]))

>>> compare_lists(li1, li2, value_func1=f)
<<< (([{'v': 1}, {'v': 3}], [1, 3]), [{'v': 2}], [5])

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

>>> timeit x = simple_compare(xrange(10000), xrange(10000))
100 loops, best of 3: 2.3 ms per loop

>>> timeit x = compare_lists(xrange(10000), xrange(10000))
10 loops, best of 3: 53.1 ms per loop

2
ответ дан 12 сентября 2011 в 09:09 Источник Поделиться

Если вы действительно пытаетесь делать комплекты, а не через список, как мешок посмотрите на этот код

a = [1,2,3]
b = [2,3,4]

print list (set(a) - set(b))
print list (set(b) - set(a))
print list (set(a) & set(b))
print list (set(a) | set(b))
print list (set(a) ^ set(b))

=========

Выход

[1]
[4]
[2, 3]
[1, 2, 3, 4]
[1, 4]

1
ответ дан 12 сентября 2011 в 10:09 Источник Поделиться

Если на счету материи, то вам нужно использовать счетчик класса из коллекции

from collections import Counter

a = [1,1,2,3,3]
b = [1,3,4,4]

print "a ",a
print "b ",b
print "union ", list ((Counter(a) | Counter(b)).elements())
print "a not b", list ((Counter(a) - Counter(b)).elements())
print "b not a", list ((Counter(b) - Counter(a)).elements())
print "b and a", list ((Counter(b) & Counter(a)).elements())

что дает этот ответ

a       [1, 1, 2, 3, 3]
b [1, 3, 4, 4]
union [1, 1, 2, 3, 3, 4, 4]
a not b [1, 2, 3]
b not a [4, 4]
b and a [1, 3]

Всегда лучше использовать встроенные, а не писать свой собственный

0
ответ дан 14 сентября 2011 в 08:09 Источник Поделиться