94 lines
5.7 KiB
Python
94 lines
5.7 KiB
Python
# https://stepik.org/lesson/701984/step/10?unit=702085
|
||
|
||
|
||
class DecisionTree:
|
||
@classmethod
|
||
def predict(cls, root, x):
|
||
"""для построения прогноза (прохода по решающему дереву) для вектора x из корневого узла дерева root"""
|
||
if not root.is_leaf:
|
||
return cls.predict(root.left if x[root.indx] else root.right, x)
|
||
return root.value
|
||
|
||
@classmethod
|
||
def add_obj(cls, obj, node=None, left=True):
|
||
"""для добавления вершин в решающее дерево (метод должен возвращать добавленную вершину - объект класса TreeObj);
|
||
|
||
В методе add_obj параметры имеют, следующие значения:
|
||
|
||
obj - ссылка на новый (добавляемый) объект решающего дерева (объект класса TreeObj);
|
||
node - ссылка на объект дерева, к которому присоединяется вершина obj;
|
||
left - флаг, определяющий ветвь дерева (объекта node), к которой присоединяется объект obj (True - к левой ветви; False - к правой).
|
||
"""
|
||
|
||
if node:
|
||
if left:
|
||
node.left = obj
|
||
else:
|
||
node.right = obj
|
||
return obj
|
||
|
||
|
||
class TreeObj:
|
||
def __init__(self, indx, value=None):
|
||
"""indx - проверяемый индекс (целое число);
|
||
value - значение с данными (строка);
|
||
__left - ссылка на следующий объект дерева по левой ветви (изначально None);
|
||
__right - ссылка на следующий объект дерева по правой ветви (изначально None).
|
||
"""
|
||
self.indx, self.value, self.__left, self.__right = indx, value, None, None
|
||
|
||
@property
|
||
def left(self):
|
||
return self.__left
|
||
|
||
@property
|
||
def is_leaf(self):
|
||
return self.__left is None and self.__right is None
|
||
|
||
@left.setter
|
||
def left(self, left):
|
||
self.value = None
|
||
self.__left = left
|
||
|
||
@property
|
||
def right(self):
|
||
return self.__right
|
||
|
||
@right.setter
|
||
def right(self, right):
|
||
self.value = None
|
||
self.__right = right
|
||
|
||
|
||
# --------------------------
|
||
|
||
|
||
def use():
|
||
root = DecisionTree.add_obj(TreeObj(0))
|
||
v_11 = DecisionTree.add_obj(TreeObj(1), root)
|
||
v_12 = DecisionTree.add_obj(TreeObj(2), root, False)
|
||
DecisionTree.add_obj(TreeObj(-1, "будет программистом"), v_11)
|
||
DecisionTree.add_obj(TreeObj(-1, "будет кодером"), v_11, False)
|
||
DecisionTree.add_obj(TreeObj(-1, "не все потеряно"), v_12)
|
||
DecisionTree.add_obj(TreeObj(-1, "безнадежен"), v_12, False)
|
||
|
||
x = [1, 1, 0]
|
||
res = DecisionTree.predict(root, x) # будет программистом
|
||
print(res)
|
||
assert res == "будет программистом", "будет программистом же?"
|
||
|
||
|
||
use()
|
||
|
||
# --------------------------
|
||
|
||
import marshal
|
||
import base64
|
||
import types
|
||
|
||
# print(base64.b85encode(marshal.dumps(tests1.__code__)))
|
||
|
||
testsb = b";{X5v000000000000sa600RI30P|`C005T&bO8VW000000049X0000000000WC5!J000000043jbO8VW000000049X0000000000WCE)K000000046bN&sX7s{jB100000f&p{|0000000000bOrzb00000003$T0000000000000000000000652000000049f0000000000YbXE!av*dC0000000000bOrzb00000003$X0000000000000000000000652000000049f0000000000YbXE!a|cQQWCW`K00000004pkbOHbX00000003$a000000000000000000000049c0000000000WCg1M000000065200000004aebOHbX00000003$a000000000000000000000049c0000000000WCp7N00000004Xds{#N300000eF1a=0000000000Y7YPa00000000000000000000bO!(c00000003kMs{sH200000d;nw!s{;T400000eFAg>0000000000Y7YPa00000000000000000000bO!(c00000003kOWD2VS00000004Xes{#N3000000RVIY0000000000Y7YPa00000000000000000000bO!(c00000003kOWDBbT00000004XeWC*JR0000000031bOHbX00000003$a000000000000000000000049c0000000000WC>&ps{#N300000d;+Ti0000000031bOHbX00000003$a000000000000000000000049c0000000000WC>&qs{#N300000d;(+$s{;T4000000RVIY0000000000Y7qbc00000000000000000000d;n(vWDcSMs{#N300000WD0920046bN&sXJs{jB100000f&p{_0000000000Y7qbc00000000000000000000d;n(vWDueOs{#N300000WDRR50046bN&sXJs{jB100000f&p{_0000000000Y7qbc00000000000000000000d;n(vWD%kPs{#N300000WDIL40046bN&sXJs{jB100000f&qB|DH2ZF2VrDnUvFY++6QoQWn^h%boEjI007XkAkezdyU?)Ffzg4`wID=gV`+0~Z*Ej_Wo01Hw9vlLyU@1Kz0r#x(6P~r(Sp&8Ake(fwb6pmzR<MMiy&cSWM6M$Y9P?KAaHVJWNBk`^;-Y{0MN1^(7MpO(6G^g(SgvlAXIW?Wlv&iAkehXzR<hSw$Q!Niy+Xk(TmZ7(TpI_zR<DJiqN&ty3vBsi!ITC(6Z3J(7Dlp(Sp#j(6AtEWoC3B(6}ISX=iA3=>Px#0O<h$008L%0000+>Hq)#|MeCC007Xx(SXpt(6iBi(6G?F(7e#N(Sgx|^$Gw00MNS7zR<MLwb6j}5&!@I(7({W(Sgvs(7w@v(SXpn(7g2q0002cz0kGMf++)X2LJ#7at8na0CENZ008wn0002cz0kGLve32BfY80si_p0s(6Z5s(6Z3J(6k`YfY7zkh|sXnj?szGwa~NBz97)F(6!Nk(6!LA(6A{3as~hZ0CEQa0043Z0000f19Aoc0043a0001T2LJ#7DGAyKXkl|<baZms3`AvPX>)0BZd7t*W!eOEd2nUg2UK!pWlv&i+5~K6W^~#JaB^>OWpZ?R+68iHXJ~YC0ssI2asvPW04W371afb0blL=VUokP-1a@CBGIIj}001B$Ao?^!I$UI7bYWa<VPafxd0cd5b960ZZ*_8WWpi9@Z)9I@Z*W{>Wn*b`X>V>{baG{7E^v9;1$1R|baQeV000090001Ub^!nYfB@VJ5|lik8Pp3av<KV>6p(530|GGy@Bjh@Tmj$*Tl5721zZ922mlEUj8~6biCohN8k}g-2qvsFv<J5hu?^EJKEx=}D@yPK0tICO;0I*%1p)<S0rUs}3>eo7AJGdRqz9-0qYBdtD}Y4Y3m4Z5AJGdRqz9-0qY9`*(+e?xMBED(*9#xf3m>Ehr~#u2s6?<O(+fC&MBD@r*8~{R1Q?tbpc2p}J<}OJzy#C;Mcf1s*8~{R1Q?tbpc0^5(-|_bM7Sl?1VG#b5Z444(F7Qr7oZZ*B{|a>I=DpC1VP*c5Z444(F7Qr7oZZLSkoCUumrGW)C4^A1^@{a*9aWZ2ppJHqB+wDEzmJZ(g;cL0|Es_0pJHj^aTP1MFI2(00|Y>2prJ}9GFz1InxL&uo%(^Iq(Al1w{ei2SoG*0tH0@^aub671szH(Fh!vRH8Z42rbYtMbZdG@B;z`MFHRkMDzs$1w{ea2u1S%0000"
|
||
tests = types.FunctionType(marshal.loads(base64.b85decode(testsb)), globals(), "tests")
|
||
tests()
|