Big Sky

2012/07/12

プログラミング言語は「e」をタイプする量が多くなる？

今日こんな記事を見た。

Mahdi Yusuf: Most Pressed Keys and Programming Syntaxes

I switch between programming languages quite a bit; I often wondered what happens when having to dea...
http://www.mahdiyusuf.com/post/9947002105/most-pressed-keys-and-programming-syntaxes-2

各プログラミング言語でどのキーを多くタイプするかという物。
Lispや関数言語で () が多いのはいいとして、どの言語もやたら e が多い。気になってつぶやいたら

英語ベースだからじゃ

英単語を書いていると、どうしてもeを打つ機会が多くなるというだけではないでしょうか。

という意見を頂いた。気になったので少し調べる事にした。
vim で普段辞書として使っている gene95 を使った。そのままだと測定材料にならないので

:%s/[^a-zA-Z]/ /g 英文字以外を全て空白に(空白を単語区切りにする)
:%s/\s\+/\r/g 空白を改行に(これにより行が単語単位になる)
:%g/^\s*$/d _ 空行を削除
:%!sort|uniq ソートしてユニーク(感嘆符 a とか多すぎる)

あとはvim scriptでカウント


let text = join(readfile(expand('~/vimfiles/dict/gene_words.txt')), '')

let arr = split(tolower(text), '\zs')

for c in map(range(char2nr('a'), char2nr('z')), 'nr2char(v:val)')

  echo c count(arr, c)

endfor

vim スクリプトにはエディタなのに配列からマッチするアイテムの数を取得する関数があったりいろいろ酷いと思います。
さて実行結果

ソートしてみよう


:%!sort -nr -k 2

おぉぉぉぉ.... やっぱり英単語って e が多いんですね。。。
ひとつ賢くなった。

Posted at by mattn

2012/07/06

Learn Vim Progressively

この文章は、 http://yannesposito.com/Scratch/en/blog/Learn-Vim-Progressively/で掲載されている「Learn Vim Progressively」の翻訳文です。
文内の全てはの筆者による物であり、訳文の内容については私による物となります。意訳が若干入っています。間違い等あればご連絡下さい。

tl;dr: 可能な限り速くvim(人類史上、最良と知られているテキストエディタ)を習得したい。その方法を提案する。生き残るには最小を学ぶ事から始め、その後徐々にトリックを混ぜて行く。

Vim 60億ドルのテキストエディタ

優れいて、強く、そして速い

vimを学ぶ事、それはあなたあなたが学ぶ最後のテキストエディタになるでしょう。私が知る限りより優れたテキストエディタはない。学ぶのは難しいが、使うと素晴らしい。

4つのステップで学ぶ事をお勧めする:

生き残る
心地よさを感じとる
より良さ、強さ、速さを感じとる
vimの強大な力を使う

この道のりの終端で、君はvimスーパースターになっているだろう。

しかし始める前に警告しておく。vimの学習は最初は苦痛となる。時間がかかり、沢山の楽器を演奏する様なものでもある。 3日程度で他のエディタよりもvimが効率的に使える様になるなんて事は期待しないで下さい。現実的に、3日間どころか2週間は確実にかかります。

レベル1 – 生き残る

vimをインストールし
vimを起動する
何もするな！読め

通常のエディタでは、キーボードをタイプするだけで、何かを書いて画面で読む事が出来る。ここではそうじゃない。 VimはNormalモードだ。 Insertモードになろう。 iの文字をタイプしよう。

ちょっとだけいい感じになるはずだ。一般的なメモ帳みたいに文字をタイプ出切る。 Normalモードに戻るにはESCキーをタップするんだ。

InsertモードとNormalモードを切り替える方法を学んだ。そして今、君が生き残る為にあるNormalモードのコマンドリストはこれだ:

i → Insertモード。ESCをタイプしてNormalモードに戻る。

x → カーソル上の文字を消す。

:wq → 保存して終了(:w保存, :q終了)。

dd → 現在の行を削除(そしてコピー)

p → ペースト

忠告:

hjkl (特に必須ではないが推奨する) → 基本的なカーソル移動 (←↓↑→). ヒント: jは下向き矢印の様に見えるよね。

:help <コマンド> → <コマンド>のヘルプを表示する。何もなしで:helpとしても使い始める事が出切る。

たった5つのコマンドだ。はじめはとても少ない。これらのコマンドが自然に使い始められる(どっぷり一日を費やすかもしれない)様になれば、レベル2に行くべきだろう。

でもその前に、ちょっとだけNormalモードについて言っておく。一般的なエディタでは通常、コピーするのにCtrlキーを使う(Ctrl-c)。実際には、Ctrlをタイプした時、それはキーの意味を変えるビットの様な物になる。 vimのNormal modeとは、このCtrlキーがずっと押しっぱなしになっている様な物だ。

注釈に関してお断り:

私はCtrl-λと書く代わりに<C-λ>と書いていく。
:によるコマンドは<enter>で終らなければならない。例えば、:qと書かれている場合それは:q<enter>を意味する。

レベル2 – 心地よさを感じ取る

あなたは生き残るために必要なコマンドを知っている。さらにいくつかのコマンドを学習しよう。これを提案する:

Insertモードのバリエーション:
- a → カーソルの後に挿入する
- o → 現在行の後の新しい行で挿入する
- O → 現在行の前の新しい行で挿入する
- cw → カーソル位置から単語の最後までを書き換える
基本的な移動
- 0 → 行の先頭に移動
- ^ → その行の空白でない最初の文字へ移動
- $ → 行の末尾に移動
- g_ → その行の空白でない最後の文字へ移動
- /pattern → patternを検索
コピー/
- P → 前にペースト。pはカーソル位置の後にペーストと覚えよう。
- yy → 現在の行をコピー。簡単に言えばddPと同じだ。
アンドゥ/リドゥ
- u → アンドゥ
- <C-r> → リドゥ
読み込み/保存/終了/ファイル(バッファ)の変更
- :e <path/to/file> → 開く
- :w → 保存
- :saveas <path/to/file> → <path/to/file>に保存
- ZZ or :wq → 保存して終了
- :q! → 保存せずに終了。また非表示のバッファに変更があっても:qa!で終了
- :bn (関連: :bp) → 次の(関連: 前の)ファイル(バッファ)を表示

これらのコマンドのすべてを統合するために時間がかかる。一度やってみると分かるが、他のエディタで出切る全てを行う事が出切るはずだ。ここまでも若干厄介だろう。しかし次のレベルに従うとその理由が分かる。

レベル3 – より良さ、強さ、速さ

ここまでの到達おめでとう! 面白いことを始められる。レベル3では、古いviと互換性のあるコマンドについて話す。

より良さ

Vimが、ユーザの繰り返し動作についてどう役に立ち得るかを見て行こう:

. → (ドット) は最後のコマンドを繰り返し
N<コマンド> → はN回繰り返す。

幾らか例を示す。ファイルを開き、タイプしよう:

2dd → は2行削除

3p → はそのテキストを3回ペースト

100iです [ESC] → は“ですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですですです “を書く。

. → つい先ほどの最後のコマンド、“です “を100個書くのを再度行う。

3. → 3個“です ”を書く(300じゃないよ。なんて賢い)。

強さ

vimを使って効率的に移動する方法を知ることは非常に重要だ。このセクションを飛ばしてはならない。

NG → N行に移動
gg → 1Gのショートカット。ファイルの先頭に移動
G → 最後の行に移動
単語の移動:
1. w → 次の単語の先頭に移動し
2. e → その単語の終わりに移動する。
デフォルトでは単語とは文字とアンダースコアで構成されている。 WORDは空白文字で区切られた文字のグループと呼ぶことにしよう。 WORDと見なしたい場合は、単に大文字のを使おう。
1. W → 次のWORDの先頭に移動し
2. E → そのWORDの終わりに移動する。

ここで、非常に効率的な移動について説明しよう:

% : (、{、[の対に移動。

* (関連: #) : カーソル位置のある単語で次の(関連: 前の)物へ移動。

私を信じなさい。最後の3つのコマンドはゴールドだ。

速さ

viでの移動の重要性について覚えておきなさい。これには理由がある。ほとんどのコマンドは、以下の一般形式を用いて使う事が出切る。

<開始位置><コマンド><終了位置>

例えば : 0y$ は以下を意味する

0 → この行の先頭に移動
y → そこをヤンク
$ → この行の末尾に向かって

yeの様な物でも行う事ができ、ここから単語の末尾までをヤンクする。またy2/fooは2番目にある“foo”までをヤンクする。

だがy (ヤンク)だけではなく、d (削除)、v (ビジュアル選択)、gU (大文字)、gu (小文字)... 等でも同様だ。

レベル4 – Vimの強大な力

先に述べたコマンドを使用すれば、快適にvimを使えるはずだ。しかしまだ、驚異的な機能ある。これらの機能のいくつかが、私がvimを使い始める理由だった。

現在行での移動: `0` `^` `$` `f` `F` `t` `T` `,` `;`

0 → 行の先頭に移動

^ → 行の最初の文字に移動

$ → 行の最後の文字に移動

fa → その行で次に見つかる文字aまで移動。, (関連: ;)は次に(関連: 前に)見つかるそれまで移動。

t, → ,の前に移動。

3fa → その行で3回目に見つかるaへ。

F と T → f と t に似ているが後方だ。

便利なtip: dt" → "までの全てを削除。

区域選択 `<アクション>a<オブジェクト>` もしくは `<アクション>i<オブジェクト>`

これらのコマンドは、ビジュアルモードでのオペレータの後でしか使う事が出来ない。しかし非常に強力だ。主なパターンは以下の通り。

<アクション>a<オブジェクト> and <アクション>i<オブジェクト>

アクションは、アクションと成り得る如何なる場所にも位置出切る。例えばd (削除), y (ヤンク), v (ビジュアルモード選択)。そしてオブジェクトは: w word、W WORD (拡張されたword)、s 文, p 段落。はたまた"、'、)、}、]といった自然な文字だ。

カーソルが(map (+) ("foo"))の最初のoにあると仮定する。

vi" → fooを選択

va" → "foo"を選択

vi) → "foo"を選択

va) → ("foo")を選択

v2i) → map (+) ("foo")を選択

v2a) → (map (+) ("foo"))を選択

Text objects selection

矩形ブロックを選択: `<C-v>`

矩形ブロックはコード上の多くの行をコメントするのにとても便利だ。通常はこうだ: 0<C-v><C-d>I-- [ESC]

^ → 行の先頭に移動
<C-v> → ブロック選択を開始
<C-d> → 下へ移動(jjj や % …なんかでも移動出来る)
I-- [ESC] → -- を書いてそれらの行をコメントアウト

Rectangular blocks

Windows以外では、クリップボードが空でないなら<C-v>の代わりに<C-q>を使えるかもしれないね。

補完: `<C-n>` と `<C-p>`

Insertモードでは単語の先頭で<C-p>をタイプしてみよう。魔法だ... Completion

マクロ : `qa` 何か実行 `q`、`@a`、`@@`

qaでアクションをaregisterに記録。そして@aはaレジスタに記録されたマクロを、あたかもそれを入力したかの様に再生。 @@は最後に実行したマクロを再生するショートカットだ。

例

数字の1だけ含んだ1行で、これをタイプしよう:

qaYp<C-a>q →

qa 記録を開始

Yp 行を複製

<C-a> 数字を増やす

q 記録を止める

@a → 1の下に2が書かれる

@@ → 2の下に3が書かれる

じゃあ、100@@で103までの連番リストが作れるよね。

Macros

ビジュアル選択: `v`,`V`,`<C-v>`

<C-v>を使った例があった。そこでv と Vだ。選択モードになると、次の操作が実行出切る:

J → 全ての行を結合
< (関連: >) → 左へ(関連: 右へ)インデント
= → オートインデント

Autoindent

ビジュアル選択した全ての行の末尾に何かを追加しよう:

<C-v>
目的の行に移動しよう(jjj や <C-d> や /pattern や % …なんかで)
$ 行末に移動
A テキストを書き込み、ESC

Append to many lines

分割: `:split` と `vsplit`

主なコマンドは以下の通りですが、:help splitで調べるべきでしょう

:split → 分割(:vsplit は縦分割)ウィンドウを作る

<C-w><dir> : hjklで示す←↓↑→の方向へ分割を変更する

<C-w>_ (関連: <C-w>|) : 分割サイズを最大に(関連: vertical split)

<C-w>+ (関連: <C-w>-) : 分割サイズを増やす(関連: shrink)

Split

終わりに

これらは私が日々使用しているコマンドの90％だ。私は君が一日あたり1つないしは2つ以上の新しいコマンドを学習しないように提案しておく。 2～3週間後には、君はvimのパワーを君自身の手で感じ始めるだろう。

Vimの学習は単なるの暗記よりも多くの訓練の方が必要となる。幸いにもvimには幾つかの非常に有用なツールと優れたドキュメントが付属している。最も基本的なコマンドに慣れるまではvimtutorを実行しよう。また注意してこのページを読むべきだ: :help usr_02.txt

そして、!、折りたたみり、レジスタ、プラグインや、他の多くの機能について学ぶであろう。 vimの学習とは、ピアノを学ぶ様に素敵な事だ。

Posted at by mattn

2012/06/27

コードリーディング2日目。sort

昨日は rm を読みました。今日は、ずいぶん前に「GNU textutilsに入ってるsort(1)にはコア数によって動的にスレッドを生成してソートする処理が入ってるのでそういうの興味ある人はコード読むといいと思います。」と言ってた部分を読もうと思います。
ソースは昨日と同様に CoreUtils の src/sort.c です。
ソートのメイン処理は main の一番下の方にあって


  if (mergeonly)

    {

      struct sortfile *sortfiles = xcalloc (nfiles, sizeof *sortfiles);

      size_t i;



      for (i = 0; i < nfiles; ++i)

        sortfiles[i].name = files[i];



      merge (sortfiles, 0, nfiles, outfile);

      IF_LINT (free (sortfiles));

    }

  else

    {

      if (!nthreads)

        {

          unsigned long int np = num_processors (NPROC_CURRENT_OVERRIDABLE);

          nthreads = MIN (np, DEFAULT_MAX_THREADS);

        }



      /* Avoid integer overflow later.  */

      size_t nthreads_max = SIZE_MAX / (2 * sizeof (struct merge_node));

      nthreads = MIN (nthreads, nthreads_max);



      sort (files, nfiles, outfile, nthreads);

    }

この様に呼び出しています。mergeonly は -m を指定しない限り、false なのでデフォルトで下側に入ります。
num_processors は pthread_getaffinity_np 等を使い、コアの数を取得しています。ソート時に使う同時スレッド数は DEFAULT_MAX_THREADS、8になっています。オーバーフローを避ける為に、マージソート時がデータ量の半分以上スレッドを起こしても意味がない事への配慮もあります。
この値を使って


      size_t nthreads_max = SIZE_MAX / (2 * sizeof (struct merge_node));

さて sort 関数に入ります。


      while (fillbuf (&buf, fp, file))

        {

          struct line *line;



          if (buf.eof && nfiles

              && (bytes_per_line + 1

                  < (buf.alloc - buf.used - bytes_per_line * buf.nlines)))

fillbuf により逐次読みを行います。fillbuf は最大 256 * 1024 バイト貯まってバッファフルになるか改行文字(リミット文字)を見つけると行数をカウントアップします。


          if (1 < buf.nlines)

            {

              struct merge_node_queue queue;

              queue_init (&queue, nthreads);

              struct merge_node *merge_tree =

                merge_tree_init (nthreads, buf.nlines, line);

              struct merge_node *root = merge_tree + 1;



              sortlines (line, nthreads, buf.nlines, root,

                         &queue, tfp, temp_output);

              queue_destroy (&queue);

              pthread_mutex_destroy (&root->lock);

              merge_tree_destroy (merge_tree);

            }

          else

            write_unique (line - 1, tfp, temp_output);

貯めたバッファが1行以上であれば sortlines を呼びます。


  if (nthreads > 1 && SUBTHREAD_LINES_HEURISTIC <= nlines

      && pthread_create (&thread, NULL, sortlines_thread, &args) == 0)

    {

      sortlines (lines - node->nlo, hi_threads, total_lines,

                 node->hi_child, queue, tfp, temp_output);

      pthread_join (thread, NULL);

    }

  else

    {

      /* Nthreads = 1, this is a leaf NODE, or pthread_create failed.

         Sort with 1 thread. */

      size_t nlo = node->nlo;

      size_t nhi = node->nhi;

      struct line *temp = lines - total_lines;

      if (1 < nhi)

        sequential_sort (lines - nlo, nhi, temp - nlo / 2, false);

      if (1 < nlo)

        sequential_sort (lines, nlo, temp, false);



      /* Update merge NODE. No need to lock yet. */

      node->lo = lines;

      node->hi = lines - nlo;

      node->end_lo = lines - nlo;

      node->end_hi = lines - nlo - nhi;



      queue_insert (queue, node);

      merge_loop (queue, total_lines, tfp, temp_output);

    }



  pthread_mutex_destroy (&node->lock);

nthreads が 2 以上で行数が 128 * 1024 未満であればスレッドを起動しています。これによりマージソートの最小比較単位に分割しているんですね。そうでない場合は、sequential_sort により、上部側と下部側に分け再帰を行いながら分割しつつ最小単位で比較し、その結果をマージしています。


static void

sequential_sort (struct line *restrict lines, size_t nlines,

                 struct line *restrict temp, bool to_temp)

{

  if (nlines == 2)

    {

      /* Declare 'swap' as int, not bool, to work around a bug

         <http://lists.gnu.org/archive/html/bug-coreutils/2005-10/msg00086.html>

         in the IBM xlc 6.0.0.0 compiler in 64-bit mode.  */

      int swap = (0 < compare (&lines[-1], &lines[-2]));

      if (to_temp)

        {

          temp[-1] = lines[-1 - swap];

          temp[-2] = lines[-2 + swap];

        }

      else if (swap)

        {

          temp[-1] = lines[-1];

          lines[-1] = lines[-2];

          lines[-2] = temp[-1];

        }

    }

  else

    {

      size_t nlo = nlines / 2;

      size_t nhi = nlines - nlo;

      struct line *lo = lines;

      struct line *hi = lines - nlo;



      sequential_sort (hi, nhi, temp - (to_temp ? nlo : 0), to_temp);

      if (1 < nlo)

        sequential_sort (lo, nlo, temp, !to_temp);

      else if (!to_temp)

        temp[-1] = lo[-1];



      struct line *dest;

      struct line const *sorted_lo;

      if (to_temp)

        {

          dest = temp;

          sorted_lo = lines;

        }

      else

        {

          dest = lines;

          sorted_lo = temp;

        }

      mergelines (dest, nlines, sorted_lo);

    }

}

mergelines は以下の通り、ポインタによるスワッピング。


static void

mergelines (struct line *restrict t, size_t nlines,

            struct line const *restrict lo)

{

  size_t nlo = nlines / 2;

  size_t nhi = nlines - nlo;

  struct line *hi = t - nlo;



  while (true)

    if (compare (lo - 1, hi - 1) <= 0)

      {

        *--t = *--lo;

        if (! --nlo)

          {

            /* HI must equal T now, and there is no need to copy from

               HI to T. */

            return;

          }

      }

    else

      {

        *--t = *--hi;

        if (! --nhi)

          {

            do

              *--t = *--lo;

            while (--nlo);



            return;

          }

      }

}

さて、ここで気になるのがスレッド間の競合ですが sortlines の if 文の下側


    {

      /* Nthreads = 1, this is a leaf NODE, or pthread_create failed.

         Sort with 1 thread. */

      size_t nlo = node->nlo;

      size_t nhi = node->nhi;

      struct line *temp = lines - total_lines;

      if (1 < nhi)

        sequential_sort (lines - nlo, nhi, temp - nlo / 2, false);

      if (1 < nlo)

        sequential_sort (lines, nlo, temp, false);



      /* Update merge NODE. No need to lock yet. */

      node->lo = lines;

      node->hi = lines - nlo;

      node->end_lo = lines - nlo;

      node->end_hi = lines - nlo - nhi;



      queue_insert (queue, node);

      merge_loop (queue, total_lines, tfp, temp_output);

    }

で、2線共にシーケンシャルソートした後、queue_insert を呼び出しています。


static void

queue_insert (struct merge_node_queue *queue, struct merge_node *node)

{

  pthread_mutex_lock (&queue->mutex);

  heap_insert (queue->priority_queue, node);

  node->queued = true;

  pthread_mutex_unlock (&queue->mutex);

  pthread_cond_signal (&queue->cond);

}

ミューテックスでロックし、ヒープ領域に差し込んでいます。ねじ込んだアイテムを compare を使いながら移動位置を探します。2分探索ですね。


static void

heapify_up (void **array, size_t count,

            int (*compare) (void const *, void const *))

{

  size_t k = count;

  void *new_element = array[k];



  while (k != 1 && compare (array[k/2], new_element) <= 0)

    {

      array[k] = array[k/2];

      k /= 2;

    }



  array[k] = new_element;

}

merge_loop は以下の通り。


static void

merge_loop (struct merge_node_queue *queue,

            size_t total_lines, FILE *tfp, char const *temp_output)

{

  while (1)

    {

      struct merge_node *node = queue_pop (queue);



      if (node->level == MERGE_END)

        {

          unlock_node (node);

          /* Reinsert so other threads can pop it. */

          queue_insert (queue, node);

          break;

        }

      mergelines_node (node, total_lines, tfp, temp_output);

      queue_check_insert (queue, node);

      queue_check_insert_parent (queue, node);



      unlock_node (node);

    }

}

merge_lines は queue_insert でインサートされているマージ指示に対して実際にマージ処理を行い、親ノードを指定してマージ指示を依頼しています。 queue_pop で queue からマージ指示を取り出し


static void

mergelines_node (struct merge_node *restrict node, size_t total_lines,

                 FILE *tfp, char const *temp_output)

{

  struct line *lo_orig = node->lo;

  struct line *hi_orig = node->hi;

  size_t to_merge = MAX_MERGE (total_lines, node->level);

  size_t merged_lo;

  size_t merged_hi;



  if (node->level > MERGE_ROOT)

    {

      /* Merge to destination buffer. */

      struct line *dest = *node->dest;

      while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)

        if (compare (node->lo - 1, node->hi - 1) <= 0)

          *--dest = *--node->lo;

        else

          *--dest = *--node->hi;



      merged_lo = lo_orig - node->lo;

      merged_hi = hi_orig - node->hi;



      if (node->nhi == merged_hi)

        while (node->lo != node->end_lo && to_merge--)

          *--dest = *--node->lo;

      else if (node->nlo == merged_lo)

        while (node->hi != node->end_hi && to_merge--)

          *--dest = *--node->hi;

      *node->dest = dest;

    }

  else

    {

      /* Merge directly to output. */

      while (node->lo != node->end_lo && node->hi != node->end_hi && to_merge--)

        {

          if (compare (node->lo - 1, node->hi - 1) <= 0)

            write_unique (--node->lo, tfp, temp_output);

          else

            write_unique (--node->hi, tfp, temp_output);

        }



      merged_lo = lo_orig - node->lo;

      merged_hi = hi_orig - node->hi;



      if (node->nhi == merged_hi)

        {

          while (node->lo != node->end_lo && to_merge--)

            write_unique (--node->lo, tfp, temp_output);

        }

      else if (node->nlo == merged_lo)

        {

          while (node->hi != node->end_hi && to_merge--)

            write_unique (--node->hi, tfp, temp_output);

        }

    }



  /* Update NODE. */

  merged_lo = lo_orig - node->lo;

  merged_hi = hi_orig - node->hi;

  node->nlo -= merged_lo;

  node->nhi -= merged_hi;

}

大小比較しながら確保した領域内で並べ替えます。マージ対象がルートの線なら、マージ中に全ての並べ替えは完了しているはずなので、逐次アウトプットしていきます。


static void

write_unique (struct line const *line, FILE *tfp, char const *temp_output)

{

  static struct line saved;



  if (unique)

    {

      if (saved.text && ! compare (line, &saved))

        return;

      saved = *line;

    }



  write_line (line, tfp, temp_output);

}

static 変数を使って前回値を保持し、unique 出力できる様にもしてあります。

以上がソートの処理です。スレッドの使い方ですが、Wikipedia のマージソートにある基本手順で言うと

データ列を分割する（通常、等分する）
各々をソートする
二つのソートされたデータ列をマージする

1、2の部分は排他無しに最小単位になるまでスレッドを作り、最小単位になった場合は後半戦として、sequential_sort を行ってそのマージを依頼する。
3は、1と2が行った処理結果 queue を抜き取りつつマージして行きながら、別スレッドが作ったキューもついでに処理する。fifo キューなので、最初に作ったキューが最後のキュー MERGE_ROOT となり、MERGE_ROOT ノードの場合に結果出力する仕組みです。

以上のソースを見た感想としては、非常にまどろっこしくて、データ量が少なけりゃ、とても無駄な事をやっている様にも見えます。sort という、一見単純そうな機能の割にはとてもしっかりしたジョブキューイングシステムが組まれているなーと思いました。1行あたりに保持するデータ量はIA32で16から20バイトなので、ちょっと大きい感じもしますが、Wikipedia のマージソートにあるgifアニメの処理を並列で行い、しかも行のテキストを別領域に確保している訳ではないので、トータルで言うとトントンくらいなのかもなーと思いました。
もしかすると、行数の少ないソートを数百回行う様な場合はスレッドを作らない -m の方が安定した速度を得られるのかもしれません。調べてませんが。

Posted at by mattn