6

タグを含む stackoverflow の投稿をできるだけ効率的に (バイナリで) シリアライズおよびデシリアライズしたいと想像してみてください。そのようなシナリオに適したデータ構造はありますか?

Stackoverflow には約 28532 の異なるタグがあり、すべてのタグを含むテーブルを作成して整数を割り当てることができます。さらに、最も一般的なタグの番号が最小になるように頻度で並べ替えることができます。「1 32 45」の形式の文字列のように単純にそれらを保存することは、検索と保存の観点からは少し効率が悪いようです

もう 1 つのアイデアは、タグを変数 bitarray として保存することです。これは、ルックアップとシリアル化の観点から魅力的です。最も一般的なタグが最初にあるため、タグを少量のメモリに収めることができる可能性があります。

もちろん、問題は、一般的ではないタグが巨大なビット配列を生成することです。大きな範囲の 0 のビット配列を「圧縮」するための標準はありますか? それとも、他の構造を完全に使用する必要がありますか?

編集

DB ソリューションやテーブル全体をメモリに保持する必要があるソリューションを探しているのではなく、個々のアイテムをフィルタリングするための構造を探しています

4

4 に答える 4

3

あなたの質問を否定するつもりはありませんが、28,000 レコードは実際にはそれほど多くありません。おそらく時期尚早に最適化していますか？最初に、DB テーブルで「通常の」インデックスを使用することに固執します。彼らが使用する過酷なヒューリスティックは、通常、非常に効率的であり、打ち負かすのは簡単ではありません (または、時間内に努力するだけの価値があり、利益が十分に大きいか?)。

また、実際にタグ クエリを実行する場所によっては、ユーザーは、最適化した 200 ミリ秒のタイム ゲインに本当に気付いているでしょうか?

最初に測定してから最適化します:-)

編集

DB がなければ、すべてのタグを ID とともに保持するマスター テーブルがおそらく存在します (可能であれば、メモリに保持します)。各投稿とともに、定期的に並べ替えられた ID のリストを保持します。

共通性に基づくストレージの量が役立つかどうかはわかりません。通常のバイナリ検索を実行できるソートされたリストは、十分に高速であることが証明される場合があります。測定 ：-）

ただし、ここでは、すべてのタグクエリに対してすべての投稿を繰り返す必要があります。

これが遅くなる場合は、各タグの投稿識別子のポケットを保存することに頼ることができます. ただし、このデータ構造は多少大きくなる可能性があり、シークして読み取るためにファイルが必要になる場合があります。

小さいテーブルの場合は、ハッシュ値 (重複あり) に基づいてテーブルを作成することに頼ることができます。このようにして、それを使用して、一致するかどうかをさらに確認する必要がある投稿のより小さな候補リストをすばやく取得できます。

于 2010-11-23T09:05:14.140 に答える
2

2 つのフィールドを持つ 2 番目のテーブルが必要です: tag_id question_id

それでおしまい。次に、tag_id、question_id、および question_id、tag_id にインデックスを作成します。これはインデックスをカバーするため、すべてのクエリが非常に高速になります。

于 2010-11-23T08:59:57.383 に答える
1

質問を抽象化しすぎたような気がします。データ構造にアクセスする方法についてあまり言及していませんでした。これは非常に重要です。

そうは言っても、各タグの出現回数を数えてから、ハフマンコーディングを使用して、タグに使用できる最短のエンコーディングを見つけることをお勧めします。これは完全に完璧というわけではありませんが、不適切であることが示されるまで、このままにしておきます。その後、コードを各質問に関連付けることができます。

于 2010-11-23T09:41:55.827 に答える
0

特定のタグ内の質問を効率的に検索したい場合は、ある種のインデックスが必要になります。おそらく、すべての Tag オブジェクトは、この特定のタグでタグ付けされたすべての質問への参照 (参照、ポインタ、数値 ID など) の配列を持つことができます。このように、タグ オブジェクトを見つけるだけで、そのタグのすべての質問を指す配列が得られます。

于 2010-11-24T15:15:19.910 に答える