MROC3 (Шамаева Лена)

Большинство использовало exec.

   1 res = ""
   2 s = input().rstrip()
   3 while s:
   4     if s.startswith("class") and ":" in s:
   5         res += f"{s.split(':')[0]}: pass\n"
   6     s = input().rstrip()
   7 try:
   8     exec(res)
   9 except Exception as E:
  10     print("No")
  11 else:
  12     print("Yes")

Это читерство )). И в этом примере лучше было бы сделать exec() в изолированном пространстве.

Теперь решение на основе алгоритма.

Алгоритм хорошо расписан здесь [https://www.python.org/download/releases/2.3/mro/ https://www.python.org/download/releases/2.3/mro/]

• Есть пример разбора алгоритма в лекциях

Берем класс и его родителей, делаем линеаризацию.

Надо разобраться с merge. На картинке на вход merge приходит список линеаризаций родительских классов и сами родительские классы.

Например, [[A,B,C], [D,C], [A,E], …] 

• Берем нулевой элемент нулевого списка. Смотрим, чтобы этот элемент встречался только в начале остальных списков (в качестве нулевого элемента) и не встречался в хвостах этих списков.

• A Можно: [[A, B, C], [D, C], [A, E], …]

• A Нельзя: [[A, B, C], [D, A], …]

Вкратце: на входе у нас список каких-то списков.

• Если элемент
  1. не является ничьим предком (среди оставшихся в этих списках классов),
  2. в списке объявления родительских классов не идет после никакого другого.
• Тогда этот элемент «хороший» и может считаться следующим кандидатом для линеаризации.

  • При этом он добавляется в результат и удаляется из всех списков

• Если элемент встречался в других списках в качестве не первого, то он «плохой».

  • Переходим к следующему списку (текущий начинается с «плохого» элемента)

• (То есть в [[A, B, C], [D, A], …] после проверки кандидата для линеаризации A (он «плохой»: сходит в хвост второго списка) переходим к D в качестве кандидата для линеаризации.)

• Если ни одного кандидата для линеаризации не было найдено, то есть любой заголовочный элемент встречался в каком-нибудь из хвостов, то линеаризация невозможна.

В комментариях приведены значения переменных при входных данных:

class A: pass
class B(A): pass
class C(A,B): pass

Программа:

   1 import re
   2 Cls, L = {}, {}
   3 # Cls – словарь, ключ – название класса, значение – список родительских классов
   4 # пример: {'A': [], 'B': [], 'C': ['A', 'B']}
   5 # L — словарь, ключ — название класса, значение — линеаризация этого класса
   6 # пример: L {'A': ['A'], 'B': ['B', 'A']}
   7 
   8 def merge(parents): # например, для строки ‘class C(A,B):’ parents = ['A', 'B']
   9     if not parents: # если parents пустой, то линеаризовать нечего
  10         return
  11     S = [L.setdefault(b, [b, *merge(Cls[b])]).copy() for b in parents] + [parents]      # [L(B1), L(B2),...L(Bn), B1,…, Bn], см. Зам. 1
  12     while S:
  13         for s in S:
  14             if not s: continue #на пустые не обращаем внимание, они могут быть даны изначально
  15             e = s[0]
  16             if all(e==ss[0] or e not in ss for ss in S): # см. Зам. 2
  17                 yield e
  18                 for ss in S:
  19                     if ss and ss[0] == e: # удаляем уже рассмотренный элемент
  20                         del ss[0]
  21                 S = list(filter(len, S)) #удаляем пустые
  22                 break
  23         else:
  24             raise TypeError # см. Зам. 3
  25 
  26 reClass = re.compile(r"class\s+(\w+)\s*(?:\((.*)\))?\s*:")
  27 #class{пробелы}{имя_класса}{пробелы_или_пусто}'''('''родительские_классы_или_пробелы''')''':
  28 s = input().rstrip() # rstrip — могут быть пустые строчки, какие-то пробельчики справа
  29 while s:
  30     res = reClass.match(s)
  31     if res:
  32         Nam, Par = res.groups()
  33         Cls[Nam] = [c.strip() for c in Par.split(",")] if Par else []
  34         try:
  35             L[Nam] = [Nam, *merge(Cls[Nam])]
  36         except TypeError:
  37             print("No")
  38             break
  39     s = input().rstrip()
  40 else:
  41     print("Yes")

• Далее подробно рассмотрим, почему некоторые строки написаны таким образом.

Зам.1

1. В классическом алгоритме merge применяется к L(B1), L(B2),…,L(Bn), [B1, B2,…,Bn]: L[C(B1 … BN)] = C + merge(L[B1] … L[BN], [B1 … BN])

   • В решении на вход функции merge дается только B1, …, Bn - родительские классы для C.

   • Мы сами строим [L(B1), L(B2),…,L(Bn), [B1, B2,…,Bn]], используя [B1, … Bn].

2. [b, *merge(Cls[b])] – линеаризация L(Bi).

   • Здесь используем то, что в python3 можно

        1 >>> a = [1,2,*range(8)]
        2 >>> a
        3 [1, 2, 0, 1, 2, 3, 4, 5, 6, 7]
        4 
     

   • Тогда

        1 S = [[b, *merge(Cls[b])] for b in parents] + [parents]
        2 # [L(B1),…,L(Bn),[B1,…,Bn]]
     

3. Но так каждый раз линеаризация пересчитывается заново. Хотим использовать ранее вычисленную линеаризацию, которая хранится в L.

      1 L_B = L[b] if b in L else [b, *merge(Cls[b])] – L(Bi)
   

4. В словарях питона есть setdefault, который возвращает значение по ключу, инициализируя элемент словаря, если необходимо, указанным значением.

      1 >>> d = {}
      2 >>> d.setdefault('a', 15)
      3 15
      4 >>> d
      5 {'a': 15}
      6 
   

   • Перепишем с setdefault:

        1 L_B = L.setdefault(b, [b, *merge(Cls[b])]) – L(Bi).
        2 S = [L.setdefault(b, [b, *merge(Cls[b])]) for b in parents] + [parents]
        3 # [L(B1),…,L(Bn),B1,…,Bn]
     

5. Если оставить так, то при удалении элемента из списка линеаризации (del ss[0]), мы удаляем его из Cls{} (потому что мы модифицируем списки, которые хранятся, как значения в ss[0]). Это серьезный изъян!

   • Сделаем копию. Стало правильно, но в 5 раз медленнее:

        1 S = [L.setdefault(b, [b, *merge(Cls[b])]).copy() for b in parents] + [parents]
     

   • Общая идея: если вы получаете список и собираетесь его модифицировать, есть шанс, что вы модифицируете это по-живому (и модифицируете то, что где-то еще используется).

Зам. 2

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

• То есть запрещено class A(A): и class B(A, A)

• Таких вариантов нет в тестах, а если бы были, проверку на повторяющиеся элементы можно при вводе сделать элементарно — просто сравнить длину списка с длиной изготовленного из него множества).

Для элемента - кандидата на линеаризацию и проверяемого списка могут быть две взаимоисключающие ситуации:

• или выбранный элемент совпадает с головой списка (равен s[0]), /
• или элемент не содержится в списке.

Если это не так, то линеаризация невозможна.

По смыслу надо проверять, что элемента нет в хвосте, то есть

• e not in ss[1:]

• Но тогда на каждой итерации будет создаваться копия строки на элемент короче ss.

• Лучше проверять вхождение в целую ss. Всего на одну проверку больше, но меньше на целое создание списка при каждой итерации! (см. Зам. 3)

Зам. 3

• Клауза else для for — нет такого элемента, который встречается только в голове и не встречается в хвосте.

• Значит, ситуация безвыходная и линеаризация невозможна.

• Но просто так return из генератора merge() не сделать (это будет просто конц итерации). Тогда бросаем исключение!

Профилирование на 7 тесте

• Седьмой тест — самый нагрузочный, на нём видны узкие места:

  $ python3 -m cProfile -s tottime ../mro.po <007.dat 
  2311051 function calls (2298438 primitive calls) in 1.297 seconds
     Ordered by: internal time
     ncalls   tottime  percall  cumtime  percall filename:lineno(function)
    2169847     0.862    0.000    0.862    0.000 mro.py:16(<genexpr>)
  56812/44231   0.264    0.000    1.286    0.000 mro.py:8(merge)

• Общее время — 1.297 секунды, из них 0.862 секунды занимает эта строчка:

     1 if all(e==ss[0] or e not in ss for ss in S): 
  

• То есть чем эффективнее будет работать эта проверка, тем быстрее будет работать вся программа.