Слияния Н отсортированный итераторы


За выходные мне стало интересно о эффективное объединение нескольких отсортированный итераторы вместе, и для них, чтобы быть в отсортированном порядке. Это довольно как вызов на HackerRank:

Вы получаете указатель на головные узлы из двух отсортированный связанный список. Данные в оба списка будут отсортированы в порядке возрастания. Изменить следующие указатели, чтобы получить один, слился связанный список, который также имеет данные по возрастанию. Либо глава указатель может быть null означает, что соответствующий список пуст.

Возможно, я немного схитрил при печати, вместо того, чтобы возвратить детали. Однако я не возражаю, что много о HackerRank вызов.

Мне удалось сделать это в О \О(3л)\$ площадь и $\О(Л(2+н))\$ времени. Так \$o(д)\$ и $\о(ЛН)\$. Где \$л\$ количество списков, и \N $\$ - это объем данных.

import operator
import functools

def from_iterable(fn):
    @functools.wraps(fn)
    def inner(*args):
        return fn(args)
    inner.from_iterable = fn
    return inner


@from_iterable
def merge(sources):
    sources = {
        id_: iter(source)
        for id_, source in enumerate(sources)
    }
    values = {}
    for id_, source in list(sources.items()):
        try:
            values[id_] = next(source)
        except StopIteration:
            del sources[id_]

    by_value = operator.itemgetter(1)
    while sources:
        id_, minimum = min(values.items(), key=by_value)
        try:
            values[id_] = next(sources[id_])
        except StopIteration:
            del values[id_], sources[id_]
        yield minimum


def iter_nodes(node):
    while node is not None:
        yield node.data
        node = node.next


def MergeLists(headA, headB):
    vals = merge.from_iterable(iter_nodes(l) for l in (headA, headB))
    print(' '.join(str(i) for i in vals), end='')

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



Комментарии
1 ответ


  1. Нет комментарии. Что делают эти функции? Какие аргументы они принимают? Зачем они возвращаются?

  2. Декораторы, как правило, названный в честь их влияние на декорируемую функцию. Например @functools.lru_cache добавляет ЛРУ кэш для функции; @unittest.skip причины теста должны быть пропущены, и так далее.

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


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

    Беда в том, что chain была ошибка. Если у нас был только chain.from_iterableтогда нам бы не было необходимости chainведь мы могли бы просто сделать кортеж: мы бы написать chain.from_iterable((arg1, arg2, ...)) вместо chain(arg1, arg2, ...). Это тривиальное изменение в соглашение о вызове (просто две скобки), что не нужна еще одна функция для его обслуживания. (Например, было бы смешно sorted и sorted.from_iterable.)

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

    Обратите внимание, что код в пост на самом деле не использовать mergeон только использует merge.from_iterable. Поэтому очевидно, надо было бы написать merge так что он принимает повторяемое, и избежать необходимости для @from_iterable декоратор и связанного с ней заблуждения.


  4. Так headA и headB не используются независимо друг от друга, вы можете изменить вызова для MergeLists так что он взял произвольное число связанных списков, как это:

    def merge_linked_lists(*lists):
    "Merge multiple sorted linked lists."
    return merge(map(iter_nodes, lists))

  5. Выражение:

    str(i) for i in vals

    может быть написано:

    map(str, vals)

    Или, если вы предпочитаете понимания, затем рассмотреть вопрос об улучшении имя переменной цикла. Имя i традиционно используется для индекса, но здесь мы не перебором индексов, но и по ценности, так v или value было бы яснее.


  6. Код в merge не использовать встроенную функцию id, так что нет необходимости respell переменную id_ для того, чтобы избежать слежки встроенный.

  7. Функция merge поддерживает две структуры данных. Словарь source карты Источник идентификатор итератора за соответствующий источник, и словарь values карты идентификатор исходного значения в передней части соответствующего источника. Код может быть упрощена, если две структуры данных были объединены в один, как этот:

    def merge(iterables):
    "Merge sorted iterables."
    entries = {} # Map from id to [front value, id, iterator].
    for id, it in enumerate(map(iter, iterables)):
    try:
    entries[id] = [next(it), id, it]
    except StopIteration:
    pass
    by_value = operator.itemgetter(1)
    while entries:
    id, entry = min(entries.items(), key=by_value)
    value, _, it = entry
    yield value
    try:
    entry[0] = next(it)
    except StopIteration:
    del entries[id]

  8. Время выполнения узкого места вызова min чтобы найти элемент с наименьшим значением. Это занимает время, пропорциональное количеству оставшихся итераторы, то есть \$o(д)\$.

    Мы можем улучшить это, чтобы \$о(\журнал л)\$, если мы сохраняем записей в куче, используя heapq модуль:

    from heapq import heapify, heappop, heapreplace

    def merge(iterables):
    "Merge sorted iterables."
    entries = [] # Heap of [front value, id, iterator].
    for id, it in enumerate(map(iter, iterables)):
    try:
    entries.append([next(it), id, it])
    except StopIteration:
    pass
    heapify(entries)
    while entries:
    value, _, it = entry = entries[0]
    yield value
    try:
    entry[0] = next(it)
    heapreplace(entries, entry)
    except StopIteration:
    heappop(entries)

    Это улучшает общее время выполнения Для \$О((П + Л)\журнал л)\$.


  9. Это уже встроенные в Python, как heapq.merge. Стоит взглянуть на исходный код — код в §8 выше-это упрощенная версия.

11
ответ дан 12 февраля 2018 в 11:02 Источник Поделиться