3

キーと値の構造のペアを持つシステムを実装しようとしています。それらはある種の線形の方法で保持される必要があり（つまり、インデックスを付けることができます）、一度位置を指定すると移動できないため、挿入は追加することしかできません（実際には多くの並べ替えはできません）。ちょうど例として、これは心に留められていることです：

Data list:
    0: { "somekey", somevalue }
    1: { "someotherkey", someothervalue }
    ...
    n: { "justanotherkey", justanothervalue }

私はこのようなシステムを設計して、キーが検索されたときにそのインデックスをキャッシュして、一定の時間でアクセスできるようにしました。さて、データの順序や量を予測する方法がなく、並べ替えることもできないため、線形検索よりも優れたアルゴリズムやデータ構造に関するアイデアが必要ですが、それでも制約は維持されます。 dが好きです。

誰かアイデアがありますか？私はそれを大幅にスピードアップできるとは思えませんが、これが私のシステムのコアになるので、少しでも役に立ちます。前もって感謝します！

==編集==

2つの別々の構造（ハッシュテーブルと動的配列など）を使用するというアイデアは、実際には私の最初の意図でした。残念ながら、キーと値を分離できないため、これは機能しません。キーはエラーとメッセージに使用されるため、インデックスがキャッシュされた後でも、元のキーにアクセスする必要があります。基本的に、それらは次のような配列構造体である必要があります。

struct Entry {
    /* Key is actually a complex struct itself with string, and params */
    Key key;
    Data* data; 
}
4

2 に答える 2

4

ハッシュテーブルキー->配列内のインデックスはどうですか？

于 2012-02-03T00:12:14.960 に答える
2

1つのオプションは、ハッシュテーブルと動的配列の組み合わせを使用することです。考え方は次のとおりです。データ構造に要素を挿入するたびに、その要素を動的配列に追加してから、キーと値のペアが存在する動的配列のインデックスに関連付けられたハッシュテーブルにキーを挿入します。このように、インデックスで検索するには、動的配列を検索し、名前で検索するには、ハッシュテーブルでインデックスを検索してから、そのインデックスをクエリします。これには、挿入、削除、およびアクセスに予想されるO（1）時間がかかります。これは、線形検索よりもはるかに高速です。

お役に立てれば！

于 2012-02-03T00:14:03.010 に答える