0

BSTのシリアル化についてどの程度正確に行っていますか？最も効率的な方法でそれを行う正しい方法は何ですか？さて、これはあまりにも一般的すぎるので、私が何を意味するのかを説明させてください。

ここにいくつかの擬似擬似コードがあります：

public int[] serialize(root){
    preorder traversal 
    convert node to binary representation
    add the binary representation to an array
    send array via stream
}

または

public int serialize(root){
    preorder traversal 
    convert node to binary representation
    send the binary representation via stream
}

私の質問は、配列を作成してビットでいっぱいに送信することですが、これは効率的ですか？または、配列のアイデア全体をスキップして、ノードが変換されるたびに、それを送信して逆シリアル化する必要がありますか？おそらく、これらの実装は両方とも愚かです。どんな助けでもいただければ幸いです。

4

4 に答える 4

1

Googleプロトコルバッファhttps://developers.google.com/protocol-buffers/docs/overviewもご覧になることをお勧めします

于 2012-08-21T02:24:52.577 に答える
0

ツリーとデータの種類によって異なります。ツリー内のノードの順序が重要な場合は、それを再作成するために十分な情報を保存する必要があります。配列内にある場合は、配列内の位置を使用して構造を再作成できます

于 2012-08-21T02:24:58.267 に答える
0

プレオーダーとインオーダーは一意ではないため、BST はポストオーダーでのみシリアル化できます。

1) 先行予約で一意ではない

      root                     root
    /     \                   / 
  left    right             left
                               \
                               right

2) 順序が一意でない

     1                 1
    /                   \    
   2                     2
于 2013-01-25T14:23:57.550 に答える
0

「ストリーム」によって C++ iostream について話している場合、それらは既に妥当なサイズでバッファリングされており、そのバッファに挿入するコストは非常に低くなります。標準ライブラリは成熟しています。独自のゲームでそれを打ち負かすのは非常に困難です。そして、価値のあるものを得るために利用できる、悪用可能な詳細が必要になります。それは言った：

出力バッファの大きさ (縮退の場合は単一要素バッファ、つまりバッファリングなし) は、バッファ フラッシュのオーバーヘッドに依存します。そのオーバーヘッドには、固定コストとサイズ関連のコストがあります。キャッシュの影響を考えると、単純な線形のコストではありません。より高価な固定オーバーヘッドでは、より大きなバッファーが固定費の償却に役立ちます。たとえば、バッファ フラッシュがゼロ コピー I/O をトリガーできる場合、大規模なシリアライゼーションをすべてバッファリングする方が劇的にコストがかからない可能性がありますが、出力操作がソース バッファをコピーする場合、バッファ サイズはL1 キャッシュ サイズは、フラッシュの固定コストが低い場合に適切な選択です。

シリアライゼーションにかかる時間がクリティカル パスに置かれない限り、これはまったく問題ではありません。つまり、ユーザーが待ち望んでいるものにします。このようなものについては、何百万ものアイテムについて話していない限り、作成するのが難しくなっています。それでも、まだ取り組んでいない場合は、選択したバッファリング スキームよりも個々のシリアライゼーションを作成する方法の方が無駄が多いことはほぼ確実です。それでも、レースしていることを決して忘れません。I/O帯域幅ですか？シリアル化されたストリームを低品質のコンプレッサーで送信すると、事前に行うよりも簡単に多くの時間を節約できます。

于 2013-01-25T18:46:51.620 に答える