Порядок доения, совместимый с максимальным количеством наблюдений

1. Обзор

1. руководство по стилю Python рекомендует 4 места для каждого уровня отступы и сохранение линий до 79 символов. Не обязательно следовать этому стилю, но другим программистам на Python проще читать код. Например, если вы придерживались 79 символов в строке, нам не пришлось бы прокручивать код по горизонтали, чтобы прочитать его здесь в обзоре кода. Кроме того, с более короткими строками вам было бы легче обнаружить опечатки, например, словари словарей.

2. Хотя описание проблемы связано с коровами и доением, должно быть ясно, что это очень тонкая маскировка, и вы действительно просто находите топологический порядок на ориентированном графике. Таким образом, нет необходимости, чтобы docstring ссылалась на «коров», и яснее сохранять абстрактные вещи, называя функцию чем-то вроде topological_order .

3. Было бы проще, если бы функция вернула топологический порядок, вместо обновления списка, переданного в качестве параметра. Я предполагаю, что вы реализовали его таким образом, потому что функция уже возвращает True, если график ацикличен и False в противном случае. Однако в Python легко вернуть несколько результатов из функции, вернув кортеж . Таким образом, код может стать:

   if newGraphIN: # There's a cycle in the graph.
       return False, None
   else: # Graph is acyclic.
       return True, newSort
   

   , а затем вызывающий может использовать назначение tuple , чтобы дать имена двум результатам:

   acyclic, order = topological_order(...)
   if acyclic:
       # Do something with order.
   else:
       # Handle cyclic case.
   

4. Код удаляет вершины из графика, когда больше нет входящих ребер:

   del newGraphIN[k]
   

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

   if newGraphIN: #there's a cycle in the graph
   

   Но я думаю, что было бы проще оставить вершины на графике по ходу и проверить в конце для любых оставшихся ребер:

   if any(newGraphIN.values()):
   

   Это сохраняет пару строк кода, а также дает возможность дальнейшего упрощения, описанного ниже.

5. Теперь, когда код больше не изменяет newGraphIN во время построения noIncoming, аргумент numCows не нужен, потому что можно вывести вершины из графика. Итак, где код имеет:

   for k in range(1,numCows+1):
     if not newGraphIN[k]:
       noIncoming.append(k) 
   

   вместо этого:

   for v, incoming in newGraphIN.items():
       if not incoming:
           noIncoming.append(v)
   

   или более просто, используя понимание :

   noIncoming = [v for v, incoming in newGraphIN.items() if not incoming]
   

6. На каждом шаге код должен извлечь наименьшую вершину в списке noIncoming (чтобы получить лексикографически наименьшую топологическую сортировку) , Для этого он сортирует весь список noIncoming. Но это неэффективно: если в списке есть \ $ n \ $ элементов, для их сортировки требуется \ $ O (n \ log n) \ $, а другой \ $ O (n) \ $ - самый маленький предмет.

   Это может быть улучшено до \ $ O (\ log n) \ $ за элемент, если noIncoming представляется как куча . Куча - это структура данных, которая специализируется на эффективном повторном извлечении минимального элемента, который здесь нужен. Python имеет heapq , реализующий эту структуру данных и связанные с ней алгоритмы. В этом случае мы начинаем с превращения noIncoming в кучу, вызывая heapq.heapify :

   heapify(noIncoming)
   

   , то для извлечения наименьшей вершины из кучи будем называть heapq.heappop

   m = heappop(noIncoming)
   

   и добавить новую вершину в кучу, мы вызываем heapq.heappush :

   heappush(noIncoming, k)
   

7. Поскольку код никогда не изменяет newGraphOUT, нет необходимости делать копию.

8. Не нужно, чтобы функция выполняла как fullGraphOUT (ориентированный график), так и fullGraphIN (тот же график со всеми обращенными краями), так как последний можно легко вычислить из первого, взяв не больше, чем потребовалось бы, чтобы сделать копию.

9. Я думаю, что имена могут быть улучшены: я бы написал graph вместо fullGraphOUT, reversed_graph вместо newGraphIN, order вместо newSort, v и w для вершин вместо m и k и sources вместо noIncoming (потому что источники и sinks являются членами теории графов для вершин без входящих и исходящих ребер соответственно).

2. Пересмотренный код

from heapq import heapify, heappop, heappush

def topological_order(graph): 
    """Return the lexicographically smallest topological order of the
    vertices in graph (if possible).

    graph must be represented as a mapping from vertex to an iterable
    of its neighbours.

    Returns:
    acyclic -- True, if graph is acyclic, otherwise False.
    order -- The topological order, if graph is acyclic, otherwise None.

    """
    # Copy of graph with all edges reversed.
    reversed_graph = {v:set() for v in graph}
    for v, outgoing in graph.items():
        for w in outgoing:
            reversed_graph[w].add(v)

    # Topological order.
    order = []

    # Heap of sources (vertices with no incoming edges).
    sources = [v for v, incoming in reversed_graph.items() if not incoming]
    heapify(sources)

    while sources:
        v = heappop(sources)
        order.append(v)
        for w in graph[v]:
            incoming = reversed_graph[w]
            incoming.remove(v)
            if not incoming:
                heappush(sources, w)

    if any(reversed_graph.values()):
        # Some edges remain, hence there's a cycle in the graph.
        return False, None
    else:
        return True, order

3. Анализ

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

Когда коду в столбце присваиваются новые ребра, он обновляет ориентированный граф этими ребрами, а затем вызывает mooSort (или topological_order в обновленном коде), в котором выполняется модификация топологический алгоритм сортировки Kahn на графике. Алгоритм Кана обычно занимает время, пропорциональное числу вершин \ $ N \ $ плюс число ребер \ $ E \ $, то есть \ $ O (N + E) \ $, а потому, что нам нужен лексикографически наименьший топологический порядок , мы накладываем дополнительное наказание за нахождение наименьшей вершины на каждом шаге, делая ее \ $ O (N ^ 2 \ log N + E) \ $ (в исходном коде) или \ $ O (N \ log N + E) \ $ (в пересмотренном коде).

Топологический порядок пересчитывается после того, как каждая партия ребер добавлена ​​в график, поэтому topological_order получает имя \ $ O (M) \ $ раз, что делает общее время выполнения \ $ O (MN \ log N + ME) \ $ (в обновленном коде). Число ребер: \ $ O (\ min (N ^ 2, MN)) \ $, так как между каждой парой вершин может быть не более одного ребра, и в каждой партии добавляется не более \ $ N \ $ ребер , поэтому общая продолжительность выполнения: \ $ O (MN (\ log N + \ min (N, M))) \ $.

Мы хотели бы сделать лучше, чем это, но это не просто, потому что проблема инкрементной топологической сортировки по-прежнему является областью активных исследований, и наиболее известные алгоритмы сложны. Взгляните на эту статью для обзора состояния дел с 2008 года:

• Бернхард Хауплер, Сиддхартха Сен, Роберт Э. Тарьян (2008). " Инкрементальный топологический заказ и сильное обслуживание компонентов ". arXiv: 0803.0792 [cs.DS].

def mooSort(currentSort, fullGraphOUT, fullGraphIN, numCows): 
  """ Sorts the cows given the current list of conditions, described by fullGraphIN and fullGraphOUT. These are dictionaries dictionaries with vertex keys and and nodes either outgoing or incoming vertices"""

Вы можете разделить docstring на несколько строк, чтобы упростить чтение.

Не сразу видно, что подразумевается под « узлами ».

  noIncoming = [] #keep a list of vertices with no incoming edges
  newSort = [] #the topologically sorted vertices
  newGraphIN = copy.deepcopy(fullGraphIN)
  newGraphOUT = copy.deepcopy(fullGraphOUT)

Стиль Python - использование строчных слов с символами подчеркивания для переменных .

Я не вижу преимущества создания новых имен для защитных копий. ИМО безопаснее повторно использовать имя параметра, потому что таким образом вы не можете случайно изменить оригинальный словарь.

Имена xIN и xOUT звучат как входы и выходы. Комментарий объясняет их значение, но я думаю, что есть более прозрачные имена, такие как predecessors и successors

  for k in range(1,numCows+1):
    if not newGraphIN[k]:

      noIncoming.append(k) 
      del newGraphIN[k] #use this to keep track of if the graph has edges at the end

Нет необходимости удалять из графика для отслеживания наличия ребер: вы можете легко проверить это с помощью len(newSort) == numCows.

На самом деле, я не вижу, что необходимо newGraphIN. Единственное, что вам нужно, , сколько предшественников имеет еще вершина.

  while noIncoming: #take each element with no incoming edges and add it to our sort, remove it from the graph
    noIncoming.sort() #sorting so we can make it lexicographic as well

Я не буду повторять точку Гарета об использовании кучи.

   currentSort[:] = newSort #set the current sort to this one

Это было неожиданно. Докшрин не сказал ничего о currentSort, и я не ожидал, что это будет форма вывода. IMO, было бы достаточно вернуть newSort, если он завершен или None в противном случае.

#now do this in a binary search

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

       lines = data.readlines()
       #turn the lines into a list of list ints
       inputData=[list(map(int,line.split())) for line in lines]
       numCows = inputData[0][0]
       numConditions = inputData[0][1]
       inputData.pop(0)
       fullGraphOUT = {} #describe graph by outgoing neighbors
       fullGraphIN = {} #describe graph by incoming neighbors
       currentSort = [] #keep track of our current sorting
       for i in range(1,numCows+1): #initialize the graph to empty
         fullGraphOUT[i] = set()
         fullGraphIN[i] = set()
       for list in inputData:
         list.pop(0)
         for k in list: 
           for j in list[list.index(k)+1:]: 
             fullGraphOUT[k].add(j)
             fullGraphIN[j].add(k)
         if not mooSort(currentSort, fullGraphOUT, fullGraphIN, numCows): #once this gives false, we can no longer sort using all the conditions
          print(currentSort)
          break

Это выглядит немного для одного тела цикла. Почему бы не разделить обработку ввода на функцию?

         for k in list: 
           for j in list[list.index(k)+1:]: 
             fullGraphOUT[k].add(j)
             fullGraphIN[j].add(k)

Это перебор. Достаточно добавить каждое ребро один раз: вам не нужно вычислять транзитивное замыкание.