Clever Geek Handbook

ミニパズル：「古い学校」ツリー

問題の声明





ほんの数日前、 Eric Lippertのブログ「 Fabulous Adventures In Coding」で非常にシンプルだが面白いタスクを投稿しました。



Nodeクラスの助けを借りて定義されたツリーがあり、そこには同じノードといくつかのテキストを持つ子があります（以下にクラスコードを示します） この種の行（改行を含む）を生成する必要があります。

ユニコード文字「│├─└」を使用する必要があります（疑似画像付きの古き良き写真を思い出してください）。 エリックが自分で設定した目標は、決定を行うときにどのような設定が行われるかを見つけることです：再帰的（ツリーとして）、より高速、またはより読みやすい。





ソースコードクラスノード：

class Node<br>{<br> public Node( string text, params Node[] children)<br> {<br> this .Text = text;<br> this .Children = children ?? new Node[] {};<br> }<br> public string Text { get ; private set ; }<br> public IList<Node> Children { get ; private set ; }<br>} <br><br> * This source code was highlighted with Source Code Highlighter .







ソースデータ：

var root = new Node( "a" , <br> new Node( "b" ,<br> new Node( "c" , <br> new Node( "d" )),<br> new Node( "e" ,<br> new Node( "f" ))),<br> new Node( "g" , <br> new Node( "h" ,<br> new Node( "i" )),<br> new Node( "j" ))); <br><br> * This source code was highlighted with Source Code Highlighter .







タスクは、ここで不足している行を埋めることです。

sealed class Dumper<br>{<br> static public string Dump(Node root) { /* ... */ }<br> /* ... */ <br>} <br><br> * This source code was highlighted with Source Code Highlighter .







解決策





そのため、Habraparserで「<spoiler>」タグが見つからなかったため、明確なソリューションを提供したくありません。 自分の決定を書く喜びを自分から奪わないために、私は自分の決定へのリンクを提供し、少し説明します。



しかし、私はまだあなたの決定を書くのに十数分を費やすことをお勧めします。 IDEがないか、開始するのが面倒な場合は、 Snippet Compilerをお勧めします（ただし、.NET 3.5専用です。4.0の場合、類似するものは見つかりませんでした-ファイルを作成せずにコードを補完します）。



最初のアプローチ


最初に、実行速度を絶対に考慮せずに、最もLINQ方式に進むというタスクを自分で設定しました。 非常に興味深い結果が得られました-linq-likeオプション 。 コードには、すべてのツリーノードの再帰的な列挙と反復の両方が含まれます。 計算は「遅延」であり、すべての行はStringBuilderまたはLinkedListを使用して収集され、Joinによって収集されることに注意してください。これにより、不要な行のコピーや配列のシフトが最小限に抑えられます。



オプションが遅く出てきました。 とても。



第二のアプローチ


レイジーコンピューティングなど もちろん美しいですが、速度の観点から最適な実装を作成したかったのです。 「レベル」インデントは常に同じであり、新しいレベルを追加するたびに使用できることに注意して、 そのようなオプションで作成することにしました 。 すべて1つの機能で、補助コンテナクラスのみが追加されました。 同じStringBuilderですが、今回は、インデントの部分の配列を破棄することにしました。 繰り返しになりますが、ツリーの通過と結果の構築は同時に発生します。



このオプションは、実行速度の点で非常に優れていることを拒否しました。 すぐに少し前に走ります。エリックの「ワイド」バージョン（つまり、奥行きよりも子供の数が多いバージョン）よりも速い場合があります。



エリックの決定


さて、 エリックの決定 。 奇妙なことに、その中に、私は「クイック」決定でしたことの多くを見つけました-例えば、彼が「子供」のリストの最後のアイテムをチェックする方法。



個人的には、この問題が好きでした。何回か似たようなことを解決しなければならなかったからです。 そして、あなたの脳を伸ばすことは素晴らしいことです。



誰かがより速いオプションを思いついた場合-書いて、C＃コードを最適化するアプローチを見るのは興味深いです。 そして、この投稿はスポーツプログラミングで書かれたものに似ていますが、このタスクは実装が他のプラットフォームや言語と比較するには単純すぎるように思えます。



さらに、おそらく私の投稿は、誰かが他のタスクで使用できる興味深いアプローチを見つけるのに役立つでしょう：IEnumerableを使用してツリーを列挙するか、再帰的にしないか。 LinkedListなどを使用して文字列を作成します。



まあ、タスクが些細であると思われ、解決策に関心がない人のために、私は費やされた時間について謝罪します。



更新：

1つの関数のみの形式のlam0x86の Ericの修正バージョン： ウォッチ

Linqを積極的に使用するsteckの 2つの非常に簡潔なオプション： ウォッチ


More articles:


All Articles