Определение наиболее эффективного решения нахождения общих элементов двух списков

Question

Задача:

a, b - списки, отсортированные по возрастанию. Вернуть список c, содержащий только те элементы из a, которые есть в b. Решение должно быть вычислительно эффективным.

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

Решения:

Вариант 1:

def get_intersection(a, b):
    a = set(a)
    b = set(b)
    c = sorted(list(a&b))
    return c

Вариант 2:

def get_list_difference(a, b):
    l = []
    for i in a:
        if i in b:
            l.append(i)
    return l

Answer 1

Разницу в производительности можно измерить например с помощью библиотеки timeit.

>>> a = [1,2,3,4,5]
>>> b = [3,5,7,8]
>>> 
>>> set(a) & set(b)
{3, 5}
>>> 
>>> import timeit
>>> 
>>> print(timeit.timeit('sorted(list(set([1,2,3,4,5]) & set([3,5,7,8])))', number=10000))
0.0662280490005287
>>> print(timeit.timeit('set([1,2,3,4,5]) & set([3,5,7,8])', number=10000))
0.04045701100039878
>>>

Answer 2

По вычислительной сложности

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

По Вашему примеру. Если где ошибаюсь, то надеюсь коллеги поправят.

Вариант 1) Если преобразуем список (list) в множество (set), то стоимость операции O(n). Далее пересечение O(min(len(s), len(t)), если равны, то O(n), а потом снова в преобразуем список O(n). И последнее сортировка списка O(n log n). Итого в худшем случае O(n) + O(n) + O(n) + O(n) + O(n) + O(n log n)

Вариант 2) Первый цикл O(n), попадание в список O(n), append() со стоимостью одной операции O(1). Где-то итого приблизительно будет O(n^2) + O(n)

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

Протестировать

Протестировать все это можно с помощью timeit или библиотеки timench. Пример кода для второй в этом гисте по ссылке https://gist.github.com/ndrwpvlv/d011e129ffdb3816caad8dff74517e86. Там же внизу результаты для упорядоченных и случайных списков длиной три ячейки и тысяча. С ростом длины соответственно вариант с множествами дает меньше временных затрат.

По timeit примеры в соседнем посте.

По оптимальному варианту. На мой взгляд, если нужна сортировка, то чуть эффективнее будет

sorted(set(a).intersection(b))

Answer 3

Оптимально будет использовать алгоритм двух указателей:

def get_intersection(a, b):
    c = []
    u = 0
    for i in range(len(a)):
        while u < len(b) and b[u] < a[i]:
            u += 1
        if u == len(b):
            break
        if a[i] == b[u]:
            c.append(a[i])
    return c

a = [0, 1, 1, 2, 5, 7, 10]
b = [-1, 1, 3, 7, 9, 12]
print(get_intersection(a, b))
# [1, 1, 7]

Этот алгоритм проходит по каждому элементу из двух массивов не более одного раза, поэтому должен быть побыстрее множеств. Сложность - O(len(a) + len(b)), то есть O(N).

Ваши решения имеют сложности O(NlogN) и O(N^2) соответственно. Первый использует сортировку, второй - по сути двойной цикл.

Answer 4

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

def get_intersect(a, b):
    c = []
    ia = ib = 0
    if not a or not b:
        return c
    while True:
        if a[ia] == b[ib]:
            c.append(a[ia])
            ia += 1
            ib += 1
            if ia >= len(a) or ib >= len(b):
                return c
        while a[ia] < b[ib]:
            ia += 1
            if ia >= len(a):
                return c
        while a[ia] > b[ib]:
            ib += 1
            if ib >= len(b):
                return c

БЛОГ НА HUSL

Определение наиболее эффективного решения нахождения общих элементов двух списков

Ответы (4 шт):