Почему реализация maxmin делит и побеждает медленнее, чем другие алгоритмы maxmin?

Question

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

грубой реализации силы ниже:

def maxmin1(vetor): 
    max,min = vetor[0],vetor[0]; 
    for elem in vetor[1:]: 
     if elem > max: 
      max = elem 
     if elem < min: 
      min = elem 
    return (min,max) 

и разделяй и властвуй реализации ниже:

def maxmin4(vetor,inicio,fim): 
    if ((fim - inicio) == 1): 
     return (vetor[inicio], vetor[inicio]) 
    elif ((fim - inicio) == 2): 
     if(vetor[inicio] < vetor[inicio+1]): 
      return (vetor[inicio], vetor[inicio+1]) 
     else: 
      return (vetor[inicio+1], vetor[inicio]) 
    else: 
     (min_left,max_left) = maxmin4(vetor,inicio,(fim-inicio)/2 + inicio) 
     (min_right,max_right) = maxmin4(vetor,(fim-inicio)/2 + inicio,fim) 
     if (max_left < max_right): 
      max = max_right 
     else: 
      max = max_left 
     if (min_left < min_right): 
      min = min_left 
     else: 
      min = min_right 
    return (min,max) 

и результаты:

input N  time algorithm 1 | time algorithm 2 
1000000 | 0.1299650669  | 0.6347620487 
2000000 | 0.266600132  | 1.3034451008 
3000000 | 0.393116951  | 2.2436430454 
4000000 | 0.5371210575  | 2.5098109245 
5000000 | 0.6094739437  | 3.4496300221 
6000000 | 0.8271648884  | 4.6163318157 
7000000 | 1.0598180294  | 4.8950240612 
8000000 | 1.053456068  | 5.1900761128 
9000000 | 1.1843969822  | 5.6422820091 
10000000| 1.361964941  | 6.9290060997 

Я не underst и почему первый алгоритм был быстрее второго, так как первые имеют сложность 2 (n -1), а вторая имеют сложность 3n/2 -2, а теоретически первая медленнее второй. почему так происходит?

Answer 1

Я был бы очень удивлен см. Рекурсия Python выполняется быстрее, чем итерация на Python. Попробуйте эту реализацию maxmin, взяв по два значения за раз.

def minmax(seq): 

    def byTwos(seq): 
     # yield values from sequence two at a time 
     # if an odd number of values, just return 
     # the last value twice (won't hurt minmax 
     # evaluation) 
     seq = iter(seq) 
     while 1: 
      last = next(seq) 
      yield last,next(seq,last) 

    seqByTwos = byTwos(seq) 
    # initialize minval and maxval 
    a,b = next(seqByTwos,(None,None)) 
    if a < b: 
     minval,maxval = a,b 
    else: 
     minval,maxval = b,a 

    # now walk the rest of the sequence 
    for a,b in seqByTwos: 
     if a < b: 
      if a < minval: 
       minval = a 
      if b > maxval: 
       maxval = b 
     else: 
      if b < minval: 
       minval = b 
      if a > maxval: 
       maxval = a 
    return minval, maxval 

Если вы хотите считать сравнения, а затем передать последовательность объектов, реализующих __lt__ и __gt__, и есть те методы обновления глобального счетчика.

Answer 2

Как оказалось, в вашем коде есть ошибка или ошибка в анализе, но это не имеет значения. Я доберусь до конца.

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

---

Вполне возможно, что это всего лишь артефакт Тестируете такой узкий диапазон, только один фактор 10. Но работает тесты с более широким диапазоном значений, например:

for i in 100, 1000, 10000, 100000, 1000000, 10000000: 
    v = [random.random() for _ in range(i)] 
    t1 = timeit.timeit(lambda: maxmin1(v), number=1) 
    t2 = timeit.timeit(lambda: maxmin4(v, 0, len(v)), number=1) 
    print('{:8}: {:.8f} {:.8f} (x{:.8f})'.format(i, t1, t2, t2/t1)) 

... вы можете увидеть, что картина держит:

 100: 0.00002003 0.00010014 (x5.00000000) 
    1000: 0.00017500 0.00080800 (x4.61716621) 
    10000: 0.00172400 0.00821304 (x4.76393307) 
    100000: 0.01630187 0.08839488 (x5.42237660) 
1000000: 0.17010999 0.76053309 (x4.47083153) 
10000000: 1.77093697 8.32503319 (x4.70092010) 

---

Итак, почему выше константа над головой во втором ве rsion? Ну, первая версия просто выполняет простую нумерацию for, два сравнения и 1 назначение для каждого элемента. Второе - это вызов функций, построение и взорвание кортежей, выполнение большего количества сравнений и т. Д. Это неизбежно будет медленнее. Если вы хотите узнать, почему он ровно в 5 раз медленнее (или, на самом деле, на 15 раз медленнее, если вы делаете 2n/3 шага вместо 2n), вам нужно будет выполнить профилирование или, по крайней мере, посмотреть на байт-код. Но я не думаю, что это того стоит.

---

Мораль этой истории в том, что есть причина, 2 (п-1) и 2л/3-2 оба O (п): Когда у вас есть два различных класса сложности, как O (п) и O (n ** 2), что всегда будет иметь значение для больших n; когда у вас есть два алгоритма в одном классе, константы в реализации (стоимость каждого шага) могут легко перевесить константы в счетчике шагов.

---

Между тем, как мы можем проверить анализ 2n/3-2? Простой, просто добавьте глобальный счетчик, который вы увеличиваете один раз для каждого вызова до maxmin4.Вот ожидаемые и фактические результаты:

 100:   65  127 
    1000:  665  1023 
    10000:  6665  11807 
    100000:  66665  131071 
1000000:  666665 1048575 
10000000: 6666665 11611391 

Но это просто означает, что вы делаете около 2/3rds, как много шагов, а не о 1/3rd, поэтому постоянная стоимость каждых шагов 7.5x, а не 15 раз , В конце концов, это не влияет на анализ.

Answer 3

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

В вашем случае вы выполняете около 4 или 5 операций для около n/2 вызовов функций (листовые узлы двоичного дерева вызовов функций) и около 16 операций для внутренних узлов (считая все назначения, арифметические операции, сравнения и кортежи). Это составляет около 10% общего объема операций.

В первой программе общее число операций по существу равно 2.x * n (где x зависит от количества выполненных заданий).

Это, наряду с относительной простотой операций в программе 1 по программе 2, приводит к коэффициенту 5, наблюдаемому в двух программах.

Кроме того, количество сравнений по алгоритму деления и покоя должно быть 3n/2, а не 2n/3.