Python: сортировка списка зависимостей

Я пытаюсь решить, может ли моя проблема разрешиться с помощью встроенной функции sorted(), или если мне нужно сделать сам - старая школа, использующая cmp, была бы относительно легкой.

Мой набор данных выглядит так:

x = [
('business', Set('fleet','address'))
('device', Set('business','model','status','pack'))
('txn', Set('device','business','operator'))
....

Правило сортировки должно быть в основном для всех значений N и Y, где Y > N, x [N] [0] не в x [Y] [1]

Хотя я использую Python 2.6, где аргумент cmp все еще доступен, я пытаюсь сделать этот Python 3 безопасным.

Итак, можно ли это сделать с помощью некоторой лямбда-магии и ключевого аргумента?

- == UPDATE == -

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

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

Мое решение:

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, set(names of dependancies))`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source]        
    emitted = []
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(set((name,)), emitted) # <-- pop self from dep, req Py2.6
            if deps:
                next_pending.append(entry)
            else:
                yield name
                emitted.append(name) # <-- not required, but preserves original order
                next_emitted.append(name)
        if not next_emitted:
            raise ValueError("cyclic dependancy detected: %s %r" % (name, (next_pending,)))
        pending = next_pending
        emitted = next_emitted

Ответ 1

То, что вы хотите, называется топологическим типом . Хотя это возможно реализовать с помощью встроенного sort(), это довольно неудобно, и лучше реализовать топологическую сортировку непосредственно в python.

Почему это будет неудобно? Если вы изучаете два алгоритма на странице wiki, они оба полагаются на запущенный набор "отмеченных узлов", концепция, которая может сжиматься в форме sort(), может использоваться, поскольку key=xxx (или даже cmp=xxx) лучше всего работает с функциями сравнения без сохранения, особенно потому, что timsort не гарантирует порядок, в котором будут рассмотрены элементы. Я (довольно) уверен, что любое решение, использующее sort(), закончит избыточным вычислением некоторой информации для каждого вызова к функции key/cmp, чтобы обойти проблему безгражданства.

Следующее - это alg, который я использовал (для сортировки некоторых зависимостей библиотеки javascript):

изменить: это сильно переработано на основе решения Winston Ewert

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, [list of dependancies])`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source] # copy deps so we can modify set in-place       
    emitted = []        
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, deps = entry
            deps.difference_update(emitted) # remove deps we emitted last pass
            if deps: # still has deps? recheck during next pass
                next_pending.append(entry) 
            else: # no more deps? time to emit
                yield name 
                emitted.append(name) # <-- not required, but helps preserve original ordering
                next_emitted.append(name) # remember what we emitted for difference_update() in next pass
        if not next_emitted: # all entries have unmet deps, one of two things is wrong...
            raise ValueError("cyclic or missing dependancy detected: %r" % (next_pending,))
        pending = next_pending
        emitted = next_emitted

Sidenote: функция t cmp() может быть включена в key=xxx, как описано в этом сообщении .

Ответ 2

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

x = [
    ('business', ('fleet','address')),
    ('device', ('business','model','status','pack')),
    ('txn', ('device','business','operator'))
]

import networkx as nx

g = nx.DiGraph()
for key, vals in x:
    for val in vals:
        g.add_edge(key, val)

print nx.topological_sort(g)

Ответ 3

Я делаю топологический вид примерно так:

def topological_sort(items):
    provided = set()
    while items:
         remaining_items = []
         emitted = False

         for item, dependencies in items:
             if dependencies.issubset(provided):
                   yield item
                   provided.add(item)
                   emitted = True
             else:
                   remaining_items.append( (item, dependencies) )

         if not emitted:
             raise TopologicalSortFailure()

         items = remaining_items

Я думаю, что это немного более прямолинейно, чем версия Eli, я не знаю об эффективности.

Ответ 4

Это предложение Уинстона с docstring и крошечной настройкой, переворачивая dependencies.issubset(provided) с помощью provided.issuperset(dependencies). Это изменение позволяет вам передать dependencies в каждой входной паре как произвольное итерируемое, а не обязательно set.

В моем примере использования есть dict, чьими ключами являются строки элементов, причем значение для каждого ключа является list имен элементов, от которых зависит этот ключ. Как только я установил, что dict не является пустым, я могу передать его iteritems() модифицированному алгоритму.

Еще раз спасибо Уинстону.

def topological_sort(items):
    """
    'items' is an iterable of (item, dependencies) pairs, where 'dependencies'
    is an iterable of the same type as 'items'.

    If 'items' is a generator rather than a data structure, it should not be
    empty. Passing an empty generator for 'items' (zero yields before return)
    will cause topological_sort() to raise TopologicalSortFailure.

    An empty iterable (e.g. list, tuple, set, ...) produces no items but
    raises no exception.
    """
    provided = set()
    while items:
         remaining_items = []
         emitted = False

         for item, dependencies in items:
             if provided.issuperset(dependencies):
                   yield item
                   provided.add(item)
                   emitted = True
             else:
                   remaining_items.append( (item, dependencies) )

         if not emitted:
             raise TopologicalSortFailure()

         items = remaining_items