2009-07-29

「本当はむずかしいクイックソート」解説

問題(?): http://d.hatena.ne.jp/sumii/20090722/p2

いきなり補足ですが、コメントでも指摘（ネタバレ？）されたとおり、一口に「クイックソート」と言っても（特にpartitionの）具体的実装は様々なバリエーションがあります。例えばホーアのオリジナルは、大まかに言っても

a[left]がpivotより大きくなるまでleft++する。ただしleftがaの範囲をオーバーしそうになったら中断して2にgotoする。
a[right]がpivotより小さくなるまでright--する。ただしrightがaの範囲をオーバーしそうになったら中断して3にgotoする。
leftがrightより小さかったらa[left]とa[right]を交換し、left++とright--をしてから、1にgotoする。
必要な場合はpivot要素を適切な位置に移動する（ミニクイズ：どのような場合にどこへ移動すればよいでしょうか？）

という感じで、決してシンプルではありません。Jon BentleyのProgramming Pearls（日本語訳「珠玉のプログラミング」）にも

Most discussions of Quicksort use a partitioning scheme based on two approaching indices like the one described in Problem 3. Although the basic idea of that scheme is straightforward, I have always found the details tricky---I once spent the better part of two days chasing down a bug hiding in a short partitioning loop. A reader of a preliminary draft complained that the standard two-index method is in fact simpler than Lomuto's, and sketched some code to make his point; I stopped looking after I found two bugs.

とありました（本は持っていないのでCACMの連載記事から引用）。要するに「（Hoareの）partition難しい」ということです。

さらに、アルゴリズムに関する標準的教科書の一つであるIntroduction to Algorithms（いわゆるCLRS）や、現時点の英語版Wikipediaには、（とりあえずa[0]をpivotとすると）次のようなpartitionアルゴリズムが載っています。

  pivot = a[0];
  s = 1;
  for (i = 1; i < n; i++) {
    if (a[i] <= pivot) {
      tmp = a[i];
      a[i] = a[s];
      a[s] = tmp;
      s++;
    }
  }
  tmp = a[0];
  a[0] = a[s - 1];
  a[s - 1] = tmp;

これはLomutoのpartitionと呼ばれることがあるようです（指摘感謝）。上述のProgramming Pearlsの

To partition the array around the value T we'll use a simple scheme that I learned from Nico Lomuto of Alsys, Inc.

が由来のようですが、そのLomutoという人が最初に（ないし自分で）考えたのかどうかはわかりませんでした。

（以下「後で書く」）

遅いにもほどがありますが（一年以上？）、とある授業のレポート課題の解説も兼ねて書きました（「詳しい説明」から下の部分）。

2009-07-28

完全準同型暗号

まだ現実的ではないようですが、「データを暗号化したままで一般的な計算（ブール代数上の乗算と加算）をする方法」がいつの間にか解かれていたそうです。（私の情報入手が遅い？）

http://doi.acm.org/10.1145/1536414.1536440

We propose a fully homomorphic encryption scheme -- i.e., a scheme that allows one to evaluate circuits over encrypted data without being able to decrypt.

(via http://techtarget.itmedia.co.jp/tt/news/0907/27/news03.html and http://www.mail-archive.com/cryptography@metzdowd.com/msg10571.html)

ところで、TechTargetの記事の

高度に数学的な構造を導入すると、暗号が破られやすくなってしまう

という部分を読んで？？？と思ったのですが、原文は

As you introduce more mathematical structure you make your system easier to crack

でした。（注：私は誤訳マニアです）

さらにところで、そろそろ「クラウド」という単語は禁止しても良いと思うのですがいかがでしょうか。

追記：専門的研究者の方による解説がありました。

2009-07-23

C++0xのconceptが見送られた件

世間で流行の話題に激しく乗り遅れていますが、それはさておき、大まかには同じような仕組みであるMLのfunctorがあれだけ難しかった（80年代から研究されて、現在でも話題になる）ことを考えれば、「むべなるかな」という感が強いように思います。残念ではありますが。

2009-07-23

アスペクト指向

AOPといえば、個人的には「modularityの定義を変更すれば、AOPはmodularである」と主張する論文が非常に印象的でした。

AOP enables modular implementation of crosscutting concerns, and modular reasoning in the presence of crosscutting concerns. But it requires a change in how module interfaces are specified. With AOP interfaces are extended as aspects cut through the primary module structure. So a module's interface cannot be fully determined without a complete system configuration.
But crosscutting concerns inherently require global knowledge to support reasoning. Using AOP, programmers get modular reasoning benefits for crosscutting concerns whereas without AOP they do not.

（強調筆者）
CACMか何かにも誰かの~~ツッコミ~~コメントが載っていたように思います。

2009-07-23

PPLサマースクール2009

http://www.is.noda.tus.ac.jp/ppl_ss09/
（via いろいろなところ）

個人的注目点：

しかし AOP の研究の成熟とともに、AOP の限界をふまえて、ポスト AOP をさぐる研究が活発化しています。例えば最近ではコンテキスト指向プログラミング (COP) が注目を集めていますし、Feature 指向 (FOP) も有名です。

（強調はすべてsumiiによる）

2009-07-22

本当はむずかしいクイックソート（またクイズ）

アルゴリズム入門の代表的例題のような「クイックソート」ですが、意外と「罠」が少なくありません。例えば以下のような教科書的実装を考えます。

void quicksort(int *a, int n) {
  int tmp, pivot, left, right;

  if (n <= 1) return;

  pivot = a[0];
  left = 1;
  right = n - 1;
  while (left <= right) {
    if (a[left] < pivot) {
      left++;
    } else {
      tmp = a[left];
      a[left] = a[right];
      a[right] = tmp;
      right--;
    }
  }

  tmp = a[right];
  a[right] = a[0];
  a[0] = tmp;

  quicksort(&a[0], right);
  quicksort(&a[left], n - left);
}

この実装を用いて、例えば乱数をソートすると

> cat qsort-rand-100000000.c
#include <stdlib.h>
#define N 1000000
int main() {
  int i, a[N];
  srand(0);
  for (i = 0; i < N; i++) {
    a[i] = rand() % 100000000;
  }
  quicksort(&a[0], N);
  return 0;
}
> gcc -O3 qsort.c qsort-rand-100000000.c -o qsort-rand-100000000
> time ./qsort-rand-100000000
0.109u 0.001s 0:00.11 90.9%     0+0k 0+0io 0pf+0w

のようになりますし、典型的最悪ケースでは

> cat qsort-worst.c
#define N 1000000
int main() {
  int i, a[N];
  for (i = 0; i < N; i++) {
    a[i] = -i;
  }
  quicksort(&a[0], N);
  return 0;
}
> gcc -O3 qsort.c qsort-worst.c -o qsort-worst
> time ./qsort-worst
331.605u 0.019s 5:31.67 99.9%   0+0k 0+0io 0pf+0w

のようになります。
さて、では

#define N 1000000
int main() {
  int i, a[N];
  for (i = 0; i < N; i++) {
    a[i] = i;
  }
  quicksort(&a[0], N);
  return 0;
}

の実行時間はどれぐらいになるでしょうか？

#include <stdlib.h>
#define N 1000000
int main() {
  int i, a[N];
  srand(0);
  for (i = 0; i < N; i++) {
    a[i] = rand() % 100;
  }
  quicksort(&a[0], N);
  return 0;
}

はどうでしょうか。予想と結果およびその理由を考察してください。…などと書いてしまうと、またどこか他の方の授業のレポート課題と被るかもしれませんが。

2009-07-22

第２回プログラム等価性クイズ：回答編

問題編：http://d.hatena.ne.jp/sumii/20090716/p1

ということで、回答はMLばかりでしたが（＆出題もMLにすべきでしたが）、最後まで無理をしてJavascript風に書くと、

var global;
function g(local) {
  global = local;
}
f(g);
global();

のような文脈C[f]を考えれば、C[f5]は（全体の実行が）停止しないのにC[f6]は停止するので、f5とf6は文脈等価になりません。

追記：「f5やf6が終了した後に無限ループしても良かったの？」とか「グローバル変数なんてずるい！」とか思った人は、

function call_f(g) {
  f(g);
}
function g(local) {
  function g2(local2) {
    local = local2;
  }
  call_f(g2);
  local();
}
call_f(g);

なる文脈C[f]も同様に（文脈等価性の）反例となります。（追記終わり）

さて、このように実際に反例があって文脈等価にならない例はまだ良いのですが、本当の問題は文脈等価になる場合（の証明）です。例えばf6を少し変えて、

function f7(g) {
  var x = 0, y = 0;
  function d() { d(); }
  function h() { if (x == 0) { y = 1; } else { d(); } }
  g(h);
  if (y == 0) { x = 1; } else { d(); }
}

という関数f7は（例えばreferenceを入れたλ計算において）f5と文脈等価でしょうか？*1　等価な場合は（数理論理学的に）証明してください。…などと言い出すと、いきなり研究レベルの問題になります。答えの例は私の最近の論文をご覧ください、と最後に宣伝。

*1:英ロンドン大学クイーン・メアリー校のヤン講師による例だそうです。