Блог

O (n) поскольку преобразование списка в set занимает O (n) времени, получение пересечения занимает O (n) времени, а len равен O (n)

 def disjoint3c(A, B, C):
    """Return True if there is no element common to all three lists."""
    return len(set(A) amp; set(B) amp; set(C)) == 0
 

или аналогично, должно быть явно O (N)

 def set_disjoint_medium (a, b, c):
    a, b, c = set(a), set(b), set(c)
    for elem in a:
        if elem in b and elem in c:
            return False
    return True
 

тем не менее, этот код O (n ^ 3):

 def set_disjoint_slowest (a, b, c):
    for e1 in a:
        for e2 in b:
            for e3 in c:
                if e1 == e2 == e3:
                    return False
    return True
 

работает быстрее

смотрите время, когда алгоритм один — это n ^ 3, а алгоритм три — это код O (n) набора … алгоритм два на самом деле n ^ 2, где мы оптимизируем алгоритм один, проверяя разобщенность перед запуском третьего цикла

 Size Input (n):  10000

Algorithm One: 0.014993906021118164

Algorithm Two: 0.013481855392456055

Algorithm Three: 0.01955580711364746

Size Input (n):  100000

Algorithm One: 0.15916991233825684

Algorithm Two: 0.1279449462890625

Algorithm Three: 0.18677806854248047

Size Input (n):  1000000

Algorithm One: 1.581618070602417

Algorithm Two: 1.146049976348877

Algorithm Three: 1.8179030418395996
 

В комментариях были даны разъяснения по поводу обозначений Big-Oh. Итак, я просто начну с тестирования кода.

Вот настройка, которую я использовал для тестирования скорости кода.

 import random

# Collapsed these because already known
def disjoint3c(A, B, C):
def set_disjoint_medium (a, b, c):
def set_disjoint_slowest (a, b, c):

a = [random.randrange(100) for i in xrange(10000)]
b = [random.randrange(100) for i in xrange(10000)]
c = [random.randrange(100) for i in xrange(10000)]

# Ran timeit.
# Results with timeit module.
1-) 0.00635750419422
2-) 0.0061145967287
3-) 0.0487953200969
 

Теперь к результатам, как вы видите, O(n^3) решение выполняется в 8 раз медленнее, чем другие решения. Но это все равно быстро для такого алгоритма (даже быстрее в вашем тесте). Почему это происходит?

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

Чтобы проверить это, вы могли бы создать списки, подобные этому. Попробуйте это сами.

 a = range(1000)
b = range(1000, 2000)
c = range(2000, 3000)
 

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

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

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

 def mysol(a, b, c):
    store = [set(), set(), set()]

    # zip_longest for Python3, not izip_longest.
    for i, j, k in itertools.izip_longest(a, b, c):
        if i: store[0].add(i)
        if j: store[1].add(j)
        if k: store[2].add(k)

        if (i in store[1] and i in store[2]) or (j in store[0] and i in store[2]) or (k in store[0] and i in store[1]):
            return False
    return True
 

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

Что касается скоростей, это выполняется в 3-4 раза медленнее, чем ваши первые два решения в худшем случае. Но работает в 4-10 раз быстрее, чем эти решения в рандомизированных списках.

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

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

С интерпретируемыми языками, такими как Python и R, постоянные коэффициенты могут быть довольно большими. Им нужно создавать и собирать много объектов, а это все O (1), но не бесплатно. К сожалению, довольно часто можно увидеть 100-кратную разницу в производительности практически эквивалентного кода.

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

Я бы не удивился, увидев, что алгоритм O (n log n), основанный на сортировке, является очень конкурентоспособным (потому что сортировка обычно невероятно хорошо оптимизирована). Для целых чисел я бы использовал массивы numpy, и, избегая интерпретатора python, насколько это возможно, вы можете получить очень быстрый результат. В то время как in1d numpys и intersect , скорее всего, дадут вам алгоритм O (n ^ 2) или O (n ^ 3), они могут оказаться быстрее, если ваши наборы обычно не пересекаются.

Также обратите внимание, что в вашем случае наборы не обязательно будут попарно непересекающимися … algX(set(),a,a)==True .