#CP AVL木をパクった話 その2 Python

友人の作ったAVL木をパクった話その2です。
結論から言うと、改善しようとしてむしろ悪化しました。

オリジナル

友人氏の作ったオリジナルのリンクがこちらです。
juppy.hatenablog.com
AVL木をすべて配列で表現しています。コンセプトは前回自分が書いたものとは全く別です。
リンク先のコードのままだと複数のAVL木を扱えないのでクラスにしました。

ソースコード

class Avltree:
    ### AVL木を表現するクラス ###
    def __init__(self,max_N):
        self.key = [None] * max_N # key保存用
        self.left = [None] * max_N # left用
        self.right = [None] * max_N # right用
        self.b = [0] * max_N # balance
        self.count = 0 # 現在の要素数を保持
        
    def search(self,key,index=0):
        if self.key[index] > key:
            if self.left[index] == None:
                return False
            else:
                return self.search(key,self.left[index])
        if self.key[index] < key:
            if self.right[index] == None:
                return False
            else:
                return self.search(key,self.right[index])
        return True
        
    def end_lower(self,index):
        if self.left[index] == None:
            return self.key[index]
        else:
            return self.end_lower(self.left[index])
            
    def end_higher(self,index):
        if self.right[index] == None:
            return self.key[index]
        else:
            return self.end_higher(self.right[index])
            
    def search_lower(self,key,lower_key=None,index=0):
        if self.key[index] > key:
            if self.left[index] == None:
                return lower_key
            else:
                return self.search_lower(key,lower_key,self.left[index])
        if self.key[index] < key:
            lower_key = self.key[index]
            if self.right[index] == None:
                return lower_key
            else:
                return self.search_lower(key,lower_key,self.right[index])
        if self.left[index] == None:
            return lower_key
        else:
            if lower_key == None:
                return end_higher(self.left[index])
            else:
                return max(lower_key,self.end_higher(self.left[index]))
                
    def search_higher(self,key,higher_key=None,index=0):
        if self.key[index] > key:
            higher_key = self.key[index]
            if self.left[index] == None:
                return higher_key
            else:
                return self.search_higher(key,higher_key,self.left[index])
        if self.key[index] < key:
            if self.right[index] == None:
                return higher_key
            else:
                return self.search_higher(key,higher_key,self.right[index])
        if self.right[index] == None:
            return higher_key
        else:
            if higher_key == None:
                return self.end_lower(self.right[index])
            else:
                return min(higher_key,self.end_lower(self.right[index]))
                
    def DoubleRightRotation(self,x):
        tl = self.left[x]
        self.left[x] = self.right[self.right[tl]]
        self.right[self.right[tl]] = x
        tlr = self.right[tl]
        self.right[tl] = self.left[tlr]
        self.left[tlr] = tl
        b = self.b[tlr]
        if b == -1:
            self.b[self.right[tlr]] = 1
            self.b[self.left[tlr]] = 0
        elif b == 1:
            self.b[self.right[tlr]] = 0
            self.b[self.left[tlr]] = -1
        else:
            self.b[self.right[tlr]] = 0
            self.b[self.left[tlr]] = 0
        self.b[tlr] = 0
        return tlr 
 
    def DoubleLeftRotation(self,x):
        tr = self.right[x]
        self.right[x] = self.left[self.left[tr]]
        self.left[self.left[tr]] = x
        trl = self.left[tl]
        self.left[tr] = self.right[trl]
        self.right[trl] = tr
        b = self.b[tlr]
        if b == 1:
            self.b[self.right[trl]] = 0
            self.b[self.left[trl]] = -1
        elif b == -1:
            self.b[self.left[trl]] = 0
            self.b[self.right[trl]] = 1
        else:
            self.b[self.right[trl]] = 0
            self.b[self.left[trl]] = 0
        self.b[trl] = 0
        return trl
        
    def SingleLeftRotation(self,x):
        tr = self.right[x]
        self.b[tr] = 0
        self.b[x] = 0
        self.right[x] = self.left[tr]
        self.left[tr] = x
        return tr
        
    def SingleRightRotaion(self,x):
        tl = self.left[x]
        self.b[tl] = 0
        self.b[x] = 0
        self.left[x] = self.right[tl]
        self.right[tl] = x
        return tl
        
    def replace(self,x,p,v):
        if self.left[p] == x:
            self.left[p] = v
        else:
            self.right[p] = v
            
    def insertx(self,index,p,key):
        if self.key[index] > key:
            if self.left[index] == None:
                self.key[self.count] = key
                self.count += 1
                self.left[index] = self.count-1
            else:
                if not self.insertx(self.left[index],index,key):
                    return False
            if self.b[index] == 1:
                self.b[index] = 0
                return False
            elif self.b[index] == 0:
                self.b[index] = -1
                return True
            else:
                if self.b[self.left[index]] == 1:
                    self.replace(index,p,self.DoubleRightRotation(index))
                elif self.b[self.left[index]] == -1:
                    self.replace(index,p,self.SingleRightRotation(index))
                return False
        if self.key[index] < key:
            if self.right[index] == None:
                self.key[self.count] = key
                self.count += 1
                self.right[index] = self.count-1
            else:
                if not self.insertx(self.right[index],index,key):
                    return False
            if self.b[index] == -1:
                self.b[index] = 0
                return False
            elif self.b[index] == 0:
                self.b[index] = 1
                return True
            else:
                if self.b[self.right[index]] == -1:
                    self.replace(index,p,self.DoubleLeftRotation(index))
                elif self.b[self.right[index]] == 1:
                    self.replace(index,p,self.SingleLeftRotation(index))
                return False
        return False
            
    def insert(self,key,index=0):
        if self.key[index] == None:
            self.key[index] = key
            self.count += 1
        elif key < self.key[index]:
            if self.left[index] == None:
                self.key[self.count] = key
                self.count += 1
                self.left[index] = self.count-1
            else:
                self.insertx(self.left[index],index,key)
        elif key > self.key[index]:
            if self.right[index] == None:
                self.key[self.count] = key
                self.count += 1
                self.right[index] = self.count-1
            else:
                self.insertx(self.right[index],index,key)
        else:
            pass

使用法

  • コンストラクタ : Avltree(max_N)
    • max_N : 木に入れられる最大の要素数(int)
    • 返り値 : Avltree オブジェクト
  • 要素検索 : search(key)
    • key : 検索する要素
    • 返り値 : True if 要素が存在する else False
  • 最大のkey未満の要素検索 : search_lower(key)
    • key : 基準値
    • 返り値 : key未満の最大要素 存在しなければNone
  • 最小のkeyより大きい要素検索 : search_higher(key)
    • key : 基準値
    • 返り値 : keyより大きい最小要素
  • 木への要素の挿入 : insert(x)
    • x : 挿入する要素
    • 返り値 : ダブりなく挿入できればTrue?

実行速度結果比較

前回自分が書いたものが、
f:id:harutech:20190226221800p:plain
でしたが、今回は以下のようになりました。まずはmain関数として以下のものを用い。forで10回回しました。

def main():
	start = time.time()
	treeA = Avltree(10**5)
	for i in range(0,10**5):
		treeA.insert(i)
	for i in range(1,10**5):
		treeA.search_higher(i)
		treeA.search_lower(i)
	print(time.time()-start)

f:id:harutech:20190301232744p:plain

結果および考察

はい。遅くなりました。
彼のサイトのページでは前回の自分のより早い結果が出ているみたいですが、これが遅くなってる原因はおそらく” . ”での参照でしょうか。
www.peignot.net
ここのページにも書いてありますが、” . ”での参照は毎回評価するらしいので遅くなるらしいです。これに関しては改善の余地がありそうです。正直それ以外はわからないです。教えてください。ここ改善できそうだよとかあったら教えてください。