3

次のシナリオに最適なデータ構造は次のとおりです。株価情報 (スクリプト コード、価格) を照合する必要があります。潜在的に、1 時間以内に数百万の見積もりが表示される可能性があります。頻繁に挿入されるため、コンパレータを含む配列リストは惨事になります。TreeSet はオプションのようですが、誰かがより良い構造を提案できます。(これには、既存の Java コレクション クラスを使用するのではなく、一般的なデータ構造を構築することも含まれます。)

4

2 に答える 2

0

以外には何も提案できませんがTreeSet、最適化の可能性を指摘することはできます。これまでのところ、上位 N 番目の見積もりよりも少ない見積もりを追加する必要はまったくないようです。これは、ツリーのサイズが無制限ではなく、最大で N であることを意味します。

例えば：

final int n = ...;
final NavigableSet<Quote> topNQuotes = new TreeSet<Quote>();

void addQuote(Quote quote) {
    //if the Set of quotes has reached N,
    if (topNQuotes.size() == n) {
        //get the greatest Quote that is less than this one
        Quote lowerQuote = topNQuotes.lower(quote);
        //if no such Quote was found in the Set, quit without adding
        if (lowerQuote == null) {
            return;
        }
        //otherwise remove and discard the lowest Quote from the Set
        topNQuotes.pollFirst();
    }
    //add the new Quote to the Set
    topNQuotes.add(quote);
}

この例はスレッドセーフではないことに注意してください。

于 2012-10-18T05:59:16.920 に答える
0

リアルタイムの価格フィードを書いた個人的な経験から、速度が問題になる場合は、余分なメモリを占有する価値があります。可能であれば、価格または注文 ID で価格フィードをハッシュすることを正直に提案します。

また、私の理解が正しければ、シンボルの上位 N の価格を表示したいと考えています。これらの N の価格に対して何百万もの注文があるかもしれませんが、それぞれを N の価格レベルのいずれかに照合できます。したがって、価格レベル オブジェクトを作成すると、データ構造はこれらの価格レベル オブジェクトへのポインターをシャッフルするだけで済みます。この場合、N が大きすぎない限り (通常、特定のシンボルの価格レベルはそれほど多くないため)、配列はローカリティで十分に高速になる可能性があります。

また、ハッシュしたくない場合は、価格レベルの本を表示するための適切な解決策として、循環配列を使用すると思います。そうすれば、先頭 (最低価格) と最後 (最高値) での挿入は、どちらも平均して一定の時間になるはずです。シャドウ配列を使用して、O(1) 一定時間の挿入を保証することもできます。

于 2012-10-18T06:55:06.503 に答える