0

この問題をコーディングするためのソートアルゴリズムを選択するには、いくつかのアドバイスが必要です。

フェーズ1では、プログラムはデータベースからclientIDとそれぞれのハッシュ（おそらく構造体を使用します）をフェッチします。0または数千のレコードが存在する可能性があります。

フェーズ2では、プログラムはXMLファイルから読み取られたレコードを使用してこのセットを完成させます。私はすでにストリームパーサーを構築しました。XMLファイルには、請求書データの前にすべてのクライアント情報が順番に含まれています。

フェーズ2が完了すると、プログラムは請求書データを読み取ります。請求書ごとに1つのclientIDがあり、これはクライアントのセットからチェックする必要があります。請求書の数は数百万のレコードになる可能性があります。

私が最初に思ったこと。クライアントレコードがいくつあるかわからないので、リンクリストを使用して動的にメモリを追加する必要があります。フェーズ2の終わりに、clientID順に並べられたデータの配列を作成できるので、請求書ごとに1つずつ、さらに検索を実行できます。おそらく、バイナリ検索を使用してすばやく取得できます。

この状況に対処するためにあなたが私に何をアドバイスするのか知りたいのですが。どのソートアルゴリズムを使用する必要がありますか？（私はCでコーディングします）。

4

2 に答える 2

3

間違いなく、最良のアルゴリズムは次の基準を満たすものです。

  • コードを書く必要はありません
  • サードパーティの依存関係は発生しません
  • あなたの目的のために十分に速い

何千ものレコードが基本的にないことを考えるとqsort、並べ替えとbsearch検索に使用することをお勧めします。これらは両方ともC標準ライブラリにあります。

注意すべき問題：

  • qsortリンクリストでは使用できません。動的に成長する配列にデータを保存することを強くお勧めします。作成の償却コストは同じであり、他の利点もあります（たとえば、メモリオーバーヘッドの削減、参照の局所性の向上）。

  • 注意深くプロファイリングした後bsearch、それが十分に高速ではないことがわかった場合、これはO（log N）ではなくO（1）であるため、ハッシュテーブルベースのルックアップに移行することをお勧めします。ただし、自分で作成しようとしないでください。これには既存のライブラリを使用します。（提案については、ここで他の回答を参照してください。）

于 2013-01-15T20:30:51.873 に答える
1

glibライブラリには、ハッシュテーブルの実装が含まれています。ソートされていない間、ハッシュテーブルを使用すると、O（1）または定数時間のルックアップを実行できます。これは、ルックアップする請求書が数百万ある場合に役立ちます。

バイナリ検索Clientを実行するための構造体のソートされた配列など、他の可能性もあります。構造体に。というメンバーが含まれているとします。クライアントIDが一意で単調に増加し（必ずしも配列インデックスと同等ではありませんが、増加します）、レコードがある場合は、ピボットインデックスに移動して、関心のあるIDかどうかを確認する必要があります。Clientunsigned intclientIDnfloor(n/2)i次に調べる配列の半分を決定するために、ピボットインデックスで構造体参照によって参照されるIDよりも大きい、等しい、または小さい。新しいピボットインデックスは、そのサブ配列の下限と上限の中間点になります。これは、目的の要素が見つかるまで再帰的に検索します。

ソートされた配列を介したバイナリ検索のルックアップパフォーマンスはO（log n）—ハッシュテーブルよりも遅く、配列をソートするためのゼロ以外のコストがありますが、全体的なメモリオーバーヘッドは小さくなります。そのためのメモリがある場合は、ハッシュテーブルの方が高速である可能性が高いため、非常に多数のルックアップに適した構造であることがよくあります。

于 2013-01-15T20:34:21.487 に答える