Pythonのバイナリツリー

Question

私はPythonでバイナリツリーを実装する必要があります。ツリーの1つのノードにはいくつかの属性があります。私の要件の1つは、メモリ使用量、特にデータ構造のオーバーヘッドの最小限のものです。

私の質問は、実装のさまざまな方法によってどのくらいのオーバーヘッドが生成されるかです。私は、あるキーが "左"で、もう一つが子ノードの "右"である辞書を使うことを考えています。もう1つの方法は、子に「左」と「右」の属性を持つクラスを使用することです。

これらの2つのオプションには、目立つ利点や欠点がありますか？それとももっと良い選択肢がありますか？

Python標準ライブラリを使用する必要があります。Python 3.5を使用しています。

Answer 1

私はあなたがそれを実装するクラス、辞書、およびnamedtupleを使用することができると思います。

クラスを使用する場合：

class BNode(object): 
    def __init__(self, val): 
     self.val = val 
     self.left = None 
     self.right = None 

import sys 
b = BNode(5) 
sys.getsizeof(b) 

これは、Python 3.5.2と私のPC上で56を返します。 最適化したい場合は、__slot__ atrributeを追加します。

class BNode(object): 
    __slot__ = ('val','left','right') 
    def __init__(self, val): 
     self.val = val 
     self.left = None 
     self.right = None 

b = BNode(5) 

これも私のPCで56を返します。あなたは辞書を使用する場合は

：

node_dict = {'left':None, 'right':None, 'val':5} 
sys.getsizeof(node_dict) 

これは私のPC上で288を返します。

別のオプションがあります：namedtuple

を使用して、これは私のPC上で76を返します。

上記のコードによれば、memeoryの制限を考慮するためにコードを実装するには、クラスに__slot__を使用する必要があります。

Answer 2

Python dictsはメモリが重いです。

デフォルトで

、クラスのインスタンスは属性 ストレージ用の辞書を持っている：あなたは__slots__の利点を取る場合は、動的な属性を必要としないクラスはcomparitively軽量することができます。これは、非常にわずかなインスタンス 変数を持つオブジェクトのためのスペースを無駄にします。大きな数字の インスタンスを作成すると、スペース消費量が急になる可能性があります。

定義で__slots__を定義すると、デフォルトを上書きできます。 __slots__宣言は、インスタンス の変数のシーケンスを取り、それぞれの変数に の値を保持するだけの十分な領域を各インスタンスに確保します。 __dict__は各インスタンスに対して が作成されていないため、領域が節約されます。

は考えてみましょう：

In [1]: class Node(object): 
    ...:  __slots__ = ('left', 'right','data') 
    ...:  def __init__(self, left, right, data): 
    ...:   self.left = left 
    ...:   self.right = right 
    ...:   self.data = data 
    ...: 

In [2]: n = Node(None, None, None) 

In [3]: d = {} 

In [4]: import sys 

In [5]: sys.getsizeof(n) 
Out[5]: 64 

In [6]: sys.getsizeof(d) 
Out[6]: 288