Python - использование регулярных выражений в экземпляре класса
У меня есть класс, который брал в списках 1 и 0 и выполнял арифметические операции конечного поля GF(2). Раньше он работал, пока я не попытался заставить его принимать входные данные в полиномиальном формате. Что касается того, как будет выполняться конечная арифметика после исправления проблемы регулярных выражений, я думал о перегрузке операторов.
Фактический код в parsePolyToListInput(input) работает когда вне класса. Проблема, кажется, в регулярном выражении, ошибки которого он принимает только в строке (это имеет смысл), но, похоже, не инициализируется с параметром self.expr (это проблема). @Staticmethod незадолго до инициализации была попыткой спасти несвязанную ошибку при передаче полинома, но это, по-видимому, совершенно неверно. Просто чтобы сэкономить ваше время, если вы решите взглянуть на любую из арифметических операций, модульное обратное не работает (похоже, из-за проблемы форматирования после каждой итерации цикла while для деления в функции и типа возвращаемого значения):
import re
class gf2poly:
#binary arithemtic on polynomials
#@staticmethod
def __init__(self,expr):
self.expr = expr
#self.expr = [int(i) for i in expr]
self.expr = gf2poly.parsePolyToListInput(self.expr)
def convert(self): #to clarify the input if necessary
convertToString = str(self.expr)
print "expression is %s"%(convertToString)
def id(self): #returns modulus 2 (1,0,0,1,1,....) for input lists
return [int(self.expr[i])%2 for i in range(len(self.expr))]
def listToInt(self): #converts list to integer for later use
result = gf2poly.id(self)
return int(''.join(map(str,result)))
def prepBinary(a,b): #converts to base 2 and orders min and max for use
a = gf2poly.listToInt(a); b = gf2poly.listToInt(b)
bina = int(str(a),2); binb = int(str(b),2)
a = min(bina,binb); b = max(bina,binb);
return a,b
@staticmethod
def outFormat(raw):
raw = str(raw[::-1]); g = [] #reverse binary string for enumeration
[g.append(i) for i,c in enumerate(raw) if c == '1']
processed = "x**"+' + x**'.join(map(str, g[::-1]))
if len(g) == 0: return 0 #return 0 if list empty
return processed #returns result in gf(2) polynomial form
def parsePolyToListInput(poly):
c = [int(i.group(0)) for i in re.finditer(r'\d+', poly)] #re.finditer returns an iterator
#m = max(c)
return [1 if x in c else 0 for x in xrange(max(c), -1, -1)]
#return d
def add(self,other): #accepts 2 lists as parameters
a = gf2poly.listToInt(self); b = gf2poly.listToInt(other)
bina = int(str(a),2); binb = int(str(b),2)
m = bina^binb; z = "{0:b}".format(m)
return z #returns binary string
def subtract(self,other): #basically same as add() but built differently
result = [self.expr[i] ^ other.expr[i] for i in range(len(max(self.expr,other.expr)))]
return int(''.join(map(str,result)))
def multiply(a,b): #a,b are lists like (1,0,1,0,0,1,....)
a,b = gf2poly.prepBinary(a,b)
g = []; bitsa = "{0:b}".format(a)
[g.append((b<<i)*int(bit)) for i,bit in enumerate(bitsa)]
m = reduce(lambda x,y: x^y,g); z = "{0:b}".format(m)
return z #returns product of 2 polynomials in gf2
def divide(a,b): #a,b are lists like (1,0,1,0,0,1,....)
a,b = gf2poly.prepBinary(a,b)
bitsa = "{0:b}".format(a); bitsb = "{0:b}".format(b)
difflen = len(str(bitsb)) - len(str(bitsa))
c = a<<difflen; q=0
while difflen >= 0 and b != 0: #a is divisor, b is dividend, b/a
q+=1<<difflen; b = b^c # b/a because of sorting in prep
lendif = abs(len(str(bin(b))) - len(str(bin(c))))
c = c>>lendif; difflen -= lendif
r = "{0:b}".format(b); q = "{0:b}".format(q)
return r,q #returns r remainder and q quotient in gf2 division
def remainder(a,b): #separate function for clarity when calling
r = gf2poly.divide(a,b)[0]; r = int(str(r),2)
return "{0:b}".format(r)
def quotient(a,b): #separate function for clarity when calling
q = gf2poly.divide(a,b)[1]; q = int(str(q),2)
return "{0:b}".format(q)
def extendedEuclideanGF2(a,b): # extended euclidean. a,b are GF(2) polynomials in list form
inita,initb=a,b; x,prevx=0,1; y,prevy = 1,0
while sum(b) != 0:
q = gf2poly.quotient(a,b);
q = list(q); q = [int(x) for x in q]
#q = list(q);
#q = tuple([int(i) for i in q])
q = gf2poly(q)
a,b = b,gf2poly.remainder(a,b);
#a = map(list, a);
#b = [list(x) for x in a];
#a = [int(x) for x in a]; b = [int(x) for x in b];
b = list(b); b = [int(x) for x in b]
#b = list(b);
#b = tuple([int(i) for i in b])
b = gf2poly(b)
#x,prevx = (prevx-q*x, x);
#y,prevy=(prevy-q*y, y)
print "types ",type(q),type(a),type(b)
#q=a//b; a,b = b,a%b; x,prevx = (prevx-q*x, x); y,prevy=(prevy-q*y, y)
#print("%d * %d + %d * %d = %d" % (inita,prevx,initb,prevy,a))
return a,prevx,prevy # returns gcd of (a,b), and factors s and t
def modular_inverse(a,mod): # where a,mod are GF(2) polynomials in list form
gcd,s,t = gf2poly.extendedEuclideanGF2(a,mod); mi = gf2poly.remainder(s,mod)
#gcd,s,t = ext_euc_alg_i(a,mod); mi = s%mod
if gcd !=1: return False
#print ("%d * %d mod %d = 1"%(a,mi,mod))
return mi # returns modular inverse of a,mod
Я обычно проверяю это с этим входом:
a = x**14 + x**1 + x**0
p1 = gf2poly(a)
b = x**6 + x**2 + x**1
p2 = gf2poly(b)
Первое, что вы можете заметить в моем коде, это то, что он не очень хорош. Для этого есть 2 причины:
1) Я написал так, чтобы 1-я версия могла выполнять работу в конечном поле GF(2) и выводить в полиномиальном формате. Затем следующие версии должны были принимать полиномиальные входы, а также выполнять важную функцию "модульного обратного преобразования", которая не работает, как планировалось (это означает, что она вообще не работает).
2) Я учу себя Python (на самом деле я учу себя программированию в целом), поэтому любая конструктивная критика со стороны профессиональных программистов Python приветствуется, так как я стараюсь как можно быстрее избавиться от привычки новичка.
РЕДАКТИРОВАТЬ:
Может быть, еще немного кода, с которым я тестировал, поможет уточнить, что работает, а что нет:
t1 = [1,1,1]; t2 = [1,0,1]; t3 = [1,1]; t4 = [1, 0, 1, 1, 1, 1, 1]
t5 = [1,1,1,1]; t6 = [1,1,0,1]; t7 = [1,0,1,1,0]
f1 = gf2poly(t1); f2 = gf2poly(t2); f3 = gf2poly(t3); f4 = gf2poly(t4)
f5 = gf2poly(t5);f6 = gf2poly(t6);f7 = gf2poly(t7)
##print "subtract: ",a.subtract(b)
##print "add: ",a.add(b)
##print "multiply: ",gf2poly.multiply(f1,f3)
##print "multiply: ",gf2poly.multiply(f1,f2)
##print "multiply: ",gf2poly.multiply(f3,f4)
##print "degree a: ",a.degree()
##print "degree c: ",c.degree()
##print "divide: ",gf2poly.divide(f1,b)
##print "divide: ",gf2poly.divide(f4,a)
##print "divide: ",gf2poly.divide(f4,f2)
##print "divide: ",gf2poly.divide(f2,a)
##print "***********************************"
##print "quotient: ",gf2poly.quotient(f2,f5)
##print "remainder: ",gf2poly.remainder(f2,f5)
##testq = gf2poly.quotient(f4,f2)
##testr = gf2poly.remainder(f4,f2)
##print "quotient: ",testq,type(testq)
##print "remainder: ",testr,type(testr)
##print "***********************************"
##print "outFormat testp: ",gf2poly.outFormat(testq)
##print "outFormat testr: ",gf2poly.outFormat(testr)
##print "***********************************"
#print "gf2poly.modular_inverse(): ",gf2poly.modular_inverse(f2,f3)
print "p1 ",p1 #,type(f2),type(f3)
#print "parsePolyToListInput ",gf2poly.parsePolyToListInput(a)
1 ответ
Часть вашей проблемы в том, что вы не заявили self в качестве аргумента для parsePolyToListInput, Когда вы вызываете метод, экземпляр, к которому вы его вызываете, неявно связан как первый аргумент. Называя первый аргумент self это соглашение, а не строгое требование - экземпляр привязан к poly, который вы затем пытаетесь запустить регулярное выражение.
Мне кажется, что в вашем дизайне есть некоторая путаница относительно поведения отдельных экземпляров класса и поведения уровня класса или модуля. В Python вполне допустимо оставлять что-то, что не принимает экземпляр класса, в качестве параметра, определенного как функция уровня модуля, вместо того, чтобы неловко вводить его в заблуждение. parsePolyToListInput может быть одной из таких функций.
Ваш add реализация, аналогично, имеет комментарий о том, что "принимает 2 списка в качестве параметров". На самом деле, он собирается получить gf2poly экземпляр в качестве первого аргумента - это, вероятно, правильно, если вы планируете перегрузку оператора, но это означает, что второй аргумент также должен быть gf2poly экземпляр также.
РЕДАКТИРОВАТЬ: Да, ваш пример кода показывает разрыв между поведением класса и поведения экземпляра. Либо ваш умноженный вызов должен выглядеть примерно так:
print "multiply: ",f1.multiply(f3)
Или умножение не должно быть методом вообще:
gfpoly.py:
def multiply(f1, f2):
a,b = prepBinary(a,b)
g = []; bitsa = "{0:b}".format(a)
[g.append((b<<i)*int(bit)) for i,bit in enumerate(bitsa)]
m = reduce(lambda x,y: x^y,g); z = "{0:b}".format(m)
return z #returns product of 2 polynomials in gf2
Этот последний подход, например, как стандарт math Библиотека делает вещи.
Преимущество определения метода умножения состоит в том, что вы можете назвать его соответствующим образом ( http://docs.python.org/2/reference/datamodel.html) и использовать его с * оператор:
print "multiply: ",f1 *f3