Вопрос о решении от дня занятий Google Python

1

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

Где я сделал это так.

# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.
def linear_merge(list1, list2):
  # +++your code here+++
  return sorted(list1 + list2)

Однако они сделали это более сложным образом. Решение Google быстрее? Потому что я заметил в комментариях, что решение должно работать в "линейном" времени, которое, вероятно, не является?

Это их решение

def linear_merge(list1, list2):
  # +++your code here+++
  # LAB(begin solution)
  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 left
  result.extend(list1)
  result.extend(list2)
  return result
Теги:

4 ответа

1
Лучший ответ

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

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

Это хорошее упражнение, чтобы подумать о том, как сделать это O (n). Ниже приведено то же самое дуновение, что и данное решение, но он избегает его ловушек, обобщая более двух списков ради упражнений. Для ровно 2 списков вы можете удалить обработку кучи и просто проверить, какой следующий элемент меньше.

import heapq

def iter_linear_merge(*args):
  """Yield non-decreasing items from sorted a and b."""
  # Technically, [1, 1, 2, 2] isn't an "increasing" sequence,
  # but it is non-decreasing.

  nexts = []
  for x in args:
    x = iter(x)
    for n in x:
      heapq.heappush(nexts, (n, x))
      break

  while len(nexts) >= 2:
    n, x = heapq.heappop(nexts)
    yield n
    for n in x:
      heapq.heappush(nexts, (n, x))
      break

  if nexts:  # Degenerate case of the heap, not strictly required.
    n, x = nexts[0]
    yield n
    for n in x:
      yield n

Вместо последнего if-for условие цикла while может быть изменено только на "nexts", но, вероятно, стоит специально обработать последний оставшийся итератор.

Если вы хотите строго вернуть список вместо итератора:

def linear_merge(*args):
  return list(iter_linear_merge(*args))
Поделиться
  • 0
    Msgstr "Для удаления из списка необходимо переместить все последующие элементы". Это на самом деле зависит от реализации базового списка. Получение первого элемента может быть легко реализовано в O (1), независимо от того, выполняется ли реализация через связанный список или массив.
  • 2
    @IoanAlexandruCucu: Конечно, это зависит от реализации базового списка, но мы говорим о конкретных реализациях: Python. Какая реализация делает это иначе, чем я описываю?
Показать ещё 3 комментария
2

это может быть еще одно солн? #

    def linear_merge(list1, list2):
            tmp = []
            while len(list1) and len(list2):
                    #print list1[-1],list2[-1]
                    if list1[-1] > list2[-1]:
                            tmp.append(list1.pop())
                    else:
                            tmp.append(list2.pop())
                    #print "tmp = ",tmp

            #print list1,list2
            tmp = tmp + list1
            tmp = tmp + list2
            tmp.reverse()
            return tmp
Поделиться
0

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

sorted(), вероятно, O (nlgn); то ваше решение не может быть линейным в худшем случае.

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

Вопрос не в том, что "быстрее" для данного случая ввода, но о том, какой алгоритм является более сложным.

Существуют гибридные варианты сортировки merge, которые возвращаются к другому алгоритму сортировки, когда размер списка входных данных падает ниже определенного порога.

Поделиться
  • 0
    У вас не будет худшего варианта для сортировки, так как вам выдаются индивидуально отсортированные списки.
  • 0
    Томас, это зависит от алгоритма сортировки; существуют виды (но, может быть, в наши дни они никогда не используются на практике?), которые хуже всего работают с уже отсортированными данными.
Показать ещё 1 комментарий
0

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

Но что за время, для чего?

Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню