テキスト処理のための正規表現に計算理論はあるのかな


なるほど。これはおもしろい。

正規表現で素数判定

「C言語で素数判定」や「Rubyで素数判定」はそうでもないのに、「正規表現で素数判定」と言われるとおもしろいと思うのはなぜだろう。

4320122070計算の理論について勉強したことのある人は皆、正規表現で素数を記述することはできないことを知っている(たとえばSipser『計算理論の基礎』を参照)。だから、「正規表現で素数判定」と言われると、一瞬不思議な感じがするのだろう。

正規表現の表現力はもともとそんなに高くない。だから、

正規表現とは元々数学の概念だけあって、数学の問題を解くのにもってこいですね!(regexp – でエラトステネスのふるい)

なんていうのは、かなりミスリーディングなジョークだ。

とはいえ、テキスト処理のための正規表現は、計算理論における正規表現よりもかなり強力なものになっている。その原因の一つに、括弧でくくられた部分文字列を参照するために「\数字」という記法が導入されたことがあり、今話題にしている素数判定を可能にしたのも、この記法だ(拙著『Webアプリケーション構築入門』でも違いを強調している)

大事なことだから繰り返す。計算理論の正規表現では、素数判定はできない。テキスト処理の正規表現では、素数判定ができる。

素数判定というと、次のようなものをそうぞうする。

sub isPrime {
  my $n=shift;
  my $imax=sqrt($n);
  for (my $i=2; $i<=$imax; $i++) {
    if ($n % $i == 0) { return 0; }
  }
  return 1;
}

たとえば、isPrime(5)を評価すれば、5が素数かどうかがわかる。

これと同じことを、1を5個並べた文字列に対するマッチング「’11111′!~m/^1?$|^(11+?)\1+$/」で調べられる。

なるほど。これはおもしろい。

さて、素数判定には、「エラトステネスのふるい」という有名な方法がある。

「2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20」という数列が与えられたときに、2の倍数を消去、3の倍数を消去、・・・としていくと、素数列つまり「2,3,5,7,11,13,17,19」が残る。

今話題にしている記法では、「11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111,1111111111111,11111111111111,111111111111111,1111111111111111,11111111111111111,111111111111111111,1111111111111111111」という文字列が与えられたときに、「11,111,11111,1111111,11111111111,1111111111111,11111111111111111,1111111111111111111」が残るといい。

正規表現でエラトステネスのふるいはさすがに無理かな(正規表現で素数判定)

という問いで期待されている解答は、次のようなものなのだろう。

これと同じことを、「・・・」という文字列に対する置換「’・・・’=~s/???/???/」で調べられる。

最初に思いついたのはこんなもの。

#!/usr/bin/perl -w
use strict;
use warnings;

my $max=shift || 20;
my $nums=join ',',map {'1' x $_} (2 .. $max);
print "$nums\n";

while ($nums =~ m/(^|,)(1+)(,|$)/) {
  printf "$2,";
  $nums=~s/(^|,)($2)+(,|$)/,/g;
}

これは、理想の形式からはほど遠い。whileなんてものを許したら、表現力が正規表現と比べてどうなのか、まったくわからなくなってしまうのだから。

たった600円でオライリー本をKindleで読む。自動化。


注意:ここで紹介する方法よりも、calibreを使う方が簡単で、できあがりも高品質です。

「たった600円でオライリー本をiPadやKindleで読む。すてき。」という記事がすてきです。100冊買っても6万円って。でも、作業がちょっと面倒です。

iPadな人は、「perl – O’ReillyのiPhoneアプリ本からepubをぶっこぬく」にあるスクリプトを使えば、処理の大部分を自動化できます。

Kindleな人は、もう一手間かかるのですが、やはりスクリプトを書いて自動化しておきましょう。(参考:Kindle形式で目次を表示する。epubとの違い。Kindle用の目次を生成するスクリプトを書いた。

以下の作業を一つのスクリプトにまとめます。

  1. toc.ncxからのネームスペースの削除
  2. toc.htmlの生成と登録
  3. iPad用のepubの生成
  4. Kindle用のmobiの生成

準備

perl, zip, unzip, kindlegenにPATHを通しておいてください。Windowsの人は、Cygwinを使うといいでしょう(デフォルトではzipは入らないかもしれないので、インストール時に選択してください)。

使い方

perl ipa2mobi.pl ipaファイル名

Kindleで読み込んだところ

ipa2mobi.plのコード

#!/usr/bin/perl -w

#------------------------------------------------------------------
print "Step 1: http://blog.livedoor.jp/dankogai/archives/51484907.html\n";

use strict;
use warnings;
use File::Basename;
use File::Path;

sub clean{
    File::Path::rmtree('Payload');
}

my $src = shift;
#die "usage:$0 src.ipa [dst.epub]" unless -f $src;
die "usage:$0 src.ipa" unless -f $src;
#my $dst = shift;
my $dst = basename($src);
#if (!$dst){
#    $dst = basename($src);
    $dst =~ s/\w+$/epub/;
#}

system qw/unzip -q/, $src, qw/-x iTunes*/;
die $! if $!;
my $app = <Payload/*.app/book>;
clean and die "No book found in the archive" unless $app;
chdir $app;
my $updir = '../../..';
#system qw/zip -q0X/, "$updir/$dst", 'mimetype';
#system qw/zip -qXr9D/, "$updir/$dst", qw/ META-INF OEBPS/;
#chdir $updir;
#clean;
#system qw{open -a /Applications/iTunes.app}, $dst;


#------------------------------------------------------------------
print "Step 2: Modify toc.ncx\n";

chdir 'OEBPS';

rename 'toc.ncx', 'toc.bak';
open(IN, 'toc.bak');
open(NCX, '> toc.ncx');

while (<IN>) {
  $_ =~ s|<(/{0,1})ncx:|<$1|g;
  print(NCX $_);
}

close(IN);
close(NCX);
unlink 'toc.bak';


#------------------------------------------------------------------
print "Step 3: Create toc.html\n";

use XML::LibXML;

if (! -f 'toc.html') {
sub processNavPoint() {
  my $node=shift;
  my $depth=shift;
  if ($depth==0) { print HTML '<h1>'; }
  printf(HTML "<a href='%s'>%s</a>",
    $node->findvalue('content/@src'),
    $node->findvalue('navLabel/text'));
  if ($depth==0) { print HTML "</h1>\n"; }
  my @navPoints=$node->findnodes('navPoint');
  if ($#navPoints!=-1) {
    print HTML "<ul>\n";
    foreach my $navPoint (@navPoints) {
      print HTML '<li>';
      &processNavPoint($navPoint,$depth+1);
      print HTML "</li>\n";
    }
    print HTML "</ul>\n";
  }
}

  open(HTML, '> toc.html');
  binmode(HTML, ":utf8");
  print HTML <<EOF;
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html>
<head>
<title>Table of Contents</title>
</head>
<body>
EOF
  my $parser = XML::LibXML->new();
  my $toc = $parser->parse_file('toc.ncx');
  &processNavPoint($toc->findnodes('/ncx/navMap/navPoint'),0);
  print HTML '</body></html>';
  close(HTML);


#------------------------------------------------------------------
print "Step 4: Modify content.opf\n";

  rename 'content.opf', 'content.bak';
  open(IN, 'content.bak');
  open(OPF, '> content.opf');

  while (<IN>) {
    print(OPF $_);
    if (/<item id="cover"/) {
      print(OPF '    <item id="toc" href="toc.html" media-type="text/html"/>'."\n");
    }
    elsif (/<itemref idref="cover"/) {
      print(OPF '    <itemref idref="toc" linear="no"/>'."\n");
    }
    elsif (/<reference href="cover.html"/) {
      print(OPF '    <reference href="toc.html" type="toc" title="Table of Contents"/>'."\n");
    }
  }
  
  close(IN);
  close(OPF);
  unlink 'content.bak';
} # end of if (! -f 'toc.html')


#------------------------------------------------------------------
print "Step 5: Create ePub\n";

chdir '..';
system qw/zip -q0X/, "$updir/$dst", 'mimetype';
system qw/zip -qXr9D/, "$updir/$dst", qw/ META-INF OEBPS/;
chdir $updir;
clean;


#------------------------------------------------------------------
print "Step 6: Create mobi\n";

system qw/kindlegen/, "$dst";

問題

  • 目次の位置が本の最後になってしまいます(ジャンプすればいいのですが)
  • perlの作法、よく知りません。

って書いておけば、誰かがきれいなスクリプトに直してくれるはず。

ゆっくり読みたいときは目に優しいKindleが、開発中にリファレンスとして使いたいときは描画の速いiPadがいいと思います。iPhoneで読むのは大変だと思います。

オライリーとしては、情報弱者を食い物にするのと情報強者にサービスするののバランスを調整することで、利益が最大になればいいのでしょう。

追記:toc.htmlがすでに存在しているときには、step 3, 4を飛ばすようにしました。

追記:目次が最後になってしまう問題が解決しました(コメントに感謝)。

追記:ここで紹介する方法よりも、calibreを使う方が簡単で、できあがりも高品質です。

広く知られているinsertion sortのコードは駄目すぎる?


やねうらおさんによると、「広く知られているinsertion sortのコードは駄目すぎる」らしい。Wikipediaに載っているコード(2009.08.06版)を、

どこの馬鹿なアルゴリズムの教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。

というのだから穏やかではない。

私の座右の書『コルメン』も、

一連の劣悪なコードはこいつが犯人かも知れない。

と非難されてしまっている。

実際のところ、どのくらいの性能差になるのか、実験してみた。

こんな感じ(codepad)。

C++の標準ライブラリ(std)のsortとWikipedia版、やねうらお版の比較。単位は秒。挿入ソートの2つ(つまりWikipedia版とやねうらお版)は、実行時間の比も計算した(1より小さい値はやねうらお版が速いことを意味する)。

size	repetition	std	wiki	yane	y/w
4	1048576		0.3512	0.1576	0.1333	0.8459
8	233016		0.1148	0.06757	0.07265	1.075
16	65536		0.111	0.02996	0.1191	3.976
32	20971		0.1388	0.1141	0.09537	0.836

Timeout

codepadはすぐにタイムアウトしてしまうから、ベンチマークにはちょっと使えない(そもそも、ほかにどんなプロセスが動いているかわからないし)。

手元のCore i7 940 2.93GHz、主記憶9Gのマシンで実行してみる。

GCC 4.4.2(64ビット)の場合(コンパイルオプションは「-O3」のみ)

size    repetition      std     wiki    yane    y/w
4       6291456         0.3001  0.1896  0.1957  1.032
8       1398099         0.1766  0.1374  0.1427  1.039
16      393216          0.1201  0.09756 0.09972 1.022
32      125829          0.1045  0.08267 0.08463 1.024
64      43689           0.08399 0.07897 0.08637 1.094
128     16047           0.07033 0.09022 0.1061  1.175
256     6144            0.06053 0.118   0.1466  1.243
512     2427            0.05325 0.1704  0.2192  1.287
1024    981             0.04746 0.263   0.3447  1.311
2048    405             0.04273 0.4241  0.5613  1.323
4096    168             0.03847 0.697   0.9245  1.326
8192    72              0.0356  1.187   1.582   1.333
16384   30              0.03148 1.978   2.623   1.326
32768   12              0.02696 3.157   4.208   1.333
65536   6               0.02857 6.37    8.425   1.323

配列のサイズが64くらいまでなら、std::sortを使うよりも挿入ソートのほうが速いようだ。その範囲では、Wikipedia版とやねうらお版にあまり差はない(Wikipedia版が若干速いか)。

インテルC++コンパイラ 11.0(64ビット)の場合(コンパイルオプションは「-fast」のみ)

size    repetition      std     wiki    yane    y/w
4       6291456         0.2103  0.2164  0.2285  1.056
8       1398099         0.1464  0.1455  0.1447  0.9947
16      393216          0.107   0.106   0.1072  1.011
32      125829          0.1034  0.08955 0.09303 1.039
64      43689           0.08693 0.08898 0.09369 1.053
128     16047           0.07405 0.1059  0.1113  1.051
256     6144            0.06446 0.1456  0.1503  1.032
512     2427            0.05672 0.218   0.2219  1.018
1024    981             0.05066 0.3439  0.3462  1.007
2048    405             0.04571 0.5608  0.5618  1.002
4096    168             0.04118 0.9253  0.9255  1
8192    72              0.03799 1.578   1.579   1
16384   30              0.03406 2.628   2.629   1.001
32768   12              0.02887 4.197   4.208   1.003
65536   6               0.0307  8.464   8.46    0.9995

GCCのときよりstd::sortが速くなるのが早い。サイズ64ならもうstd::sortでよいようだ。GCCの場合より、std::sortが有利になるのが少し早い。Wikipedia版とやねうらお版にあまり差はない(やはり、Wikipedia版が若干速いか)。

Visual Studio 2008(32ビット)の場合(Releaseモード。オプションはデフォルトのまま)

size    repetition      std     wiki    yane    y/w
4       6291456         0.329   0.184   0.171   0.9293
8       1398099         0.209   0.14    0.142   1.014
16      393216          0.136   0.114   0.111   0.9737
32      125829          0.105   0.1     0.098   0.98
64      43689           0.103   0.099   0.097   0.9798
128     16047           0.093   0.113   0.115   1.018
256     6144            0.083   0.141   0.155   1.099
512     2427            0.075   0.195   0.226   1.159
1024    981             0.066   0.295   0.35    1.186
2048    405             0.061   0.469   0.568   1.211
4096    168             0.057   0.77    0.937   1.217
8192    72              0.051   1.313   1.617   1.232
16384   30              0.045   2.207   2.72    1.232
32768   12              0.038   3.57    4.398   1.232
65536   6               0.04    6.966   8.513   1.222

配列サイズ64くらいまでは、挿入ソートがstd::sortより速い。その範囲では、Wikipedia版よりやねうらお版のほうが若干速いか。

いずれにしても、配列サイズが小さいなら、挿入ソートを試す価値はありそうだ。しかし、GNUやインテルのコンパイラをよく使う私には、挿入ソートの細かいチューニングは早すぎる最適化になりそうだ。

小さい配列限定のすごく速いソートなら、ソーティングネットワークはどうだろう。サイズ7の場合はこんな感じ(codepad)。batcherがソーティングネットワーク。単位は秒。codepadだと遅いか。

GCC 4.4.2(64ビット)では、ソーティングネットワークが速い。

std::sort: 0.411432
wikipedia: 0.3258
yaneurao: 0.331935
batcher: 0.28106

インテルC++コンパイラ 11.0(64ビット)の場合

std::sort: 0.324813
wikipedia: 0.331058
yaneurao: 0.298131
batcher: 0.228164

ここで使っている関数bathcersortは、CPANにあるAlgorithm::Networkで作った。次のようなコードでASCIIアートを描ける。

use Algorithm::Networksort qw(:all);
$inputs=7;
my @network = nw_comparators($inputs, algorithm => 'batcher');
print nw_graph(\@network, $inputs), "\n";
o--^--------^-----^-----------------o
   |        |     |                  
o--|--^-----|--^--v--------^--^-----o
   |  |     |  |           |  |      
o--|--|--^--v--|--^-----^--|--v-----o
   |  |  |     |  |     |  |         
o--|--|--|-----v--|--^--v--|--^--^--o
   |  |  |        |  |     |  |  |   
o--v--|--|--^-----v--|--^--v--|--v--o
      |  |  |        |  |     |      
o-----v--|--|--------v--v-----|--^--o
         |  |                 |  |   
o--------v--v-----------------v--v--o

仕組みを知りたいという向きにはKnuthの第3巻が、「サイズ7限定じゃ意味ないし、任意のサイズでできるようにしたらコンパイルできないじゃん」という向きには『LET OVER LAMBDA Edition 1.0』がおすすめ。

47561461474434133632

フェルマーの最終定理の「反例」(Perl, awk, JavaScript, PHP編)


a=5999856, b=99992800, c=100000000としたときに、a^3 + b^3 = c^3になるような言語があります。codepadでちょっと試してみましょう。

Codepadで確認(Perl)

$a=5999856;
$b=99992800;
$c=100000000;
print $a*$a*$a+$b*$b*$b-$c*$c*$c;

Codepadで確認(PHP)

<?php
$a=5999856;
$b=99992800;
$c=100000000;
echo $a*$a*$a+$b*$b*$b-$c*$c*$c;
?>

ideone.comで確認(awk)

$ awk 'BEGIN{a=5999856; b=99992800; c=100000000; print a**3+b**3-c**3;}'
0

追記:フェルマーの最終定理の反「反例」(MPFR対応Gawk)

ideone.comで確認(JavaScript)

a=5999856;
b=99992800;
c=100000000;
print(a*a*a+b*b*b-c*c*c);

SchemeやPython、Rubyでもできますが、おかしいことがすぐにわかってしまいますね。

Codepadで確認(Scheme)

(display (- (+ (expt 5999856 3.0) (expt 99992800 3.0)) (expt 100000000 3.0)))

Codepadで確認(Python)

a=5999856;
b=99992800;
c=100000000;
print a**3.0+b**3.0-c**3.0;

Codepadで確認(Ruby)

a=5999856;
b=99992800;
c=100000000;
print a**3.0+b**3.0-c**3.0;

フェルマーの大定理が解けた!―オイラーからワイルズの証明まで (ブルーバックス)フェルマーの最終定理について数学者が書いた読み物がほしい方には、足立恒雄『フェルマーの大定理が解けた!―オイラーからワイルズの証明まで』がおすすめです。