Linux上での「クイックセレクト」（またはそれに似た）実装ですか？

Question

問題：特定のログの最終日に最も頻繁に繰り返される「パターン」が何であるかをよく知る必要があります。

GET /app1/public/pkg_e/v3/555413242345562/account/stats 401 954 5 
GET /app1/public/pkg_e/v3/555412562561928/account/stats 200 954 97 
GET /app1/secure/pkg_e/v3/555416251626403/ex/items/ 200 517 18 
GET /app1/secure/pkg_e/v3/555412564516032/ex/cycle/items 200 32839 50 
DELETE /app1/internal/pkg_e/v3/accounts/555411543532089/devices/bbbbbbbb-cccc-2000-dddd-43a8eabcdaa0 404 - 1 
GET /app1/secure/pkg_e/v3/555412465246556/sessions 200 947 40 
GET /app1/public/pkg_e/v3/555416264256223/account/stats 401 954 4 
GET /app2/provisioning/v3/555412562561928/devices 200 1643 65 
... 

私は（メソッドおよびリターンコードと一緒に）最も頻繁に使用するURLを見つけるしたい場合は - 私がやります：ここでのTomcatログの小さなサブセットのためのような

[root@srv112:~]$ N=6;cat test|awk '{print $1" "$2" ("$3")"}'\ 
|sed 's/[0-9a-f-]\+ (/%GUID% (/;s/\/[0-9]\{4,\}\//\/%USERNAME%\//'\ 
|sort|uniq -c|sort -rn|head -$N 
     4 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (401) 
     2 GET /app1/secure/pkg_e/v3/%USERNAME%/devices (200) 
     2 GET /app1/public/pkg_e/v3/%USERNAME%/account/stats (200) 
     2 DELETE /app1/internal/pkg_e/v3/accounts/%USERNAME%/devices/%GUID% (404) 
     1 POST /app2/servlet/handler (200) 
     1 POST /app1/servlet/handler (200) 

私は、同じファイルから最も頻繁にユーザ名を見つけるしたい場合は - 私がやる：

[root@srv112:~]$ N=4;cat test|grep -Po '(?<=\/)[0-9]{4,}(?=\/)'\ 
|sort|uniq -c|sort -rn|head -$N 
     9 555412562561928 
     2 555411543532089 
     1 555417257243373 
     1 555416264256223 

以上は小さなデータ・セットにはかなりうまく動作しますが、入力の大きなセットのために - パフォーマンス（複雑さ）はsort|uniq -c|sort -rn|head -$Nは耐え難いです解決するために

（〜100台のサーバー、サーバーあたり〜250個のログファイル、ログファイルあたり〜1mlnラインの話）ATTEMPT：|sort|uniq -c部分は簡単にそれを回す、AWK 1-ライナーで置き換えることができます。

|awk '{S[$0]+=1}END{for(i in S)print S[i]"\t"i}'|sort -rn|head -$N 

が、私は|sort -rn|head -$N一部を最適化するために（hereを議論）「クイック選択アルゴリズム」のシンプル/標準とメモリ・効率的な実装を見つけることができませんでした。 （所与のN = 3）に

3 tasty oranges 
225 magic balls 
17 happy dolls 
15 misty clouds 
93 juicy melons 
55 rusty ideas 
... 

： はオンに、GNUバイナリ、RPMの、AWK 1ライナーまたはI /データセンターにまたがって運ぶことができるいくつかの簡単にコンパイルANSI Cコードを探していた

（ - コアのjava内 .quickselect(...)の欠如に驚いた方法で） -

225 magic balls 
93 juicy melons 
55 rusty ideas 

私はおそらくサンプルJavaコードと上記の標準入力フォーマットのポートそれをつかむことができますが、どこでもJavaのランタイムを展開する必要が魅力されていません。 私は多分サンプル（配列ベースの）Cスニペットをつかんで、上記の標準入力フォーマットに適合させてからしばらくの間、テスト・アンド・フィックス・リーク&などを漏らすことができます。あるいはawkの中から最初から実装することさえできます。 BUT（！） - この単純なニーズには、定期的に1％以上の人が直面している可能性があります。標準的な（事前テスト済みの）実装があったはずです。 希望は...多分私はそれをルックアップするために間違ったキーワードを使用しています...

その他の障害物：はまた、大規模なデータセットのためにそれを回避するために問題のカップルに直面していました：

• ログファイルは〜100台のNFSマウントされたボリュームに置かれているので、 は並列化して作業を小さなチャンクに分割する意味があります
• 上記のawk '{S[$0]+=1}...にはメモリが必要です - 私は1635GB 48GBの空きRAMがあり、 スワップのnty ...多分私が見落として、いくつかのLinuxの制限）

は私の現在のソリューションは、（）まだ進行中で、信頼性がないと、最適ではないように見えます：自分の小さなツールを書いた場合、私はわからない

find /logs/mount/srv*/tomcat/2013-09-24/ -type f -name "*_22:*"|\ 
# TODO: reorder 'find' output to round-robin through srv1 srv2 ... 
#  to help 'parallel' work with multiple servers at once 
parallel -P20 $"zgrep -Po '[my pattern-grep regexp]' {}\ 
|awk '{S[\$0]+=1} 
END{for(i in S)if(S[i]>4)print \"count: \"S[i]\"\\n\"i}'" 
# I throw away patterns met less than 5 times per log file 
# in hope those won't pop on top of result list anyway - bogus 
# but helps to address 16GB-mem problem for 'awk' below 
awk '{if("count:"==$1){C=$2}else{S[$0]+=C}} 
END{for(i in S)if(S[i]>99)print S[i]"\t"i}'|\ 
# I also skip all patterns which are met less than 100 times 
# the hope that these won't be on top of the list is quite reliable 
sort -rn|head -$N 
# above line is the inefficient one I strive to address 

Answer 1

あなたには受け入れられますが、|sort|uniq -c|sort -rn|head -$N -partを|sort|quickselect $Nに置き換える小さなツールを簡単に書くことができます。このツールの利点は、最初のsortの出力を1行ずつ、メモリに多くのデータを保存しないで1行だけ読み込むことです。実際には、現在の行を保持するためのメモリーと先頭の$N行しか印刷されません。

ここでソースquickselect.cppだ：私ははい、私はあなたがすぐに解決策を求めていた実現します

g++ -O3 quickselect.cpp -o quickselect 

、しかし：

#include <iostream> 
#include <string> 
#include <map> 
#include <cstdlib> 
#include <cassert> 

typedef std::multimap< std::size_t, std::string, std::greater<std::size_t> > winner_t; 
winner_t winner; 
std::size_t max; 

void insert(int count, const std::string& line) 
{ 
    winner.insert(winner_t::value_type(count, line)); 
    if(winner.size() > max) 
     winner.erase(--winner.end()); 
} 

int main(int argc, char** argv) 
{ 
    assert(argc == 2); 
    max = std::atol(argv[1]); 
    assert(max > 0); 
    std::string current, last; 
    std::size_t count = 0; 
    while(std::getline(std::cin, current)) { 
     if(current != last) { 
      insert(count, last); 
      count = 1; 
      last = current; 
     } 
     else ++count; 
    } 
    if(count) insert(count, current); 
    for(winner_t::iterator it = winner.begin(); it != winner.end(); ++it) 
     std::cout << it->first << " " << it->second << std::endl; 
} 

してコンパイルします同等に効率的なものは何も知らない。そして上記はとてもシンプルなので、エラーのマージンはほとんどありません（単一の数値コマンドラインパラメータを混乱させないでください）。