パスワードを忘れた? アカウント作成
27413 journal

okkyの日記: これがゆとりか… 12

日記 by okky

いや、私は 1966年の早生まれなので、ここ60年ぐらいで一番きつい教育を受けた世代。ほぼ全ての世代に対して「ゆとり」と言える立場ではあるのですが。
# 教育を「うけた」からといってそれが「身についている」
# と考えてはいけない、好例ですな。

.

それはともかく。
どうやら Merge Sort を知らない人がいるらしい。

http://srad.jp/~messier42/journal/442400

それは merge sort というやり方そのものだよ。つーか merge sort 知ってるなら最初に思いつくのがそれだ。

そして普通は

1) uniq <original file> | split -l 10000 - /tmp/aa
2) for i in /tmp/aa*; sort $i | uniq > $i.2; done
3) sort -m /tmp/aa*.2 | uniq > <result>

のように各ステップに uniq を入れて、n がなるべく小さくなるように努力するものだ。uniq は O(n)、 sort はどうやっても O( n * log n)のアルゴリズムだからね。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • ううむ,マージソートを知ってるか否かってあまりゆとりとは関係ないと思う.
    モノホンのゆとり(世代関係なくそういう人がいるという意味で)は,
    「できません」って言って終わりだから.

    自分は70年代前半の生まれでそれなりに受験戦争を経験してきた世代だけど,
    自分が詳しい分野なんて本当に限られてるし.たまたま「マージソート」という
    手法について今まで必要がなかったから名前知りませんでした,ってだけでは?
    --
    屍体メモ [windy.cx]
  • merge sort (スコア:2, すばらしい洞察)

    by messier42 (36151) on 2008年06月11日 21時26分 (#1361639) ホームページ 日記
    > どうやら Merge Sort を知らない人がいるらしい。
    教祖様は相変わらず突っ込みが鋭い。それはさておきsortコマンド
    自体も/tmpに作られる作業ファイルから類推してアルゴリズムは
    マージソートもしくは類似アルゴリズムと思いますので、/tmpに
    十分余裕があるならそのまま処理しても大した時間差はないと思い
    ます。
    • by okky (2487) on 2008年06月11日 23時23分 (#1361711) ホームページ 日記
      uniq で数を削りながら…というのは十分意義があると思いますよ。1Gbyte前後ごとに分割するなら特に…。

      64bit CPUの場合、オリジナルファイルを mmap しながらソートできるので、これまた性能に差が出るでしょう。

      最後に。split で分割したファイルを置く場所があるのに、-T を使う場所はなかったんでしょうか??
      --
      fjの教祖様
      親コメント
    • by pharmer (32222) on 2008年06月11日 23時26分 (#1361715)
      /tmp に余裕が無い事だけが問題なら
      TMPDIRを設定すれば問題解決するのでは?
      親コメント
      • > 環境変数 $TMPDIR
        > -Tオプション
        確かにそうですね(w

        150GBのsortに、実は3日もかかったのですが、次やるときは
        TMPDIRで試してみます。
        親コメント
        • 次やるときはTMPDIRで試してみます。

          もう一度やるというなら、せっかくだからもう一声。さすがに3日もかかるのは無駄すぎる。

          1) 各行ごとに checksum でもハッシュでもいいから、hash値をとる。
                128bit のような巨大なものにする必要は無い。8bitとかでも十分だが、
                各行がほぼ均等に分散するような hash 関数を選ぶ事。もちろん、
                ファイルシステムとファイルハンドラーが悲鳴を上げないなら、
                hash 値のサイズは大きくてもいいが…まぁ、8bitぐらいでやめとけ。
                単純に全バイトを unsigned char 型に足し合わせていって、最後に
                %256 の結果を見る、と言うのでも十分。

          2) 1 で求めた hash値のファイル名に当該行を append する。
              つまり、ある行のhash値が 0x35 なら、/work/35 というファイルに、その行を
              append する。いや、ファイル名は "35"でなくてもいいが。
              判るでしょうが、この段階で「重複する行」は全て同じファイルに行きます。
              違うファイルが「互いに重複する行」を持つ事はありえません。
              逆に1つのファイルの中に複数種類の行が入っている可能性はありえます。

          3) 全部の行を処理し終わったら、/work/00 - /work/ff というファイルができている。
                それぞれを別々に uniq | sort | uniq をかける。そう。先に uniq を一度かけてから sort して、もう一度 uniq を掛け直す。 2のステップで「濃縮」されているので、重複率は高いのだ。平均ファイル長は1Gbyteを下回るので、おそらく /tmp だろうが on memory だろうが、素直に終わるだろう。

          4) 必要なら、それらのファイルを再度結合し直せばよい。
                もし、最終出力がソートしてある必要がないなら cat で十分。
                ソートしてある必要があっても、sort -m でOK。
                そもそもくっつける必要がないなら、ここの時間は0。

          .

          ようするに。

          世の中には sort よりも軽い「似た行を発見する方法」ならばあるのだから、先にそれを実行しろ、ってことです。データが先に分割できると、より高速なメディア内部だけで実行が終わります(on HDD より on Memory, on Memory より on Cache)。
          オーダーが大きくなって厄介な処理は、やるとしても分割した後でやれ、と。log n 分ぐらいはメディアの高速化が吸収してくれるから。
          --
          fjの教祖様
          親コメント
          • なかなか良さそうなアイデアですね。プログラムも簡単に作れそうですし、試してみます。

            ただ、ファイルシステムのフラグメンテーションがすごい事になりそうですね(汗
            親コメント
            • テンポラリファイルがフラグメンテーション起こしてもたかが知れてるし(全部消せばきれいになくなる)。Fedora9 マシンを立ててその上でやってみる、という手もある。

              .

              それはともかく。「なかなかよさそう」としか考えないと言うことは、試算をしなかったな?!

              Sort は merge sort でも O( n* log n )は確定だ。O(n)で最初に 256 個のファイルに分割すると、sort しなくてはいけない行数が 1/256 に減るので、sort の計算オーダーは

              O( (1/256) * (1/8) )

              になる。ファイルが 256個あるのでこれを 256倍しても O(1/8) だ。

              実際には均等分散は難しいとしても、 1/4 ぐらいにはなろう。開発に 1日かけてももう1日あれば結果が出る。

              .

              で、ここまでヒントを出せば判っていると思っていたが、本当にわかってなさそうなので。

              重複している行だけを切り出すなら、Hash 関数のビット数をもう少し増やして 10bit ぐらいにする。ファイルを開け閉めする必要が出るので、最初のファイル分割の部分に手間がかかるが、その代わりファイル一つあたりのサイズは 512Mbyte を下回る(平均 150Mbyte)はずだ。

              512Mbyteのファイルに、すでに開発してあると言う perl スクリプトを流せば、パンクすることもなく、O(n)で全部終わる、というのは考えたかい?

              しかも、この処理の場合、150Gbyte を2回なめれば終わる。処理速度が 10Mbyte /sec だとしても、0.4日で終わる計算だ。開発に1日かけるなら、3時間以上かかる処理になるとは思えない。
              --
              fjの教祖様
              親コメント
  • それよりも150GBのファイルってのが気になる。内容は何だろう?
    何かのログだったとしたら、そんなに肥大するまで放置していた管理者失格だな。
    最近の連中はリソースが有限だということを知らないから困る。
    はっきり言っちゃえばバカ。
    --
    morikun
    • たぶん、システムログではない。

      システムログならば日付や時刻が入っているから uniq できないし、そもそも「repeated x times」という記述があるので、この方法では回数の感情にならない。

      じゃぁ何さって、それは知りませんけどね。

      .
      昔 1/20 に gzip 圧縮された 4Gbyte のテキストを追い回したことならあります。
      1995年ぐらいかしら。WSのHDDをどうひねっても80Gbyteなんてなかった時代。

      PPC603e が8台ぐらい並列でつながったシステムがどう動くのか、エミュレーションをしたときのログですが。
      # Bus slashing が起こって、あらゆる処理がふんずまる…というのがよく判る、
      # すごいログでした。1行 1pixel で600dpi で印刷すると、3kmぐらいの長さになる計算。

      まぁ、たぶんそういう類の研究・実験ログではないでしょうか。
      --
      fjの教祖様
      親コメント
    • > それよりも150GBのファイルってのが気になる。内容は何だろう?
      研究データです。一度しか出現しない文字列を排除して、二回以上
      出現する文字列を取り出す必要があったのですが、当初perlの連想配列
      にぶちこんだら当然ながらメモリ不足になり、sort + uniq する事に
      しました。
      親コメント
  • mergesortを知らずに自分で思いついたならむしろ天才かも。
    --
    署名スパムがウザい?アカウント作って非表示に設定すればスッキリさ。
typodupeerror

人生の大半の問題はスルー力で解決する -- スルー力研究専門家

読み込み中...