ストリーム（または要素の長いリスト、数千または数百万になる可能性があります）を持っています。グループの平均。効率的な方法で最初のN個の結果をグループ化、並べ替え、返す
{groupId: 1, value: 10}, {groupId: 2, value: 4}, {groupId: 1: value: 2}
とフォームグループ：
{groupId: 1, average: 6}, {groupId: 2: average}
明らかにナイーブな溶液は、グループを反復平均でソートグループ及び第24グループを返すことである形態である項目がそう。何百万ものアイテムを扱うことができる高性能ソリューションのアイディアですか？
リスト全体をエスケープして、特定のグループのすべてのメンバーを取得することはできません。あなたはその平均値で利用できる各グループを持っていたら、次の操作を実行できます。
をヒープと挿入します。ヒープソートの最後のステップを適用し、取得したコンテナーを逆にすることで、ヒープを最大ヒープにすることができます。
全体的な複雑：（Kは、総グループ数とNは、上記定義される）
O（N +（KN）の.ln（N）+ N.ln （N） = O（N + K.ln（N））
ありがとうございました。これは、Solrがグループ化された結果を並べ替えるためにやっていることですが、平均の代わりにmax関数を使用しています。これらの並べ替え（最初のN要素の並べ替え）がアルゴリズムフィールドに名前を持っているかどうか知っていますか？ – agori
@agori私が知っているわけではありませんが、この問題はよく知られています。 IIRCの「コーディング・インタビューのクラッキング」で見つけることができる優れたソリューションもあります。 – Rerito
私はGuavaによって実装された優先度キューを使用しました： 'MinMaxPriorityQueue.orderedBy（new MyComparator（））.maximumSize（groupOffset + this.topNGroups）.create（）;' – agori
グループごとに2つの値（そのグループとカウンタの合計値）を保持してください。最後に、このグループの平均を得るためにカウンターで合計を割ります。
グループが限られているため情報を保持できません。いずれかのグループがある時点でリーダーになる可能性があるからです。
グループを平均でソートする場合は、リスト全体を反復処理する方法はありません。しかし、 "何百万"でも、これは大きな問題ではありません。 –
Hmm。あなたはそれがどのような種類のデータであるかは分かりませんでした。おそらくApache SparkやApache Stormのようなマイクロバッチ処理アプリを使用することができます。 –
@CaptainFogettiこのデータはLuceneインデックスに由来しています。私はユースケースでLuceneコレクタを実装しようとしています。 – agori