Грубая сила за наблюдателем
Как построить микромашины с паттерном Observer, способные решать самые сложные задачи.
При поиске довольно часто презирают силу грубой силы. Создается впечатление, что лучший способ решить проблемы - использовать какой-нибудь подходящий и осторожный метод. Однако чем сложнее и менее интерактивен код, тем более ограничена эффективность. Если, с другой стороны, мы беспокоимся о реализации чего-то более динамичного, то применимость формул к каждому случаю улучшается.
Поэтому для очень сложных проблем и не очень больших записей может быть целесообразно иметь итераторы, которые предлагают нам самые быстрые решения.
Грубая сила расписания
Представьте, что мы хотим реализовать простое школьное расписание. Для этого нам пришлось бы объединить учителей, курсы, классы ... Но расписание признает, по крайней мере, соответствие, которое обозначает, для какого класса, в какой день и в какое время дня, учителя, предмета и курса. Итак, мы можем подготовить эту инициализацию:
def test1(days, hours, clrooms, courses, teachs, subjs):
D = ['d' + str(X) for X in range(days)]
H = ['h' + str(X) for X in range(hours)]
R = ['r' + str(X) for X in range(clrooms)]
C = ['c' + str(X) for X in range(courses)]
T = ['t' + str(X) for X in range(teachs)]
S = ['s' + str(X) for X in range(subjs)]
return ((R, H, D), (S, T, C))
Если мы хотим повторить композицию списков (дни, часы и классы; или курсы, учителя и предметы), мы должны сначала объединить списки, чтобы их можно было хорошо закодировать, поэтому я могу предложить этот класс:
class Combine:
def __init__(self, domains):
self.D = domains
self.len = self._calculateLen()
def _calculateLen(self):
R = 1
for X in self.D:
R*= len(X)
return R
def __getitem__(self, item):
R = []
for dom in self.D:
R.append(dom[item % len(dom)])
item //= len(dom)
return tuple(R)
Вы можете протестировать приведенный выше код следующим образом:
>>> c = Combine([('a', 'b'), ('1', '2', '3')])
>>> for i in range(125, 136):
print(''.join(c[i]), end=' ')
b3 a1 b1 a2 b2 a3 b3 a1 b1 a2 b2
Цель класса Combine - предложить технику, которая позволяет нам обойти каждую из возможностей без какой-либо погрешности (грубой силы). И, с другой стороны, мы смогли проиндексировать любую возможность с большим числом. Следовательно, итератор, который мы можем использовать, будет следующим.
def corresp (dom, im, ini = 0):
'Returns the iterator'
'For every item in dom there is no more than one item in im'
X = Combine(dom)
Y = Combine(im)
while True:
C = {}
index = ini
for j in range(X.len):
C[X[ini + j]] = Y[index]
index //= Y.len
yield C
ini += 1
Этот итератор изначально подготовлен исключительно для учета всех совпадений. Таким образом, легко построить расписание, если в качестве ограничения используется только ОДНА корреспонденция.
>>> for X in corresp(*test1(3, 4, 2, 2, 5, 5)):
print(X)
break
{('r0', 'h0', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h0', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h1', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h1', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h2', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h2', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h3', 'd0'): ('s0', 't0', 'c0'), ('r1', 'h3', 'd0'): ('s0', 't0', 'c0'), ('r0', 'h0', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h0', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h1', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h1', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h2', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h2', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h3', 'd1'): ('s0', 't0', 'c0'), ('r1', 'h3', 'd1'): ('s0', 't0', 'c0'), ('r0', 'h0', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h0', 'd2'): ('s0', 't0', 'c0'), ('r0', 'h1', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h1', 'd2'): ('s0', 't0', 'c0'), ('r0', 'h2', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h2', 'd2'): ('s0', 't0', 'c0'), ('r0', 'h3', 'd2'): ('s0', 't0', 'c0'), ('r1', 'h3', 'd2'): ('s0', 't0', 'c0')}
Но нельзя забывать, что в расписании имеет значение:
- количество раз, когда тема появляется в неделю,
- сколько непоследовательных часов у испытуемого в день, и
- сколько непоследовательных часов у учителя в день.
Так что этот код вполне может быть первым приближением. Хотя цель этого поста - не рассказывать о том, как создавать расписания.
Грубая сила логики
Когда маленький ребенок сталкивается с проблемой логики, он, кажется, не применяет аксиомы Клини для ее решения; или любой другой продукт формальной системы блестящего ума.
Похоже, что используемые им механизмы похожи на паттерн наблюдателя. То есть попробуйте применить простые операции к каждому из явлений в выражении.
Тестирование всех возможных комбинаций в очень хорошо упорядоченной структуре может быть хорошим методом для поиска быстрых решений. Но, прежде всего, как работает шаблон наблюдателя?
Пример паттерна наблюдателя
Представьте, что вас интересует красное платье, но не только вы. Со временем возможно, что такие платья появятся в магазине, поэтому, чтобы быстро их купить, вы дадите магазину свой номер телефона, чтобы они могли позвонить вам.
Следовательно, чтобы применить шаблон, мы должны распознать подписку пользователя и механизм для уведомления всех о любых происходящих изменениях.
Как это могло быть применимо к логике?
Причины микромашин
Когда я предлагал реализацию, способную удовлетворить любую булеву формулу в цикле, я потребовал полиномиальное время, которое не было бы ни меньше, ни больше, чем n ⁵, n - количество статьи. Как объяснено ниже:
Однако O (n⁵) и o (n⁵) означает, что если для записи размером 10 (логическая формула из 10 пунктов) мы берем 1 секунду для решения [10⁵ меток времени → 1 секунда], то для записи размером 20 мы займет: 20⁵ = 2⁵ · 10⁵ → 2⁵ · 1 секунда = 32 секунды. Вот почему, несмотря на то, что код будет работать намного быстрее на машинах будущего, мы можем быть заинтересованы в более быстрых результатах.
Подготовка конструкции
Чтобы решить любую булеву формулу в рекордно короткие сроки, используя грубую силу для шаблона наблюдателя, нам нужно будет поместить в массив все переменные, включая временные.
Представьте себе массив, в котором хранятся только логические значения и значение Нет, и что, когда значение не равно Нет, все микромашины, подписавшиеся на эту ячейку, будут уведомлены ( Observer Pattern).
На самом деле, с этим массивом было бы легче работать, если бы мы могли вычислять его противоположность через индекс при доступе к его элементам. То есть создайте такие свойства, как: A [-X] = 1- A [X]
class DiaconArray:
def __init__(self, size):
self.body=[None]*size
def __setitem__(self, position, value):
if value == None:
self.body[position] = None
elif position<0:
self.body[-position] = 1 - value
else:
self.body[position] = value
def __getitem__(self,position):
if type(position) == slice:
other = DiaconArray(1)
other.body = self.body[position]
return other
elif self.body[abs(position)] == None:
return None
elif position < 0:
return 1 - self.body[-position]
else:
return self.body[position]
Вы можете найти ссылку с кодом в конце этого поста.
Наблюдатели создаются по повторяющемуся шаблону логических операторов, то есть все наблюдатели выполняют одну и ту же логическую операцию. В этом случае мы воспользуемся так называемым оператором χ из Криптоанализа.
Представьте, что мы определяем χ как: chi = lambda x, y, z0: (x & (1^y)) ^ z0 Каждый наблюдатель будет состоять из 4 временных переменных, где 3 должны быть входом χ, а четвертая - выходом. Это означает, что если бы x, y и z0 не были None, выходные данные можно было бы решить по формуле выше . Но что могло бы случиться, если бы на выходе не было None, а x и y…, тогда у нас было достаточно информации, чтобы знать значение z0. Вот почему мы должны определять нашу микромашину по-другому.
class Chi:
opChi=[ lambda x,y,z0,z1:z0^z1 if y==0 else None,
lambda x,y,z0,z1: z0^z1^1 if x==1 else None,
lambda x,y,z0,z1:(x&(1^y))^z1,
lambda x,y,z0,z1:(x&(1^y))^z0]
В этом случае мы наблюдаем четыре вида операций, которые нам приходилось делать, если мы хотели угадать аргумент 0, 1, 2 или 3 в χ (x, y, z0, z1).
Но что мы могли сделать, если бы у нас были только некоторые из ценностей вместо всех необходимых? Решение в следующем коде:
X=["323121323020313010212010",
#0000
"212010", #0001
"313010", #0010
"10", #0011
"323020", #0100
"20", #0101
"30", #0110
"0", #0111
"323121", #1000
"21", #1001
"31", #1010
"1", #1011
"32", #1100
"2", #1101
"3", #1110
"", #1111
]
Если бы мы знали все аргументы, кроме четвертого #1110 в χ (x, y, z0, z1), нам нужно было бы найти только четвертый оператор "3" в opChi, и если бы мы знали все, кроме третьего #1101, нам оставалось найти только третий "2". Таким образом, логически, если бы мы знали все аргументы, кроме четвертого И третьего #1100, нам нужно было бы найти только позже или третий или четвертый оператор "32" в зависимости от того, какой аргумент мы вывели раньше.
class Chi:
def __init__(self, n, op=[]):
'None means indeterminate'
self.observers=DiaconArray(n)
self.operators=op[:]
self.methods=[] #Invariant of the launchers
# [(function, X, Y, Z0, Z1),...]
self.launchers={} # observers no observed
# {pos:[(posMet, posArg),...],...}
# posArg respecting the string
for K in range(n):
self.launchers[K]=[]
for o in op:
self._generateInvariant(o)
В методах мы помещаем строку, выведенную в Chi.X, и позиции в массиве, которые являются аргументами операции. В средствах запуска мы помещаем для каждой заявленной позиции Нет, что такое индекс методов и строковый индекс function из этой позиции Нет. Мы будем уведомлять наблюдателя обо всех операторах в _generateInvariant.
def _generateInvariant(self, operator):
for op in operator:
if abs(op)>=len(self.observers):
n=len(self.observers)
self.observers+=DiaconArray(abs(op)-n+1)
for K in range(n,len(self.observers)):
self.launchers[K]=[]
px,py,pz0,pz1=operator
function=Chi.X[Chi.apply(self.observers[px],
self.observers[py],
self.observers[pz0],
self.observers[pz1])]
if len(function)==0:
return False
elif len(function)==1:
value= Chi.opChi[int(function)](
self.observers[px],
self.observers[py],
self.observers[pz0],
self.observers[pz1])
self[(px,py,pz0,pz1)[int(function)]]=value
return False
elif function=="10":
if not self.observers[pz0]==self.observers[pz1]:
self[px]=1
self[py]=0
return False
elif function=="20":
if self.observers[py]==1:
self[pz0]=self.observers[pz1]
return False
elif function=="30":
if self.observers[py]==1:
self[pz1]=self.observers[pz0]
return False
elif function=="21":
if self.observers[px]==0:
self[pz0]=self.observers[pz1]
return False
elif function=="31":
if self.observers[px]==0:
self[pz1]=self.observers[pz0]
return False
self.methods.append((function,px,py,pz0,pz1))
for k in range(4):
Key=(px,py,pz0,pz1)[k]
if self.observers[Key]==None:
self.launchers[abs(Key)].append(
(len(self.methods)-1,k))
return True
Чтобы понять код, вы должны соблюдать определенные части:
- Метод apply декодирует индекс X из состояния None / not- None каждого аргумента.
- если
len(function)==1означает, что новый Наблюдатель не нужен. Потому что можно решить аргумент Нет напрямую. - Есть некоторые исключения, когда новый Observer не нужен.
- Наконец, оператор добавлен в методы и настроен для каждого его средства запуска аргументов None.
В моей последней версии я реализовал разные способы обеспечения запроса: чем выше параметр temperature, тем больше возможностей дать последовательный ответ, но будет выполнено больше операций.
Структура интерфейса
Построив ядро Структуры, вы можете заметить, что с ней сложно работать: вам нужно представить каждую логическую формулу как комбинацию операторов χ. Чтобы решить эту проблему и проверить все результаты, я реализовал в том же файле класс DiaconChi.
class DiaconChi:
def __init__(self,n):
self.C = Chi(2*n)
self.n = n
self.auxiliars = 1
self.C[0] = 0
self.C[1] = 1
В этом случае мы будем использовать временные переменные в нечетных позициях массива, а пользовательские переменные - в четных позициях. Обратите внимание, что первая временная переменная равна 1, а первая пользовательская переменная - 0.
Но вот код, который нас интересует.
def _adjustN(self,*secuencia):
for X in secuencia:
if abs(X) >= self.n:
self.n = abs(X) + 1
def AND(self, result, *sec):
self._adjustN(result)
self._adjustN(*sec)
R = 2 * sec[0]
for op in sec[1:-1]:
auxiliar = 2 * self.auxiliars + 1
self.auxiliars += 1
self.C.opera([R,-2*op,0,auxiliar])
R = auxiliar
self.C.opera([R,-2*sec[-1],0,2*result])
def _ANDaux(self, rAux, *sec):
'rAux is the output'
self._adjustN(*sec)
R = sec[0]
for op in sec[1:-1]:
auxiliar = 2 * self.auxiliars + 1
self.auxiliars += 1
self.C.opera([R, -op, 0, auxiliar])
R = auxiliar
self.C.opera([R, -sec[-1], 0, rAux])
def OR(self, result, *sec):
self.AND(-result, *tuple([-X for X in sec]))
def SAT3(self, clauses):
for c in clauses:
self._ANDaux(0, -2*c[0], -2*c[1], -2*c[2])
Учитывая,
- _adjustN - это метод, который увеличивает длину массива, если этого требуют переменные.
- opera - это собственный метод, который требует операции χ.
- SAT3 реализует в массиве логическое произведение суммы трех логических литералов.
Проверим, (x + y + z) (¬x + ¬y + z) (x + ¬y + ¬z) = 1; если x = 1 и z = 0, что произойдет с y?
>>> C=DiaconChi(23) >>> C[0] 0 >>> C[1] >>> C.SAT([(1,2,3),(-1,-2,3),(1,-2,-3)]) >>> C[1] >>> C[2] >>> C[3] >>> C[1]=1 >>> C[3]=0 >>> C[2] 0 >>> C 0100-------------------
Об эффективности и точности
В этом разделе я предложу код для проверки того, когда микромашины работают правильно и насколько они быстры в секундах.
from profile import time
from random import randrange
def testGen(clauses, variables):
cc = DiaconChi(variables)
SAT3 = [[(randrange(variables)+1) * (2*randrange(2)-1) \
for Y in range(3)] \
for X in range(clauses)]
cc.SAT(SAT3)
before = time.time()
try:
for V in range(1, variables+1):
if cc[V] is None:
cc[V] = 0
except BadAssignment:
return round(time.time() - before), False
elapsedTime = time.time() - before
for (A, B, C) in SAT3:
if (cc[A] or cc[B] or cc[C]) == 0:
raise "Fatal error"
return round(elapsedTime, 4), True
В предыдущем коде мы можем наблюдать три возможных возврата:
- Если бы была неудачная попытка, она вернула бы потраченное впустую время и Ложь.
- Если бы было решение, оно вернуло бы необходимое время и True.
- Если в коде есть ошибка (не ожидаемая), появится сообщение «Неустранимая ошибка».
Чтобы получить хороший график, нам понадобится что-то вроде этого:
def precision(clauses, variables, lots):
T = 0
S = 0
for i in range(lots):
time, sucess = testGen(clauses, variables)
T += time
S += int(sucess)
return round(T/lots, 4), round(S/lots, 4)
И это вернет пару (время, точность), усредненную по лотам.
Вы можете считать, что время зависит от количества предложений (наблюдателей), а точность соотношения между переменными и предложениями (взаимосвязь между наблюдателями).
Кодекс и их выводы
Учитывая, что есть некоторые другие версии с другими операторами, может быть интересно понять, насколько легко создать эксклюзивную машину, которая дает неожиданно хорошие результаты. Можно подумать, насколько легко можно распределить наблюдателей по разным машинам в сети.
Таким образом, эти приложения специально разработаны для ситуаций, требующих быстрого реагирования и наличия эффективной распределительной сети.
Вы можете протестировать все и найти код в двух файлах моей книги Две точные философии: DiaconArray.py и diaconChi.py
