java - 整数のストリームの最大値と最小値

Question

整数のストリームが与えられた場合（私はそれらを1回しか通過できません）、最大値と最小値を見つけるための最良の解決策は何ですか？各数値を処理するのに十分な時間があれば、最小値と最大値を別々の変数に保持するのが最も簡単な解決策だと思いますが、すべてを処理できない場合の最善のアプローチは何ですか？単に最大変数と最小変数を保持し、たとえば1秒おきの数値をスキップするよりも優れた解決策はありますか？

Answer 1

真の最大値と最小値が必要な場合は、変数を使用してそれらを追跡するだけです。

入力データによっては、確率的な最小/最大が「十分に正確」である場合があります。したがって、50％の確率ですべての数値を見るだけの場合、正確な最小値または最大値を持っているのはおそらく50％だけです。しかし、おそらくすでに75％の確率で、少なくとも2番目に大きい/小さいなどがあります。ただし、バイアスのないサンプリングを行うために乱数を計算することは、すべての数値を最小/最大で調べるよりもすでにコストがかかります。毎秒スキップするのは危険です。データに偶数/奇数のパターンがあり、ひどくねじ込まれている可能性があります。