Differences between revisions 1 and 2
Revision 1 as of 2020-12-05 14:27:10
Size: 11695
Editor: FrBrGeorge
Comment:
Revision 2 as of 2020-12-05 14:30:02
Size: 11706
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 60: Line 60:
import re

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/]

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

linear.png

Надо разобраться с 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): 
    
  • То есть чем эффективнее будет работать эта проверка, тем быстрее будет работать вся программа.

LecturesCMC/PythonIntro2020/Homework_MroC3/Review (last edited 2020-12-05 14:30:02 by FrBrGeorge)