Pythonデータ構造とアルゴリズム(20,AVLツリーと二分探索ツリーの性能比較)

1週間に2編増えることを保証して、それによって自分のよく勉強することを促します!コードの多くの場所で私は詳細な説明をして、理解を助けました.よし、やれば終わりだ～がんばれ!声明:本pythonデータ構造とアルゴリズムはimooc上のliuyubobo先生javaデータ構造のpythonが書き換え、自分の理解と新しいものを追加しました.liuyubobobo先生は本当に素晴らしい先生です.彼が大好きです～間違いがあったら、仲間たちに指摘してもらい、一緒に勉強してください～
一、テストコードの実現

前期は自己平衡機構を持つAVLツリーを学びましたが、普通の二分探索ツリーよりどれだけ速いのでしょうか.テストコードを見てみましょう.

# -*- coding: utf-8 -*-
# Author:           Annihilation7
# Data:             2019-02-17  00:07 am
# Python version:   3.6

from binarysearchTree import bst
from avl import avl_tree

import time
import numpy as np
import random  
import copy


class Test_factory:
    def __init__(self, data_nums):
        self.data_nums = data_nums  #     
        # self.data1 = [np.random.randint(200000) for i in range(self.data_nums)]
        self.data1 = [i for i in range(self.data_nums)]  #                       O(n)      ！
        self.data2 = copy.deepcopy(self.data1) #    data1
        self.data3 = copy.deepcopy(self.data1)
        random.shuffle(self.data2)  #   data2
        random.shuffle(self.data3)

    def __call__(self, bst_object):
        start_time = time.time()
        for val in self.data1:
            bst_object.add(val)  # data_nums add  
        for val in self.data2:
            bst_object.contains(val)  # data_nums     
        for val in self.data3:
            bst_object.remove(val)  # data_nums     
        end_time = time.time()
        print('{}   ： {}s'.format(bst_object, end_time - start_time))


if __name__ == '__main__':
    op_nums = 900 # [0, 899]
    bst = bst.BST()
    avl = avl_tree.Avltree()
    test_factory = Test_factory(op_nums)
    test_factory(avl)
    test_factory(bst)

二、テスト出力

AVL    ： 0.05291891098022461s
        ： 0.31839799880981445s

三、総括と問題

上記の比較テストから、データ量が900の場合、AVLツリーは従来の二分探索ツリーブロックの6倍近くになることがわかりました.データ量がある程度大きくなると利点がより顕著になります.

op_をnumsが1000に増大すると,二分探索ツリー追加ノードが最大再帰深さを超えたエラーが報告される.RecursionError:maximum recursion depth exceedAVLツリーはエラーを報告しません.以前の二分検索ツリーのコードを繰り返しチェックし、debugも行いましたが、何の問題も見つかりませんでした.だから私のテストデータ量は最終的に900になりました.仲間たちはデータセットを増やしてみて、かばんを見て間違いを報告しないことができます.私自身もプログラムを書いて、私のパソコンのpythonの最大再帰深さを見て、19377で、私もなぜ間違っているのか分かりません.

データをテストコードの注釈に変更するとself.data 1=[np.random.randint(200000)for i in range(self.data_nums)]のとき、avlツリーが二分検索ツリーより遅いことに気づきました!!同じく私をとても困らせて、二分検索ツリーのコードをチェックして、avlツリーのコードとテストコードの各方面はすべていかなる問題を発見していません!回転操作の時間がかかったのか.皆さんもその文でテストしてもいいですが、私のパソコンの問題かどうか分かりません.--つらいよああ～～/(ㄒo125679182)/

改善、最適化できる点があれば、仲間たちに批判してもらいたい.