1

私は再帰に頭を悩ませています。私ができる単純な再帰ですが、これは私にとって簡単ではありません。ここでの私の目標は、この検索アルゴリズムを高速化することです。再帰が役立つと思います。子を持つ単純な 43 ノード ツリーで 15 秒かかります。以下は、機能するコードの展開された再帰形式です。

var nodeList = new Array();
         var removeList = new Array();
         var count = 0;
         var foundInThisNodeTree;

         var find = function ( condition )
         {
         }

         while ( this.treeIDMap.igTree( "nodeByPath", count ).data() )
         {
             var foundInThisNodeTree = false;
             var n;
             n = this.treeIDMap.igTree( "nodeFromElement", this.treeIDMap.igTree( "nodeByPath", count ) )
             if ( n.data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; }
             else {//look deeper
                 var i = 0;
                 while ( this.treeIDMap.igTree( "nodeByPath", count + "_" + i ).data() )
                 {
                     n = this.treeIDMap.igTree( "nodeFromElement", this.treeIDMap.igTree( "nodeByPath", count + "_" + i ) );
                     if ( n.data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                     else {//look deeper
                         var j = 0;
                         while ( this.treeIDMap.igTree( "nodeByPath", count + "_" + i + "_" + j ).data() )
                         {
                             n = this.treeIDMap.igTree( "nodeFromElement", this.treeIDMap.igTree( "nodeByPath", count + "_" + i + "_" + j ) );
                             if ( n.data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                             else {//look deeper
                                 var k = 0;
                                 while ( this.treeIDMap.igTree( "nodeByPath", count + "_" + i + "_" + j + "_" + k ).data() )
                                 {
                                     n = this.treeIDMap.igTree( "nodeFromElement", this.treeIDMap.igTree( "nodeByPath", count + "_" + i + "_" + j + "_" + k ) );
                                     if ( n.data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                                     k++;
                                 }
                             }

                             j++;
                         }
                     }
                     i++;
                 }
             }
             if ( !foundInThisNodeTree ) this.treeIDMap.igTree("removeAt", ""+count )
             else count++;
         }

** * Mirco Ellmann によって提案された 2 番目の改訂* ****

var nodeList = new Array();
         var removeList = new Array();
         var count = 0;
         var foundInThisNodeTree;
         filter = filter.toLowerCase();
         while ( this.treeIDMap.igTree( "nodeByPath", count ).data() )
         {
             var foundInThisNodeTree = false;
             var n;
             n = this.treeIDMap.igTree( "nodeFromElement", this.treeIDMap.igTree( "nodeByPath", count ) )
             if ( n.data.ITEM.toLowerCase().indexOf( filter ) > -1 ) { foundInThisNodeTree = true; }
             else {//look deeper
                 var i = 0;
                 n = this.treeIDMap.igTree( "childrenByPath", count );
                 while ( n[i] )
                 {
                     if ( n[i].data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                         var j = 0;
                         n = this.treeIDMap.igTree( "childrenByPath", count + "_" + i );
                         while ( n[j]  )
                         {
                             if ( n[j].data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                                 var k = 0;
                                 n = this.treeIDMap.igTree( "childrenByPath", count + "_" + i + "_" + j);
                                 while ( n[k] )
                                 {
                                     if ( n[k].data.ITEM.indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                                     k++;
                                 }
                             j++;
                         }

                     i++;
                 }
             }
             if ( !foundInThisNodeTree ) this.treeIDMap.igTree("removeAt", ""+count )
             else count++;
         }

****分岐可能なツリーを使用してデータを取得するため、ツリーを呼び出す必要はありません* ***

 var count = 0;
 var foundInThisNodeTree;
 filter = filter.toLowerCase();
 while ( this.treeIDMap.igTree( "nodeByPath", count ).data() )
 {
     var foundInThisNodeTree = false;
     var n;
     n = this.treeIDMap.igTree( "nodeFromElement", this.treeIDMap.igTree( "nodeByPath", count ) )
     if ( n.data.ITEM.toLowerCase().indexOf( filter ) > -1 ) { foundInThisNodeTree = true; }
     if ( n.data.branch )//look at all childer under the root node
     {      
         var i = 0;
         n = n.data.branch;
         while ( n[i] )//look at all childer under the root node
         {      
            if ( n[i].ITEM.toLowerCase().indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
            while ( n[i].branch )//look deeper
            {
                var j = 0;
                n = n[i].branch;
                if ( n[j].ITEM.toLowerCase().indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                while ( n[j].branch )//look deeper
                {
                    var k = 0;
                    n = n[j].branch;
                    if ( n[k].ITEM.toLowerCase().indexOf( filter ) > -1 ) { foundInThisNodeTree = true; break; }
                    k++;
                }

                j++;
            }

             i++;
         }
     }
     if ( !foundInThisNodeTree ) this.treeIDMap.igTree("removeAt", ""+count )
     else count++;
 }
4

3 に答える 3

0

あなたは本当にこれを再帰的にやっているわけではありません。むしろ、階層内のレベルごとにコードを繰り返しています。必要なのは、現在のノードパスをパラメーターとして受け取り、現在のノードのパスに ID を追加して、その子のそれぞれに対して同じメソッドを再帰的に呼び出すヘルパー関数です。再帰的には、コードがツリーの任意の深さで機能する必要があることを意味します。私には、あなたのコードは設定された深さでしか機能しないようです。

速度の問題については、2 つの問題が考えられます。私はあなたのコードをあまり詳しく読んでいなかったので、どちらがより可能性が高いかを判断するのはあなたに任せます。

  1. ノードを再訪している可能性があります。もしそうなら、明らかにそれはパフォーマンスに影響を与えます。

  2. 使用しているフレームワークは、ノードの検索が遅い可能性があります。1 つの解決策は、フレームワークで呼び出す別のメソッドを見つけることです。たとえば、フレームワークは内部的に階層表現を持っているかもしれませんが、完全なパスを渡すときにそれを再構築または解析する必要があります。代わりに、ソースと相対パスを取るメソッドを探してください。それが問題でない場合は、フレームワークが遅いだけかもしれません。すべてのノードを読み取り、代わりに使用する独自のメモリ内ツリーを構築する方がよい場合があります。

于 2013-05-08T18:24:09.883 に答える