1

学校のプロジェクトの締め切りの数時間前にそれを達成できるかどうかを確認するために、これを決定する必要がありますが、データ構造についてあまり理解していないため、提案が必要です...

私がしなければならないことが 2 つあります。それらはおそらく異なるデータ構造を使用するでしょう。

  1. プロファイル レコードを保持するためのデータ構造が必要です。プロファイルは、名前と社会保障番号で検索できる必要があります。SSN は独自のものなので、それを有利に利用できるでしょうか? ここではハッシュマップが最善の策だと思いますか? しかし、ハッシュ マップで SSN を使用して、特定のプロファイルを探す際の利点として使用するにはどうすればよいでしょうか? 基本的で分かりやすい説明は大歓迎です。

  2. 都市に関するレコードを保持するためのデータ構造が必要です。訪問者が最も多い都市、訪問者が少ない都市、および特定の都市を訪問するクライアント (クライアントに関するデータのプロファイルは #1 のデータ構造から取得されます)を知る必要があります。

これは私のプロジェクトに必要な 3 番目のデータ構造であり、どこから始めればよいか分からないデータ構造です。使用するデータ構造のタイプに関する提案は、可能であれば、上記のデータを太字で古いものにする方法の例とともに高く評価されます。

注:最初のデータ構造は既に完了しています (以前の質問
で話しました)。2 つ目はここ #1 に投稿されています。他のグループ メンバーが対応していますが、私たちがやろうとしていることが「最善の」アプローチであるかどうかを知る必要があります。3 番目は #2 で、私が最も助けを必要としているものです。

4

3 に答える 3

3

正しい答えは、バランスの取れた検索ツリーと配列の間のどこかにあります。

ここで言及した状況とelse-threadは、非常に重要な点、つまり処理しているデータのサイズを見逃しています。処理する必要があるデータの量に応じて、データ構造とアルゴリズムを選択します。自分の選択を正当化できることが重要です。効率の低い一般的なアルゴリズムを使用することが常に悪いわけではありません。選択をバックアップできること (例: データ サイズが常に 10 未満であるためバブル ソートを選択すること) は、a) より優れた分野の指揮と b) プラグマティズムを示しています。どちらも不足しています。

于 2009-03-22T04:36:47.877 に答える
1

宿題以外では、これにはリレーショナル データベースを使用します。しかし、それはおそらく役に立たないでしょう…</p>

他の人がすでに指摘しているように、最初に把握する必要があるのは、処理しているデータの量です。O( n ) ブルートフォース検索は、 nが小さい限り十分高速です。些細な量のデータはこれを些細な問題にするので (配列に入れて、力ずくで検索するだけです)、データ量が大きいと仮定します。

都市の保存

まず、検索要件には、複数の方法で並べ替えられたデータが必要なようです。

  1. いくつかの都市の一意の識別子 (名前?)
  2. 来場者数

これは実際に満足するのはそれほど難しいことではありません。(1)が一番簡単です。都市を配列に格納します。配列インデックスは一意の識別子になります (仮定: 都市を削除しないか、都市を削除する場合は、その配列スポットを未使用のままにして、メモリを浪費します。追加は問題ありません)。

ここで、訪問数が最も多いものと最も少ないものを見つけられるようにする必要もあります。変更 (都市の追加、訪問者数の変更など) が発生し、リレーショナル データベースから借用することを想定して、バランス ツリーの形式を使用してインデックスを作成することをお勧めします。データベースは一般的に B-Tree を使用しますが、別のものがうまくいくかもしれません: check木に関するウィキペディアの記事。各ツリー ノードには、都市データのポインター (または配列インデックス) を保持するだけです。別のコピーを作成する理由はありません。

1 つの単純な理由から、ハッシュよりもツリーをお勧めします。上位または下位の N 個のアイテムを見つけるために、非常に簡単に事前注文または逆注文トラバーサルを実行できます。ハッシュではそれができません。

もちろん、変更が行われない可能性がある場合は、別の配列を使用してください (アイテムへのポインターの、繰り返しますが、それらを複製しないでください)。

プロファイルへの都市のリンク

これを行う方法は、データをクエリする方法と、データの形式によって異なります。最も一般的なのは、各プロファイルを複数の都市に関連付けることができ、各都市を複数のプロファイルに関連付けることができるということです。さらに、どちらの方向からでも効率的にクエリを実行できるようにしたいと考えています。そして「ボブはどの都市を訪れますか?」。

再び恥知らずにデータベースから持ち上げて、別のデータ構造を作成します。これは、次の行に沿ったかなり単純なものです。

struct profile_city {
    /* btree pointers here */
    size_t profile_idx; /* or use a pointer */
    size_t city_idx;    /* for both indices */
};

したがって、ボブ (プロファイル 4) がフェニックス (都市 2) を訪れた profile_idx = 4としcity_idx = 2ます。ボブがラスベガス (都市 1) も訪れたと言うには、もう 1 つ追加するので、ボブには 2 つあることになります。

ここで、選択肢があります。これらをツリーまたはハッシュに格納できます。個人的には、そのコードは既に書かれているので、ツリーを使用します。ただし、ルックアップの場合、ハッシュはO(log n ) ではなく O( n )になります。

また、都市の訪問回数で行ったのと同じように、インデックスを作成して city_idx、その側からもルックアップを実行できるようにします。

結論

これで、最も訪問された 5 つの都市を検索し (都市訪問カウント インデックスを順番に走査して)、city_idxインデックス内の各都市を検索して profile_idx. ユニークなアイテムだけを手に入れれば、答えが見つかります。

ああ、ここで何かがおかしいようです: これは、インストラクターが数時間で書きたいと思う非常に多くのコードのようです!

于 2009-03-22T08:44:27.657 に答える
1

複数のキーを検索できるようにするには、便利な形式でデータを保存し、キーの高速検索インデックスを提供します。

これは、データを作成順に配列 (またはリンク リストなど) に保持し、(key, data*)すべての興味深いキー (SSN 、 名前、 ...）。

もっと時間があれば、マップごとに異なるものを持たないようにする方法を考え出すこともできます...struct

この解決策はおそらく両方の問題に当てはまると思います。

幸運を。

明確にするために：

まず、学生レコードの単純な配列があります

typedef
struct student_s {
   char ssn[10]; // nul terminated so we can use str* functions 
   char name[100];
   float GPA;
   ...
} student;
student slist[MAX_STUDENTS];

これはあなたが行くにつれて満たされます。順序がないため、任意のキーでの検索は線形時間操作です。1,000 エントリでは問題ありませんが、10,000 エントリでは問題になる可能性があり、100 万エントリでは問題になることは間違いありません。dirkgently のコメントを参照してください。

高速に検索できるようにしたい場合は、構造の別のレイヤーが必要です。次のように、キーとメインのデータ構造の間にマップを作成します。

typedef
struct str_map {
   char* key;
   student *data;
} smap;
smap skey[MAX_STUDENTS]

キーで並べ替えられたskey を維持して、高速な検索を実行できるようにします。(配列のみをソートしておくのが面倒なので、おそらくツリーまたはハッシュマップを優先します。)

単一のフィールドでのみ高速な検索が必要な場合は、この複雑さは必要ありません (もちろん回避する必要があります)。

于 2009-03-22T04:18:01.777 に答える