Моя реализация слияния двух отсортированных списков в линейное время - что можно улучшить?

Question

Fromg Google Python Class:

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):
  merged_list = []
  i = 0
  j = 0

  while True:
    if i == len(list1):
        return merged_list + list2[j:]
    if j == len(list2):
        return merged_list + list1[i:]

    if list1[i] <= list2[j]:
        merged_list.append(list1[i])
        i += 1
    else:
        merged_list.append(list2[j])
        j += 1

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

Я видел похожие вопросы, задаваемые здесь, и все решения выглядят очень похоже намой, т.е. очень C-like.Больше нет питон-подобного решения?Или это из-за природы алгоритма?

Answer 1

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

Это работает, если передан любой итератор, а не только списки.

Этот подход также проходит один из более полезных тестов: он ведет себя хорошо, когда прошел бесконечный или почти бесконечный итератор, например. linear_merge(xrange(10**9), xrange(10**9)).

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

def linear_merge(list1, list2):
    """
    >>> a = [1, 3, 5, 7]
    >>> b = [2, 4, 6, 8]
    >>> [i for i in linear_merge(a, b)]
    [1, 2, 3, 4, 5, 6, 7, 8]
    >>> [i for i in linear_merge(b, a)]
    [1, 2, 3, 4, 5, 6, 7, 8]
    >>> a = [1, 2, 2, 3]
    >>> b = [2, 2, 4, 4]
    >>> [i for i in linear_merge(a, b)]
    [1, 2, 2, 2, 2, 3, 4, 4]
    """
    list1 = iter(list1)
    list2 = iter(list2)

    value1 = next(list1)
    value2 = next(list2)

    # We'll normally exit this loop from a next() call raising StopIteration, which is
    # how a generator function exits anyway.
    while True:
        if value1 <= value2:
            # Yield the lower value.
            yield value1
            try:
                # Grab the next value from list1.
                value1 = next(list1)
            except StopIteration:
                # list1 is empty.  Yield the last value we received from list2, then
                # yield the rest of list2.
                yield value2
                while True:
                    yield next(list2)
        else:
            yield value2
            try:
                value2 = next(list2)

            except StopIteration:
                # list2 is empty.
                yield value1
                while True:
                    yield next(list1)

Answer 2

Этот вопрос охватывает этот вопрос более подробно, чем вам, вероятно, нужно.;) Выбранный ответ соответствует вашему требованию.Если бы мне нужно было сделать это самому, я бы сделал это так, как описано в его ответе dbr (сложите списки вместе, отсортируйте новый список), поскольку это очень просто.:

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

def mergeSortedLists(a, b):
    l = []
    while a and b:
        if a[0] < b[0]:
            l.append(a.pop(0))
        else:
            l.append(b.pop(0))
    return l + a + b

Answer 3

Зачем останавливаться на двух списках?

Вот моя реализация на основе генератора для объединения любого числа отсортированных итераторов за линейное время.

Я не уверен, почему чего-то такого нет в itertools ...

def merge(*sortedlists):

    # Create a list of tuples containing each iterator and its first value
    iterlist = [[i,i.next()] for i in [iter(j) for j in sortedlists]]

    # Perform an initial sort of each iterator's first value
    iterlist.sort(key=lambda x: x[1])

    # Helper function to move the larger first item to its proper position
    def reorder(iterlist, i): 
        if i == len(iterlist) or iterlist[0][1] < iterlist[i][1]:
            iterlist.insert(i-1,iterlist.pop(0))
        else:
            reorder(iterlist,i+1)

    while True:
        if len(iterlist):
            # Reorder the list if the 1st element has grown larger than the 2nd
            if len(iterlist) > 1 and iterlist[0][1] > iterlist[1][1]:
                reorder(iterlist, 1)

            yield iterlist[0][1]

            # try to pull the next value from the current iterator
            try:
                iterlist[0][1] = iterlist[0][0].next()
            except StopIteration:
                del iterlist[0]
        else:
            break

Вот пример:

x = [1,10,20,33,99]
y = [3,11,20,99,1001]
z = [3,5,7,70,1002]

[i for i in merge(x,y,z)]

Answer 4

привет, я только что выполнил это упражнение, и мне было интересно, почему бы не использовать,

def linear_merge(list1, list2):
  return sorted(list1 + list2)

Функция сортировки питонов линейна, не так ли?

Answer 5

Другой генератор:

def merge(xs, ys):
    xs = iter(xs)
    ys = iter(ys)
    try:
        y = next(ys)
    except StopIteration:
        for x in xs:
            yield x
        raise StopIteration
    while True:
        for x in xs:
            if x > y:
                yield y
                break
            yield x
        else:
            yield y
            for y in ys:
                yield y
            break
        xs, ys, y = ys, xs, x

Answer 6

Вот моя реализация из предыдущего вопроса :

def merge(*args):
    import copy
    def merge_lists(left, right):
        result = []
        while (len(left) and len(right)):
            which_list = (left if left[0] <= right[0] else right)
            result.append(which_list.pop(0))
        return result + left + right
    lists = [arg for arg in args]
    while len(lists) > 1:
        left, right = copy.copy(lists.pop(0)), copy.copy(lists.pop(0))
        result = merge_lists(left, right)
        lists.append(result)
    return lists.pop(0)

Answer 7

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

def linear_merge(list1, list2):
    merged_list = []
    i = 0
    j = 0

    try:
        while True:
            if list1[i] <= list2[j]:
                merged_list.append(list1[i])
                i += 1
            else:
                merged_list.append(list2[j])
                j += 1
    except IndexError:
        if i == len(list1):
            merged_list.extend(list2[j:])
        if j == len(list2):
            merged_list.extend(list1[i:])
    return merged_list

edit Оптимизировано согласно комментарию Джона Мачина.Перемещено try за пределы while True и расширено merged_list при исключении.

Answer 8

Это решение выполняется за линейное время и без редактирования l1 и l2:

def merge(l1, l2):
  m, m2 = len(l1), len(l2)
  newList = []
  l, r = 0, 0
  while l < m and r < m2:
    if l1[l] < l2[r]:
      newList.append(l1[l])
      l += 1
    else:
      newList.append(l2[r])
      r += 1
  return newList + l1[l:] + l2[r:]

Answer 9

Согласно примечанию здесь:

# Note: the solution above is kind of cute, but unforunately list.pop(0)
# is not constant time with the standard python list implementation, so
# the above is not strictly linear time.
# An alternate approach uses pop(-1) to remove the endmost elements
# from each list, building a solution list which is backwards.
# Then use reversed() to put the result back in the correct order. That
# solution works in linear time, but is more ugly.    

и эта ссылка http://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

append - это O (1), reverse - это O (n), но также говорится, что pop - это O (n), так что же и что? В любом случае я изменил принятый ответ, чтобы использовать pop (-1):

def linear_merge(list1, list2):
    # +++your code here+++
    ret = []
    while list1 and list2:
        if list1[-1] > list2[-1]:
            ret.append(list1.pop(-1))
        else:
            ret.append(list2.pop(-1))

    ret.reverse()

    return list1 + list2 + ret