ソートされたログで重要なエントリを見つけよう

Question

私は数千の整数からなるログファイルをそれぞれ新しい行に分けています。私はこのような整数の配列にこれを解析し、ソートしました。今、私の問題は、このログから "重要な"整数を見つけることになります。これらは、ユーザが設定可能な時間の一部を表示するものです。

たとえば、ログを指定すると、ユーザーは、一定の縮尺で表示されたエントリのみを表示するようにフィルタリングできます。

現在、アレイ全体をスキャンして、各エントリが表示される回数をカウントしています。確かに良い方法がありますか？

Answer 1

まず、以下のことは理論的な解決策であり、@MBoの提案を使用する必要があります。

ソートされた配列のすべての要素m = n/lを取ります。長さがmの同一の配列がi*mと(i+1)*mの間に適合できないので、これらの要素だけが重要となり得る。

各要素xについて、配列の下限と上限をバイナリ検索で検索します。インデックスを削除すると、カウントを知ることができ、xを重要でないとみなしたり、破棄したりすることができます。

合計複雑度はO((n/m) * log n) = O(l * log n)となります。 mの場合、それはO(n)より（漸近的に）良好であり得る。実際の改善を取得するには、しかし、あなたは非常に特殊な状況が必要になります。

• 配列は、あなたに与えられているあなたはiにアクセスすることができます（そうでない場合は、単にカウント並べ替えを使用していて、すぐに答えを得る）

• を事前ソート配列全体の配列を読み取ることなくO(1)に配列の012番目の要素。それ以外の場合は、ハッシュテーブルを使用してカウントソートを再度使用します。

あなたは（それがあまりにも可変幅のために可能であるが、いくつかの余分な努力が必要です）ソートされた固定幅の整数"data.bin"からなるファイルがあるとします。あなたのファイルが（MBの数百）非常に大きい場合を除き、あなたは、最新のハードウェア上のナイーブO(n)に比べて顕著な改善が得られないだろう、推測として

def find_all_important(l, n): 
    m = n/l 
    for i = m to l step m: 
    x = read_integer_at_offset("data.bin", i) 
    lower_bound = find_lower_bound(x, 0, i) 
    upper_bound = find_upper_bound(x, i, n) 
    if upper_bound - lower_bound >= m: 
     report(x) 

def find_lower_bound(x, begin, end): 
    if end - begin == 0: 
    return begin 
    mid = (end + begin)/2 
    x = read_integer_at_offset("data.bin", mid) 
    if mid < x: 
    return find_lower_bound(x, mid + 1, end) 
    else: 
    return find_lower_bound(x, begin, mid) 

：次に擬似コードでは、アルゴリズムは、そうのようなものである可能性があります。もちろん、データがRAMに収まらない場合は実行可能です。しかし、いつものように最適化はテストの価値があるかもしれません。

Answer 2

ソートにはおそらくO（NlogN）時間がかかります。同じデータセットに対して（n/I）回のクエリを何度も実行する必要がありますか？

はいた場合、ソートされた配列の中を歩く(Value;Count)ペアを作り、Countフィールドによってそれらを並べ替えます。今度はバイナリ検索で多数のペアを簡単に分離することができます