Линейное слияние для списков в Python

Question

Я работаю над упражнениями Google Python в классе .Одним из упражнений является следующее:

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

Решение, которое я придумал, было:

    def linear_merge(list1, list2):
      list1.extend(list2) 
      return sorted(list1)

Оно прошло функцию тестированияно решение дано так:

    def linear_merge(list1, list2):
      result = []
      # Look at the two lists so long as both are non-empty.
      # Take whichever element [0] is smaller.
      while len(list1) and len(list2):
        if list1[0] < list2[0]:
          result.append(list1.pop(0))
         else:
          result.append(list2.pop(0))

      # Now tack on what's left
      result.extend(list1)
      result.extend(list2)
      return result

В состав решения было включено следующее:

Примечание: решение, приведенное выше, довольно мило, но к сожалению list.pop (0)не постоянное время со стандартной реализацией списка Python, поэтому приведенное выше не является строго линейным временем.Альтернативный подход использует pop (-1) для удаления самых конечных элементов из каждого списка, создавая список решений, который имеет обратную сторону.Затем используйте reversed (), чтобы вернуть результат в правильном порядке.Это решение работает за линейное время, но оно более уродливо.

Почему эти два решения настолько разные?Я что-то упускаю или они излишне сложные?

Answer 1

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

Answer 2

Мне больше всего нравится подход @Abhijit. Вот немного более питонная / читабельная версия его фрагмента кода:

def linear_merge(list1, list2):
    result = []

    while list1 and list2:
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

    return (result + list1 + list2)[-1::-1]

С помощью встроенных функций Python мы:

1. не нужно явно проверять, являются ли списки пустыми с помощью len function.
2. может объединять / добавлять пустые списки, и результат останется неизменным, поэтому нет необходимости в явной проверке.
3. мы можем объединить несколько операторов (если позволяет удобочитаемость), что иногда делает код более компактным.

Answer 3

Как вы заметили, ваше решение работает отлично.Так почему сложность?Ну, для начала

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

Ну, вы не явнопроходя через любые списки, но вы звоните sorted().Так сколько раз sorted() пройдет по спискам?

Ну, на самом деле я не знаю.Обычно алгоритм сортировки работает примерно в O(n*log(n)) время, хотя посмотрите на эту цитату из документации по Python:

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

Может быть, кто-то, кто лучше знает timsort, сможет понять это.

Но то, что они делают в решении, использует тот факт, что они знать у них есть 2 отсортированных списка.Таким образом, вместо того, чтобы начинать с нуля с sorted, они выбирают элементы 1 на 1.

Answer 4

result = []
while list1 and list2:
    result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

if len(list1):
    result += list1[-1::-1]
if len(list2):
    result += list2[-1::-1]

return result[-1::-1]

Решение @Abhijit и @intel не работает во всех случаях, потому что они не перевернули оставшиеся части первоначальных списков. Если у нас есть list1 = [1, 2, 3, 5, 9, 11, 13, 17] и list2 = [6, 7, 12, 15], то их решение даст [5, 3, 2, 1, 6, 7, 9, 11, 12, 13, 15, 17] там, где мы хотим [1, 2, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17].

Answer 5

def linear_merge(list1, list2):
     a= list1 + list2
     a.sort() 
     return a

Answer 6

Немного улучшено все еще уродливым решением (в Python3.5):

def linear_merge(list1: list, list2: list):
    result = []

    while len(list1) and len(list2):
        result.append((list1 if list1[-1] > list2[-1] else list2).pop(-1))

    result += list1 if len(list1) else list2

    return result[-1::-1]

Answer 7

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

def linear_merge(list1, list2):
  # NOT return sorted (list1 + list2), as this is not linear
  list3 = []
  rem = []
  empty = False

  while not empty:
    # Get last items from each list, if they exist
    if len (list1) > 0:
      a = list1[-1]
    else:
      rem = list2[:]
      empty = True

    if len (list2) > 0:
      b = list2[-1]
    else:
      rem = list1[:]
      empty = True

    # Pop the one that's largest onto the new list
    if not empty:
      if a > b:
        list3.append (a)
        list1.pop ()
      else:
        list3.append (b)
        list2.pop ()

  # add the (reversed) remainder to the list
  rem.reverse ()
  list3 += rem

  # reverse the entire list
  list3.reverse ()
  return list3

Answer 8

Ваше решение - O (n log n), что означает, что если бы ваши списки были в 10 раз длиннее, программа заняла бы (примерно) в 30 раз больше времени.Их решение займет всего 10 раз.