Неожиданное замедление в Advent of Code 2015, день 7

Я решаю версию Advent of Code 2015 года и получил на день 7 неожиданное поведение, которое, возможно, кто-то может помочь мне понять.

Задача состоит в том, чтобы вычислить значения (беззнаковые 16-битные), которые производит сеть проводов, например,

 123 -> x
 456 -> y
 x AND y -> d
 x OR y -> e
 x LSHIFT 2 -> f
 y RSHIFT 2 -> g
 NOT x -> h
 NOT y -> i

Я решил эту проблему с помощью графов и топологической сортировки, чтобы определить соответствующий порядок назначений. Однако я также хотел попробовать гораздо более элегантное 🔁 решение, предложенное Мэтью Баттериком, которое заключается в том, чтобы интерпретировать входные данные как DSL и позволить ему вычислить значение самостоятельно. Решение по ссылке есть в Racket. Я создал следующую версию Python,

import re

def uint(i): 
  """ unsigned int """
  return i if i >= 0 else 65536+i

fs = { }   # a dictionary of lambda expressions

with open('input_day7.txt', 'r') as f:
  for line in f:
    ws = re.split('[ >-]', line.rstrip()) # input pre-processing
    ws = [w for w in ws if w != '']

    if ws[0] == 'NOT':
      fs[ws[2]] = lambda x=ws[1]: uint(~fs[x]())
      
    elif ws[1] == 'AND':
      try:      # int AND y -> z
        fs[ws[3]] = lambda x=int(ws[0]), y=ws[2] : x & fs[y]()
      except:   #   x AND y -> z
        fs[ws[3]] = lambda x=ws[0], y=ws[2] : fs[x]() & fs[y]()
      
    elif ws[1] == 'OR':
      fs[ws[3]] = lambda x=ws[0], y=ws[2] : fs[x]() | fs[y]()
      
    elif ws[1] == 'LSHIFT':
      fs[ws[3]] = lambda x=ws[0], y=int(ws[2]) : fs[x]() << y
      
    elif ws[1] == 'RSHIFT':
      fs[ws[3]] = lambda x=ws[0], y=int(ws[2]) : fs[x]() >> y
      
    else:
      try:     # 123 -> x
        fs[ws[1]] = lambda x=int(ws[0]): x
      except:  #   y -> x
        fs[ws[1]] = lambda x=ws[0]: fs[x]()

print(fs['dw']()) # still works, but 'dy' already takes much more time

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

Кто-нибудь может объяснить, почему это так? Спасибо,

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

— 11.12.2020 23:52

python

11.12.2020 22:53

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

249

Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Каждый узел с одинаковыми значениями может оцениваться много раз, так как нет мемоизации. Например, я вижу, что "e OR f" повторяется более миллиона раз.

Я не рассматривал такую возможность (противная сеть и глупый я). И, при ближайшем рассмотрении, в сообщении Баттерика также упоминается мемоизация. Просто включил кеш в программу и теперь все ок. Спасибо.

— 12.12.2020 08:45

12.12.2020 01:36

В моем решении используется встроенная функция Python eval. Поскольку имена некоторых проводов соответствуют ключевым словам Python, я меняю как, если, в, есть или на my_as, my_if...

def subs_operators(line):
  for k,v in {"AND": "&", "OR":"|", "XOR":"^", "NOT": "65536 + ~",
          "LSHIFT": "<<", "RSHIFT":">>"}.items():
    if line.find(k) != -1:
      return line.replace(k,v)
  return line

def subs_keywords(line):
  for k,v in {"as":"zz_as","if":"zz_if", 
              "in":"zz_in","is":"zz_is","or":"zz_or"}.items():
    if line.find(k) != -1 :
      return line.replace(k,v)
  return line

с этими примитивами преобразования ввод предварительно обрабатывается

with open("input.txt",'r') as file:
  lines = file.readlines()


lines= list(map(subs_operators, lines))
lines= list(map(subs_keywords, lines))

operations=list(map(lambda x:x.strip().split(' -> '),lines))

Теперь инструкции по вводу выглядят так:

['ба и до н.э.', 'бд']

['jl | джк', 'джм']

['б >> 1', 'в']

['о и к', 'р']

['65536 + ~ р', 'к']

С помощью списка логических значений я контролирую, какие операции оцениваются. изначально все ложно

ctrl=[] #to control if the operation is evaluable
for op in operations:
  ctrl.append(False)

Я вхожу в бесконечный цикл, пока не будут оценены все операции. В каждой итерации я оценивал только операции, которые не оценивались.

while not all(ctrl):
  for pos, operation in enumerate(operations):
    if not ctrl[pos]: #eval not previously evaluated instructions
      try:
        res = eval(operation[0])
        ctrl[pos]= True
        globals()[operation[1]] = res
      except:
        pass

Если evals терпит неудачу, это означает, что не все его входы имеют сигнал. Обработчик исключений помогает мне перейти к следующей операции.

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

Первый цикл оценивал 7 операций, второй цикл оценивал 4 операции...

мне понадобилось 112 циклов, чтобы вычислить a = 956