#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?
実行速度結果比較
前回自分が書いたものが、
でしたが、今回は以下のようになりました。まずは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)
結果および考察
はい。遅くなりました。
彼のサイトのページでは前回の自分のより早い結果が出ているみたいですが、これが遅くなってる原因はおそらく” . ”での参照でしょうか。
www.peignot.net
ここのページにも書いてありますが、” . ”での参照は毎回評価するらしいので遅くなるらしいです。これに関しては改善の余地がありそうです。正直それ以外はわからないです。教えてください。ここ改善できそうだよとかあったら教えてください。