Функциональный подход к алгоритму сортировки слиянием

1656621278 funkczionalnyj podhod k algoritmu sortirovki sliyaniem

Джо Чейзинга

yOEzzeaSsJspQoc6e7VvAqK3lxDt-gUfnbm2
Фото Рикардо Гомеса Ангела на Unsplash

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

Очень часто суть алгоритма (как вы решаете конкретную проблему логически без компьютерной кодировки) выглядит очень просто и понятно, если описывать ее графически. Как ни странно, но он часто плохо переводится в код, написанный на таких языках, как Python, Java или C++. Потому понять становится гораздо сложнее.

Другими словами, алгоритмическая концепция не отображает непосредственно способ написания и чтения кода.

Почему алгоритмы так трудно кодировать?

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

Что еще хуже, кроме языков микроуправления, кому пришлось изобрести API для лучшего микроуправления. Они назвали это объектно-ориентированным программированием (ООП) и добавили концепцию классов к программированию, но я думаю, что модули и функции могли бы справляться с теми же вещами, очень спасибо.

C++ не сделал C лучше, но проложил путь, вдохновляя больше потомков ООП. И все вместе, все это усложняет отвлеченное алгоритмическое мышление по вышеупомянутым причинам.

Пример: сортировка слиянием

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

ZcTwK7oDpCLBjTjYrP-3ZlnUCSWe7EkYj7Zb
Автор Swfung8 — Собственная работа, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=14961648

Ключевые шаги по созданию сортировки слиянием немногочисленны и просты. На самом деле я могу объяснить это, используя числовые блоки моей дочери (полезно следовать этим, возвращаясь к анимированной диаграмме для справки):

  • Во-первых, нам нужно продолжать разбивать список чисел (либо букв, либо любых типов сортируемых значений) пополам, пока мы не получим много одноэлементных списков. Список с одним элементом технически отсортирован. Это называется тривиально отсортированным.
  • Затем мы создаем новый пустой список, в котором мы можем начать переупорядочивать элементы и размещать их один за другим, согласно которому один меньше/меньше другого.
  • Затем нам нужно «соединить» каждую пару списков вместе, фактически отменив шаги разделения. Но на этот раз на каждом шагу мы должны убедиться, что меньший элемент в паре, о котором идет речь, сначала помещается в пустой список.

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

def merge(a, b):
    out = []

    while (len(a) > 0 and len(b) > 0): 
        if (a[0] <= b[0]):
            out.append(a[0])
            del a[0]
        else:
            out.append(b[0])
            del b[0]

    while (len(a) > 0):
        out.append(a[0])
        del a[0]
    while (len(b) > 0):
        out.append(b[0])
        del b[0]

    return out

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

Наша первая попытка

Вот одна попытка (которую вы могли бы использовать во время сеанса работы с доской):

Чтобы объединить список a и bнам нужно сначала создать пустой список с ним out для ясности (поскольку в Python мы не можем быть уверены, что он действительно выйдет). Тогда пока (или пока) оба списка не будут пустыми, мы будем продолжать бороться за голову обоих списков. Побеждает тот, кто меньше или равен противнику и получает право войти out сначала. Побежденному придется остаться и ждать нового участника. Матчи-реванши продолжаются до первого while разрывы цикла.

Сейчас тоже в какой-то момент a или b будет пустым, а в остальном останется один или несколько элементов. В другом списке не осталось ни одного участника, двух while циклы обязательно быстро отслеживают эти бедные элементы out поэтому оба списка исчерпаны. Затем, когда все это будет сделано, мы возвращаемся out.

И это тестовые случаи для слияния:

assert(merge([1], [2]) == [1, 2])
assert(merge([2], [1]) == [1, 2])
assert(merge([4, 1], [3, 0, 2]) == [3, 0, 2, 4, 1])

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

Разделяй и властвуй

Теперь перейдем в раздел. Этот процесс также известен как разделение или, несколько более грандиозным языком, разделяй и властвуй (кстати, определение в политике не менее интересно).

7r1BOCtjx7Z261gFldhvdk6sxqLYy0xGpe57
Золотой медальон Филиппа II Македонского, который, как говорится, придумал максиму divide et impera (разделяй и властвуй). Национальная библиотека Франции, Париж

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

def half(arr):
    mid = len(arr) / 2
    return arr[:mid], arr[mid:]

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

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

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

Одна очевидная ирония заключается в том, что даже в языке с итеративным циклом, как Python, он все равно не может полностью избежать рекурсии (это может обойтись без рекурсии, но я уверен, что это сделает это еще более странным). Рекурсия – это территория, где итерационные конструкции, такие как циклы for и while, становятся совершенно бесполезными.

Более того, рекурсия не является естественной в Python. Он не выглядит естественным и прозрачным, а скорее чувствует себя полуготовым, как его лямбда. Попытка озвучить рекурсии в Python могла бы выглядеть так: «тогда мы делаем это рекурсивно и молимся, чтобы все удалось и в конце концов попало в базовый регистр, чтобы он не попал в бесконечную тьму переполнения стека». Вау, верно?

Итак, вот mergesort функция:

def mergesort(arr):

    if (len(arr) <= 1):
        return arr

    left, right = half(arr)
    L = mergesort(left)
    R = mergesort(right)

    return merge(L, R)

По-видимому, это действительно чисто и легко читается. Но непонятно, что произойдет после звонка half , по крайней мере, семантически. Из-за этой «неродности» рекурсии рекурсивные вызовы очень непрозрачны и мешают учебным усилиям.

Единственный способ представить этот процесс сортировки слиянием, вероятно, – это отслеживать изменения в подсписках на каждом шагу:

input: [0, 3, 1, 3, 2, 6, 5]
A alias for mergesort / half
B alias for merge

## subdividing by half ...

                 A([0, 3, 1, 3, 2, 6, 5])
              A([0, 3, 1])    A([3, 2, 6, 5])
          A([0])  A([3, 1])  A([3, 2])   A([6, 5])
    A([]) A([0]) A([3])  A([1]) A([3]) A([2]) A([6]) A([5]) 

## base case reached, start merging ...

       B([], [0]) B([3], [1]) B([3], [2]) B([6], [5])
          B([0], [1, 3])         B([2, 3], [5, 6])
                B([0, 1, 3], [2, 3, 5, 6])
                 B([0, 1, 2, 3, 3, 5, 6])

output: [0, 1, 2, 3, 3, 5, 6]

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

Например, нужно примерно 3 шага, чтобы продолжать делить 10 на 2, пока оно не приблизится к 1, насколько это возможно (или ровно 3 шага, чтобы достичь 1 при целочисленном делении). Но нужно всего около 26 шагов, чтобы сделать то же самое и разделить 100 000 000 на 2, пока не достигнете 1. Этот факт можно выразить так:

2^3.321928 = 10
2^6.643856 = 100

...

2^26.575425 = 100000000

or 

log base 2 of 100000000 = 26.575425

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

Почему существует разрыв между концептуальными процессами самого алгоритма и кодом, предписывающим компьютеру вычислять такие процессы?

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

NEuX4NWEDEEpa2TikKqjT2ABx5kj8tPZk8A5
Не совсем так, но вы поняли суть.

Погрузитесь глубже в код

«Есть разница между знанием пути и хождением по пути».
― Морфеус, Матрица

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

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

Скажем, вы хотите создать базовый вариант для Python. В нем вы хотите вернуть соответствующий список, если он содержит только один элемент, и пустой список, если есть два элемента. Итак, вам нужно написать что-то вроде этого:

if (len(arr) == 1):
    return arr
elif (len(arr) == 2):
    return []

Или, чтобы сделать это хуже, но интереснее, вы можете попытаться получить доступ к первому элементу по индексу 0 и второму элементу по индексу 1 и подготовиться к обработке IndexError исключение.

В функциональном языке, как Erlang — которым я буду пользоваться в этой статье для ее системы динамических типов, таких как Python — вы более или менее сделали бы что-то подобное:

case Arr of
  [_] -> Arr;
  [_,_] -> []
end.

Это дает вам более ясное представление о состоянии данных. После того, как он достаточно обучен, он требует гораздо меньше когнитивных сил для чтения и понимания того, что делает код, чем len(arr) . Только имейте в виду: программист, не владеющий английским, может спросить: «Что такое len?» Тогда вы отвлекаетесь на буквальное значение функции вместо этого выражения.

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

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

merge([], [], Acc) -> Acc;
merge([], [H | T], Acc) -> [H | merge([], T, Acc)];
merge([H | T], [], Acc) -> [H | merge(T, [], Acc)];
merge([Ha | Ta], [Hb | Tb], Acc) ->
  case Ha =< Hb of
    true  -> [Ha | merge(Ta, [Hb | Tb], Acc)];
    false -> [Hb | merge([Ha | Ta], Tb, Acc)]
  end.

Какая гадость! Вы думаете, что это точно не улучшение с точки зрения читабельности. Да, Эрланг, правда, не получит никаких призов за красивый язык. На самом деле, многие функциональные языки могут выглядеть как тарабарство для неподготовленных глаз.

Но давайте дадим ему шанс. Мы пройдем каждый шаг по-прежнему, и, возможно, в конце концов кто-нибудь из нас увидит свет. Но прежде чем мы продолжим, для тех из вас, кто не знаком с Erlang, следует обратить внимание на некоторые моменты:

  • Каждый блок merge считается функцией той же функции. Они разделены ;. Когда выражение заканчивается на Erlang, оно заканчивается точкой (.). Это условно разделить функцию на несколько пунктов для разных случаев. Например, merge([], [], Acc) -> Aкуб.см; Предложение отображает случай, когда первые два аргумента являются пустыми списками на значение последнего аргумента.
  • Арити играет немаловажную роль в Эрланге. Две функции с одинаковым названием и арностью считаются одной и той же функцией. В противном случае они не есть. Например, merge/1 и merge/3 (как функции и их арность рассматриваются в Erlang) это две разные функции.
  • Erlang использует строгое соответствие шаблона (это используется во многих других функциональных языках, но особенно Erlang). Поскольку значения в чистых функциональных языках неизменны, безопасно связывать переменные в подобной форме данных к существующей форме с помощью соответствующей формы. Вот тривиальный пример:
{X, Y} = {0.5, 0.13}.
X.  %% 0.5
Y.  %% 0.13

[A, B, C | _] = [alice, jane, bob, kent, ollie].
[A, B, C].  %% [alice, jane, bob]
  • Обратите внимание, что мы редко будем говорить о возвращении значений, когда работаем с функциями Erlang, поскольку они действительно ничего не «возвращают» сами по себе. Он сопоставляет входящее значение с новым значением. Это не одно и то же, что вывести или вернуть его из функции. Сама программа функции есть значение. Например, если Add(N1, N2) -> N1+N2., Add(1, 2) равна 3. Нет никакого способа вернуть что-нибудь, кроме 3, поэтому мы можем сказать, что это 3. Вот почему вы можете легко do add_one = add(1) и then add_one(2) есть 3, add_one(5) равно 6 и так далее.

Для тех, кто заинтересован, смотрите ссылку на прозрачность. Чтобы сделать это более понятным и рисковать излишеством, вот над чем подумать:

когда f(x) является функцией с одной арностью, а отображение есть f(x) ->; x , то это окончательное that f(1) -&gt; 1, f(2) -> 2, f(3.1416) -> 3.1416, and f("foo») -> «foo».

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

a = 1
def add_to_a(b):
return b + a

Теперь a может быть что-нибудь раньше add_to_a вызывается. Таким образом, в Python вы можете написать чистую версию вышеприведенного как:

def add(a, b):
return a + b
или lambda a, b: a + b .

Теперь пора погрузиться в неизвестное.

Vg7C4II-2IY3Jx58NEN-nzHtSmVS9FwmWk6L
Так сказал Фрэнк О. Гэри.

Идя вперед с Эрлангом

merge([], [], Acc) -> Acc;

Первый пункт ст. merge/3 функция означает, что когда первые два аргумента являются пустыми списками, отображать все выражение на (или «возвращать») третий аргумент Acc.

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

здесь, Acc означает аккумулятор, который можно рассматривать как контейнер состояния. В случае merge/3, Acc это список, который начинается пустым. Но когда рекурсивные вызовы начинаются, он накапливает значение из первых двух списков, используя программируемую логику (о которой мы поговорим дальше).

Этот процесс исчерпания ценности для создания другой ценности совместно известен как уменьшение. Следовательно, в данном случае можно заключить, что поскольку первые два списка исчерпаны (пусты), Acc должно быть созревшим для сбора.

merge([], [H | T], Acc) -> [H | merge([], T, Acc)];

Второе предложение соответствует случаю, когда первый список уже пуст, но во втором списке все еще есть по крайней мере один элемент. [H | T] означает, что список имеет элемент head H какие минусы в другой список T. У Erlang список является связанным списком, а глава имеет указатель на остальной список. Итак, список [1, 2, 3, 4] можно рассматривать как:

%% match A, B, C, and D to 1, 2, 3, and 4, respectively

[A | [B | [C | [D | []]]]] = [1, 2, 3, 4].

В этом случае, как вы можете видеть на приведенном примере, T может быть просто пустым списком хвостов. Поэтому в этом втором случае мы сопоставляем его со значением нового списка, в котором H элемент второго списка связан с рекурсивным результатом вызова merge/3 когда T это второй довод.

merge([H | T], [], Acc) -> [H | merge(T, [], Acc)];

Третий случай является лишь обратной стороной второго случая. Это соответствует случаю, когда первый список не пуст, а второй есть. Это предложение отображает значение по аналогичному шаблону, за исключением того, что оно вызывает merge/3 с хвостом первого списка как первым доводом и оставляет второй список пустым.

merge([Ha | Ta], [Hb | Tb], Acc) ->
  case Ha =< Hb of
    true  -> [Ha | merge(Ta, [Hb | Tb], Acc)];
    false -> [Hb | merge([Ha | Ta], Tb, Acc)]
  end.

Начнём с мяса merge/3 сначала. Это предложение соответствует случаю, когда первый и второй аргументы являются пустыми списками. В этом случае мы вводим a case … of предложение (эквивалент переключения регистра на других языках), чтобы проверить, есть ли элемент head первого списка (Ha) меньше или равно главному элементу второго списка (Hb).

Если это правда, мы кон Ha в полученный список следующего рекурсивного вызова для слияния с хвостовым списком предыдущего первого списка (Ta) как новый первый аргумент. Второй и третий аргументы оставляем неизменными.

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

Однако для операции разделения, которая нуждается в двух функциях, все стало немного неровным: half/1 и half/3.

half([]) -> {[], []};
half([X]) -> {[X], []};
half([X,Y]) -> {[X], [Y]};
half(L) ->
  Len = length(L),
  half(L, {0, Len}, {[], []}).

half([], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse(Acc2)};
half([X], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse([X | Acc2])};
half([H|T], {Cnt, Len}, {Acc1, Acc2}) ->
  case Cnt >= (Len div 2) of
      true -> half(T, {Cnt + 1, Len}, {Acc1, [H|Acc2]});
      false -> half(T, {Cnt + 1, Len}, {[H|Acc1], Acc2})
  end.

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

Если ваш ум настроен на работу со связанными списками, вы больше придерживаетесь того, что «Я могу перейти только вперед через список, работая с несколькими элементами одновременно. Мне нужно создать два пустых списка и подсчитывать, сколько элементов я получил из исходного списка и поместил в первый, чтобы я знал, когда пора перейти к другому сегменту. Все вышеперечисленное нужно передать как аргументы в рекурсивных вызовах». Вау!

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

The half/1 функция, хотя она действительно не нужна, есть для удобства.

half([]) -> {[], []};
half([X]) -> {[X], []};
half([X,Y]) -> {[X], [Y]};
half(L) ->
  Len = length(L),
  half(L, {0, Len}, {[], []}).

Вы должны понять, что делает каждое предложение функции Erlang. Новые пары скобок здесь представляют кортежи в Erlang. Да, мы возвращаем левую и правую пару значений, как в версии Python. The half/1 функция предназначена для обработки простых, явных базовых случаев, не гарантирующих целесообразности передачи в других аргументах.

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

  • длина списка L и звонки half/3 с L как первый аргумент
  • пара переменных счетчика и длина списка, которые будут использоваться для сигнала переключения из списка один на список два
  • и, конечно, пара пустых списков для заполнения элементов L в
half([], _, {Acc1, Acc2}) ->
  {lists:reverse(Acc1), lists:reverse(Acc2)};

half/3 выглядит как беспорядок, но только для неподготовленных глаз. Первое предложение соответствует шаблону, когда список источников исчерпывается. В этом случае вторая пара счетчика и длина не имеют значения, поскольку это уже конец. Мы это просто знаем Acc1 и Acc2 созрели для урожайности. Но подождите, что с реверсом обоих?

Добавление элемента в связанный список является очень медленной операцией. Он выполняется O(N) раз для каждого добавления, потому что ему нужно создать новый список, скопировать в него существующий, создать указатель на новый элемент и назначить его последнему элементу. Это как бы переделать весь список. Совместите это с рекурсиями, и вам предстоит катастрофа.

Единственный хороший способ добавить что-то в связанный список – это добавить его в начало. Тогда все, что ему нужно сделать это создать память для этого нового значения и дать ему ссылку на заголовок связанного списка. Простая операция O(1). Таким образом, даже если мы могли бы объединить списки с помощью ++ люблю [1, 2, 3] ++ [4]мы редко хотим делать это таким образом, особенно с рекурсиями.

Метод состоит в том, чтобы сначала перевернуть список источников, а затем добавить в него элемент, как [4 | [3, 2, 1]] , и снова верните их, чтобы получить правильный результат. Это может показаться ужасным, но реверсирование списка и возвращение его обратно являются операцией O(2N), то есть O(N). Но между ними для присоединения элементов к списку требуется только O(1), поэтому в основном это не требует дополнительного времени выполнения.

half([H|T], {Cnt, Len}, {Acc1, Acc2}) ->
  case Cnt >= (Len div 2) of
      true -> half(T, {Cnt + 1, Len}, {Acc1, [H|Acc2]});
      false -> half(T, {Cnt + 1, Len}, {[H|Acc1], Acc2})
  end.

Возвращаясь к half/3. Второй пункт, мясо функции, выполняет то же, что и метафора наливания кофе, которую мы посетили ранее. Поскольку список источников все еще «выпускает» данные, мы хотим отслеживать время, когда мы выливали значение из него в первую чашку кофе. Acc1.

Помните об этом в half/1Последний пункт мы вычислили длину исходного списка? Это переменная Len здесь, и она остается неизменной на протяжении всех вызовов. Это там, чтобы мы могли сравнивать Cnt противопоставьте его разделению на 2, чтобы увидеть, перешли ли мы к середине списка источников и должны ли перейти к заполнению Acc2 . Вот где case … of заходит.

Теперь давайте объединим их всех вместе mergesort/1 . Это должно быть так же просто, как версия Python, и его можно сравнить.

mergesort([A]) -> [A];
mergesort([A, B]) ->
  case A =< B of
      true -> [A,B];
      false -> [B,A]
  end;
mergesort(L) ->
  {Left, Right} = half(L),
  merge(mergesort(Left), mergesort(Right), []).

Это!

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

Обновление

Реализация Python merge функция не является эффективной, поскольку в каждом while loop первый элемент в списке удаляется. Хотя это обычный шаблон в функциональных языках, таких как Erlang, у Python очень дорого удалить или вставить элемент где угодно, кроме последней позиции, потому что в отличие от списка Erlang, который является связанным списком, который очень эффективно удалять или добавлять элемент В главе списка список Python ведет себя как массив, который должен изменить расположение всех других элементов, когда их удаляют или добавляют, что приводит к O(n) времени выполнения.

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

def merge(a, b):
    out = []

    ai = 0
    bi = 0

    while (ai <= len(a) - 1 and bi <= len(b) - 1): 
        if (a[ai] <= b[bi]):
            out.append(a[ai])
            ai += 1
        else:
            out.append(b[bi])            
            bi += 1

    while (ai <= len(a) - 1):
        out.append(a[ai])
        ai += 1

    while (bi <= len(b) - 1):
        out.append(b[bi])
        bi += 1

    return out

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *