4

データを照合するための最も効率的なデータ構造は何ですか？たとえば、次のシナリオが表示されたとします。

<time available> <buy or sell> <company name> <buy or sell price> <amount to buy or sell>

ファイルに次のものが含まれるようにするため：

0 sell yahoo $100 #1
2 sell yahoo $14  #1
2 sell yahoo $28  #1
.. 95 other yahoo sells <$125 and amount #1
3 sell yahoo $17  #1
5 sell yahoo $33  #1
9 buy yahoo  $125 #100

この最後の購入をO（n）時間での前の100の販売と一致させることは可能ですか？ここで、購入を購入したい会社（または同点の場合は最初に来る）？

単純な解決策はリストを並べ替えて順番に並べることですが、これにはO（n）時間よりも時間がかかります。この問題とそれに類似した問題を処理するための最も効率的なデータ構造は何ですか？

4

2 に答える 2

2

価格でランク付けされた、会社名から売り注文のヒープまでのハッシュマップを使用してみてください。売り注文の挿入は現在O(log n)であり、買いが売り注文を使い果たしていない場合、または使い切っているO(log n)場合（問題ステートメントで指定されていない場合） 、買い注文は一定になります。

于 2013-03-24T22:17:07.380 に答える
0

売買は同じ組織を扱うので、すべてのyahooレコードがキーとして「yahoo」を使用してマップにハッシュされるリストに保持されるように、すべての購入（または）販売レコードをマップに保存することをお勧めします。これにより、検索スペースが最小限に抑えられます。タイムスタンプ、価格、数量で並べ替えると、挿入時にこの構造を実装することで、最適なコストで目的の機能を実装できます。その後、検索スペースが最小限であったため、この後のクエリの所要時間は短くなります。

于 2013-03-25T12:49:07.013 に答える