-1

次のように機能するアルゴリズムを実装するとします。

次の形式の値を含むファイルから読み込みます。

Mark Buy  20 1 100
Bob  Sell 20 2 90

入力の形式は次のとおりです。

<name><buy or sell><quantity><time><company><buy maximum or sell minimum>

買い手と売り手を一致させる最速の方法は何ですか (一部の会社では、その会社の最高の購入者がその会社の最低の販売者よりも優れている場合にのみ、買い手と売り手が一致します)。一番上にある買いまたは売りが、使用する価格を決定するものになります。

したがって、与えられた例では、「マークは時間 1 に、時間 2 にボブから 100 ドルで 20 の Google を購入した」となります。

このアルゴリズムを最適化して速度を上げるにはどうすればよいでしょうか? 最初にファイル全体を読み取ることが最適な解決策でしょうか?

4

1 に答える 1

1

必要なのは、コモディティごとに 2 つの優先キューです。1 つはアクティブな買い入札用 (最大価格で優先)、もう 1 つはアクティブな売り入札 (最小価格で優先) に加えて、入札作成/有効期限イベント (優先価格で優先) 用の全体的なキューです。時間）。(因果関係/オンライン シーケンスではなく、前述のように入札がバッチ ファイルにある場合は、作成/有効期限イベントを並べ替えるだけで済みますが、購入キューと販売キューが必要です)。

プライオリティ キューを使用することが重要です。その後はすべて配管です。

foreach bid creation/expiry event, in chronological order:
  if the event is an expiry:
    delete the bid from the appropriate queue
  else, the event is a creation:
    add the bid to the appropriate queue
    repeat until no further transaction can be performed:
      find max-active-buy and min-active-sell bids for the given commodity
      if they match:
        execute (and record) the transaction
        update partially fulfilled bids, and remove completely fulfilled ones

バッチ操作として実行する場合は、個々の商品を整理して、それぞれを個別に実行することで、物事を少し単純化できます。ただし、市場がなんらかの方法で相互作用する場合 (十分な口座残高の確認など)、これは機能しません。

プライオリティ キュー操作は、アイテム数で O(log N) の漸近的なパフォーマンスを持つことができます。この漸近的な限界を達成する、高速で実用的なプライオリティ キュー データ構造が多数あります。

ファイル全体をバッチとして評価しているので、償却されたパフォーマンス保証で優先度キューを調べたいと思うかもしれませんが、コードをリアルタイム設定で使用することが予想される場合は、厳密な per の優先度キューに固執する必要があります。 -クエリ保証。

于 2013-03-29T21:22:30.673 に答える