Java Trieの最適化

Question

私はtrieのデータ構造で練習しています（コースワークは関係ありません）。このクラスは、文字列の部分文字列を格納するために使用されます。長さがnの文字列の場合、合計部分文字列はn(n+1)/2です。特に、trieのこの実装は、自然順序付けを保持し、ランダムな文字列のTreeMapまたはTreeSetより効率的です。文字列全体ではなく、単一の文字を格納するだけでなく、メモリに保存されます。

サフィックス配列を格納する方がよいかもしれませんが、新しいプロジェクトを開始する前に、このtrieクラスの速度が合理的に最適化されていることを確認したかったのです。

class Trie 
{ 
    final Trie my_parent; 
    final Trie[] my_children; 
    final char my_value; 

    public Trie(final Trie the_parent, final char the_value) 
    { 
     my_parent = the_parent; 
     my_value = the_value; 
     my_children = new Trie[26]; 
    } 

    public int insertIterative(final char[] the_text) 
    { 
     int number = 0; 
     Trie parent = this; 

     for(int ator = 0; ator < the_text.length; ator++) 
     { 
      final int key = the_text[ator] - 97; 
      Trie child = parent.my_children[key]; 

      if(child == null) 
      { 
       child = new Trie(parent, the_text[ator]); 
       parent.my_children[key] = child; 
       number++; 
      } 

      parent = child; 
     } 

     return number; 
    } 

    public String getString() 
    { 
     final StringBuilder builder = new StringBuilder(); 
     Trie parent = this; 

     while(parent.my_parent != null) 
     { 
      builder.append(parent.my_value); 
      parent = parent.my_parent; 
     } 

     return builder.reverse().toString(); 
    } 
} 

Answer 1

は、上記の私のコメントを参照してください、とにかく、いくつかの観察は：

あなたは26の子供は関係なく、彼らが使用されているかどうかの、すぐに試み割り当てます。あなたはこれらをゆっくりと作成できます（つまり、特定の文字に遭遇した場合のみ）。

あなたのコードは、プレーンなASCII文字のみで動作し、外国語の文字、ハイフン、アポストロフィ、大文字小文字の混在は処理しません。レイジー割り当てもこれを助けます。

実装では、charごとにTrieオブジェクトを使用し、いくつかの空きスペアを使用しているため、メモリ使用量が非常に多い可能性があります。

の結果を追加して反転するのではなく、正しい順序で収集する方が良いですが、これをベンチマークする必要があります。 Trieの深さを追跡していれば、StringBuilderではなく正しい長さの配列を割り当てることができますが、深さを追跡することは独自のメモリコストを伴います。