ブログシステムを MovableType から WordPress に移行したものの、写真の扱いが一部変わったので、その修正作業に追われた。

ひとつは MovableType で活用した Lightbox というプラグインの移行問題。Lightbox を導入すると、小さいサイズ(アイキャッチ画像)の写真を記事に埋め込み、そこをクリックすると写真が元サイズで大きく拡大表示される。記事の横幅が600ドットとか制限があるため、サイズがそれ以上の写真を見せるには、Lightbox が必要だったわけだ。

アイキャッチ画像の作成はLightboxによって自動的に作成される。縮小したいサイズを指示するだけでOK。

できあがったhtmlコードは一例として、以下のようになっている。

<a rel="lightbox" href="/hobby/img/
130525-8.png">
<img alt="130525-8.png"
src="/hobby/assets_c/2013/05/
130525-8-thumb-510x486-1487.png"
class="mt-image-center" style="text-align: center; display: block;
margin: 0 auto 20px;" height="486" width="510" /></a>

しかし、このままでは WP に移行しても画像は表示されない。代わりに、ファイル名の表示があって、そこをクリックしてはじめて画像が表示される。致命的エラーにはならないが、改善したい。

試しに、WP では以下のように直すと画像が難なく表示される。

<a href="/hobby/img/130525-8.png">
<img alt="130525-8.png"
src="/hobby/img/130525-8.png"
class="mt-image-center" style="text-align: center; display: block;
margin: 0 auto 20px;" height="486" width="510" /></a>

整理すると、修正箇所は以下の3点。

  1. rel=”lightbox” を削除
  2. assets_c/2013/05 を img に置き換え
  3. -thumb-510×486-1487 を削除

手動でやるのであれば、時間がかかるが、いつかは修正が終わる。ただ、記事の数が2500、一つの記事に画像が複数の場合も結構ある。ということで、自動修正を試みた。

wp での記事一括修正プラグインとして、Search Regex が有名。何しろ、正規表現が使えるから。しかし、ネットで調べても、earch Regex の正規表現をまともに説明するところはあまりにも少ない。ゴミ記事のオンパレードだからね、ネットは。

最終的に、トライアンドテストで以下のように使うことにした。結果オーケー。

  1. rel=”lightbox” の削除。
    正規表現は必要なく、ヌル文字で置き換えれば済む。
  2. assets_c/2013/05 の置換。
    正規表現
    Search pattern: #assets_c/\d+/\d+#
    Replace pattern; img
  3. -thumb-510×486-1487 の削除。
    正規表現
    Search pattern: #-thumb-\d+x\d+-\d+.#
    Replace pattern: .

また、上の例と関係ないが、Search pattern に ( ) をつけることによって、その部分を Replace pattern で再利用することもできる。

Search pattern: #daily/img/([\d]+)-([\d]+)-([\d]+).html#
Replace pattern: daily/img/$1-$2.jpg
Result: daily/img/12-3456-789.html → daily/img/12-3456.jpg

Search pattern: #hobby/img/([\d]+)-([\d]+).html#
Replace pattern: hobby/img/$1.jpg
Result: hobby/img/1234-789.html → hobby/img/1234.jpg

大文字の拡張子を小文字に統一しないといけないので、所定のディレクトリにおいて、つぎのコマンドを使った。OSはCentos 6.5。

#rename .PNG .png *.PNG
#rename .JPG .jpg *.JPG

Unix (Linux) は数十年遊んできたが、rename コマンドを使った回数はそう多くない。勿論 mv コマンドでもできないことはないが面倒。

滅多にやらない作業なので、メモしておく。

/etc以下が逝かれたCentos 5.5 のOSディスクからデータを救出することが目標。

① 外付け光学ドライブを用意し、Centosの入ったDVDをセットして、DVDから立ち上げ。
② Linuxのインストール画面が出てきたら、すかさずコマンド linux rescue をキーイン。
③ 言語、キーボード種類、ネットワーク設定画面で適宜選択し、次のRescue画面をskip。
④ コマンド fdisk -l をキーインし、ディスク構成を確認。
 <画面表示の一部メモ> なお、内蔵HDD(160GB)以外に、外付けUSBメモリ(4GB)を今回救出のために使った。
 Disk /dev/sda: 160.0 GB, 160041885696 bytes
 /dev/sda1 * 1 13 104391 83 Linux
 /dev/sda2 14 19457 156183930 8e Linux LVM
 Disk /dev/sdb: 4051 MB, 4051697664 bytes
 /dev/sdb1 * 1 1090 3956720 c W95 FAT32 (LBA)
⑤ lvm pvscan
    lvm vgscan
    lvm lvscan
と3つのコマンドをキーインし、論理ボリュームマネージャをアクティブ。
⑥ lvm vgchange -ay とキーインし、ボリュームグループ VolGroup00 をアクティブ。
 2 logical volume(s) in volume group “VolGroup00” now active
⑦ もう一度 lvm lvscan とキーインし、状態確認。
 ACTIVE ‘/dev/VolGroup00/LogVol00’ [146.47 GB] inherit
 ACTIVE ‘/dev/VolGroup00/LogVol01’ [2.47 GB] inherit
⑧ いよいよマウント
 mkdir /mnt/img/
 mount /dev/volGroup00/LogVol00 /mnt/img/
⑨ 壊れたHDDの内容が/mnt/img下に現れ、成功。

最後に、ファイルコピー先用USBメモリをマウント。
 mkdir /mnt/flash
 mount -t vfat /dev/sdb1 /mnt/flash

効率的に約数の個数を求めるアルゴリズムを考えているが、まだ四苦八苦している状態。つまり、1~500万までの整数について、それぞれの約数の数を一気に求めたい。

個々の整数なら、素因数分解して、因数の指数の積で約数の数が分かるのだが、1個1個やっているのでは、遅すぎて話にならない。

それよりも多少高速なプログラムは以下の通り。それでも数秒かかってしまう。

#define MAX   5000000
int c[MAX+10];  /* 約数の数を記録する */
void calc(void)
{
    int i, j;
    for (i = 1; i <= MAX; i++) c[i] = 1;
    for (j = 2; j <= MAX; j++) {
        for (i = j; i <= MAX; i+=j) c[i]++;
    }
}

プログラム自体は約数の定義そのものなので、面白みがないけど、圧倒的に分かりやすい。

さて、約数の数について、規則性を見るために、500万までの整数のうち、約数の個数が 1, 2, 3, …100となる整数の個数をリストアップしてみた。

約数の数が1の整数は1だけ。約数の数が2の整数は素数、つまり500万までの整数のうち、素数となる整数は348513個もある。だが、約数の数が8の整数が一番多いことに不思議さを感じている。ほかにも面白いことが沢山潜んでいるようだ。

(1,1) (2,348513) (3,331) (4,978982) (5,15) (6,189382) (7,6) (8,1118592) (9,630) (10,34670) (11,2) (12,429792) (13,2) (14,8631) (15,213) (16,689491) (17,1) (18,38545) (19,1) (20,71017) (21,89) (22,675) (23,1) (24,362994) (25,13) (26,201) (27,386) (28,16023) (29,0) (30,11399) (31,0) (32,248237) (33,21) (34,20) (35,11) (36,61776) (37,0) (38,7) (39,11) (40,50345) (41,0) (42,2722) (43,0) (44,984) (45,209) (46,0) (47,0) (48,146533) (49,2) (50,703) (51,3) (52,243) (53,0) (54,3921) (55,4) (56,9754) (57,1) (58,0) (59,0) (60,15024) (61,0) (62,0) (63,70) (64,50410) (65,2) (66,208) (67,0) (68,11) (69,0) (70,292) (71,0) (72,31359) (73,0) (74,0) (75,33) (76,1) (77,2) (78,59) (79,0) (80,15341) (81,84) (82,0) (83,0) (84,2909) (85,0) (86,0) (87,0) (88,400) (89,0) (90,1291) (91,1) (92,0) (93,0) (94,0) (95,0) (96,27891) (97,0) (98,27) (99,10) (100,700)

約数の数が与えられて、もとの整数を高速に計算するプログラムも考えたい。

最後に、約数の数が1, 2, 3, … 100となる、それぞれの最小整数をリストアップしておく。(ご注意、あくまでも500万までの整数のうち。拡大していけば、0の部分はなくなる。)

(1,1) (2,2) (3,4) (4,6) (5,16) (6,12) (7,64) (8,24) (9,36) (10,48) (11,1024) (12,60) (13,4096) (14,192) (15,144) (16,120) (17,65536) (18,180) (19,262144) (20,240) (21,576) (22,3072) (23,4194304) (24,360) (25,1296) (26,12288) (27,900) (28,960) (29,0) (30,720) (31,0) (32,840) (33,9216) (34,196608) (35,5184) (36,1260) (37,0) (38,786432) (39,36864) (40,1680) (41,0) (42,2880) (43,0) (44,15360) (45,3600) (46,0) (47,0) (48,2520) (49,46656) (50,6480) (51,589824) (52,61440) (53,0) (54,6300) (55,82944) (56,6720) (57,2359296) (58,0) (59,0) (60,5040) (61,0) (62,0) (63,14400) (64,7560) (65,331776) (66,46080) (67,0) (68,983040) (69,0) (70,25920) (71,0) (72,10080) (73,0) (74,0) (75,32400) (76,3932160) (77,746496) (78,184320)
(79,0) (80,15120) (81,44100) (82,0) (83,0) (84,20160) (85,0) (86,0) (87,0) (88,107520) (89,0) (90,25200) (91,2985984) (92,0) (93,0) (94,0) (95,0) (96,27720) (97,0) (98,233280) (99,230400) (100,45360)

1以外は、すべて偶数のようだ。

指定された約数の数となる、最小整数を求める (Smallest number with exactly n divisors) プログラム。それも面白そう。

約数の数が素数の場合は簡単に分かるが、素数以外の場合はどうなっているんだろう。

p11176.jpg

上図は整数の2進表示において、連続した1の並びの最大値の個数を表すもの。たとえば、3桁の2進数(つまり、整数0から7まで)は以下の通りだが、連続した1の並びの最大値は左から 0,1,1,2,1,1,2,3になっている。2進数101では、ビット1は2箇所にあるが、連続した1の並びの長さはそれぞれ1なので、全体としても1だ。

   000 001 010 011 100 101 110 111

そこで、同じ最大値のものをまとめて、最長値が0のものが1つ(000)、最長値が1のものが4つ(001,010,100,101)、最長値が2のものが2つ(011,110)、最長値が3のものが1つ(
111)になり、つまり 1 4 2 1という並び(上から3段目)が得られる。

ビット数をn、連続した1の並びの最長値をkとすると、整数それぞれにnとkはきまった対応関係になる。それを関数T(n,k)で表すと、つぎのような漸化式が成り立つ。

p11176-1.jpg

ただ、値がすぐに大きくなっていくので、多倍長整数か、実数を利用すること。

問題 UVa #11176 – Winning Streakを解くのに、こういう知識が勉強になる。

p11190.jpg

上式の通り、ごく簡単な、ベキ級数の合計を算出する問題。変数 l, h, k の値はともに1~15000000、hとlとの差は1000以内。

kの値が10以内なら、探せば、それなりの計算式が出てくるが、1500万ではそんな式は存在しないだろう。

力任せで、C言語の数学関数をそのまま使うと、無限大になってしまい、計算不能になる。

考え方
 合計値は級数の後ろの項によってほぼ決まるので、級数の末尾から計算することにしよう。

大事なことは、個々の項の値を、仮数部と指数部に分けておく。

例えば、999100、998100の値を
  999100 仮数部 0.9047921471 指数部 e+300
  998100 仮数部 0.8185668046 指数部 e+300
に分ける。

指数部の値が1つ違うと、項の値として1桁も違ってくる。指数部の値が5も違うと、5桁も右の部分にしか影響しないので、その後の計算を打ち切っても全体の合計値にほとんど影響がないだろうと考えてよい。例えば、
  880100 仮数部 0.2807160311 指数部 e+295
当たりから、その後の合計計算を打ち切る。基数やkの値が大きければ大きいほどすぐに打ち切ることになる。

また、合計の計算では、級数の末尾から項ひとつひとつ足していくが、個々の項の指数部は、末尾項の指数部の値に(つまり、最大指数部)に合わせて、仮数部の小数点をシフトさせる。
 上の例では、級数の末尾項が999100なら、個々の項の指数部の値をe+300に統一して、仮数部の値を合計する。
  970100 仮数部 0.0475525075 指数部 e+300

なお、シフトする前の仮数部、指数部は以下の数学関数でも求めることができる。

 ベキ乗 xk → 仮数部 pow(10, modf(k*log10(x), &e)) 指数部 左の e

最後に、元問題の検証データを載せておく(入力データの各行は左から、l, h, kの値)

10 10 1000000
14999001 15000100 1
14999001 15000000 15000000
0 0 15000000
0 1 15000000
0 0 1
Case 0001: 0.100000e0001000001
Case 0002: 0.164995e0000000011
Case 0003: 0.121628e0107641370
Case 0004: 0.000000e0000000001
Case 0005: 0.100000e0000000001
Case 0006: 0.000000e0000000001