著者アーカイブ 杉浦

著者:杉浦

画像処理の初歩

 コンピュータの世界において画像中の色はよくRGBAという数値で表されます。それぞれRed、Green、Blue、Alphaの略でまとまったものを画素と呼ばれます。RGBは色の強さをAlphaは大体の場合で透明度を表します。4項目は8bitで表せる0~255の範囲の整数で表されます。
 この色を表した値の変化によってさまざまな発展した情報を画像から得ることができます。例えば、境界です。色の急激な変化は何かと何かの境を表します。ある範囲のRGBAの微分をとることでその範囲の色の変化の大きさを得ることができ、境界を判断できますまた、近隣の画素の値と近づけることで画像をぼかしたり、ノイズを除去したりできます。近づけるためには中央値だったり、平均値だったりが使えます。逆に近隣の色の値と遠ざけることで各画素を強調することができます。例えば次の式
 加工後の画素=(9*加工前の画素-sum(周囲8マスの各画素))
です。RGBを常に同じ値にした場合にはモノトーンの画像にできます。
 色を値にすることは二次元信号として像をとらえられるということです。このためフーリエ変換を始めとした各種信号処理、ディープラーニングの様な機械学習、ベクトルや差分による圧縮などなどの像のための様々な技術がコンピュータ上で使われています。

著者:杉浦

正規表現を図示するWebアプリであるRegexperの紹介

 正規表現は便利なものですが巨大なものになると一見してわからなくなります。エスケープコードが必要になるような場合はますます謎の式になります。この記事で紹介するのは正規表現を状態遷移図の様に図示してくれるwebアプリであるRegexperです。Regexperはjavascriptの正規表現に対応しています。

Regexep

 以下の二つの正規表現を使用例に使います。
/^(?:[0-9]|[a-z]|[\._%\+-])+(?:@)(?:[0-9]|[a-z]|[\.-])+(?:\.)[a-z]{2,}$/i
^([a-zA-Z0-9])+([a-zA-Z0-9\._-])*@([a-zA-Z0-9_-])+([a-zA-Z0-9\._-]+)+$

 灰色のテキストボックスの中に正規表現を入れて”Display”と書かれたボタンをクリックで使用です。
/^(?:[0-9]|[a-z]|[\._%\+-])+(?:@)(?:[0-9]|[a-z]|[\.-])+(?:\.)[a-z]{2,}$/i

^([a-zA-Z0-9])+([a-zA-Z0-9\._-])*@([a-zA-Z0-9_-])+([a-zA-Z0-9\._-]+)+$

どちらもメールアドレスを表現しようとしている正規表現なのだと視覚から直観的にわかります。

著者:杉浦

コード中のif節を減らす

これの記事はシンプルなif節を減らすことについての記事です。
例えば、次のようなプログラムがあるとします。条件ABCの真偽に応じて01を返すプログラムです。

if A
    if B
        if C
            return 1;
        else
            return 0;
        end
    else
        if C
            return 0;
        else
            return 1;
        end
    end
else
    if B
        if C
            return 1;
        else
            return 0;
        end
    else
        if C
            return 1;
        else
            return 0;
        end
    end
end

このプログラムは一見読みにくく、また余分な動作があります。if節を減らすことで速度と可読性の向上が見込めます。単純な真偽を表に表します。ABCが条件、Rが返り値です。1は値の1の他に真の意味も持ちます。0は値の0の他に偽の意味も持ちます。

A B C R
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0

例えば~AB~C=1、AB~C=1です。~は否定の意味です。ここからB~C=1と短縮でき、以下の様にプログラムを変えることができます。

if B
    if C
        if A
            return 0;
        else
            return 0;
        end
    else
        return 1;
    end
else
    if C
        if A
            return 1;
        else
            return 0;
        end
    else
        if A
            return 1;
        else
            return 0;
        end
    end
end

判定が減った分、文量も処理量も減りました。
そんなこんなで真偽を最適化した場合、次のような式ができます。
1 = ~A~BC + B~C + A~C
この式に従った場合、以下の様にプログラムを変えることができます。

if C
    if ~A
        if ~B
            return 1;
        end
    end
else
    if A
        return 1;
    end
    if B
        return 1;
    end
end
return 0;

最初の書き方が愚直すぎるのもありますが随分と簡略化できました。
真理値の短縮には多くのアプリ、ライブラリもあるのでコードを簡略化したい際にはググって使うのが良いと思います。

著者:杉浦

ハッシュ探索

 人間が本棚から特定本を探す時、どのような行動をとるでしょうか。
 慣れ親しんだ自宅の本棚ならここに入れてある、と一瞬で目当ての本の場所がわかると思います。図書館の様な場所なら辞書内を探す様にタイトルを追って大体の場所を行ったり来たりして探していくと思います。前者と後者の違いは題名と保管場所に密接な関係があるかないかの違いです。前者ならば題名を思い出した時に保管場所も共に思い出しているでしょう。後者ならば題名からこのあたりにあるだろうと推測を付けているでしょう。データ名がコンピュータがデータを保存している場所を示した場合、コンピュータも自宅の本棚から本を見つける様に一瞬で目当てのデータを探せるでしょう。ハッシュ探索は大体そのような方法です。
 コンピュータのデータ格納場所は番地、値で表せます。データ名もまた、値で表せます。データの格納番地をデータ名とした場合、データ名の場所にアクセスしにいけばそれで一発でデータを読み出せます。大体このような考えがハッシュ探索です。実際には、格納場所はもっと狭く、格納番地を読み出すためのコストもバカにならないので、データそのままでなく何らかの別のものをキー(格納番地)として扱います。それでも多くの場合で他のデータ構造より高速に特定のデータを読み出せます。
 多くの言語にはマップというデータ構造が備えられておりハッシュ探索に対応しています。先ほどのデータ名や格納番地足るキーと共にデータ値を登録していくデータ構造です。
追記:人間の頭が一瞬で目当てのデータを見つけられる主な仕組みはハッシュ探索の仕組みというより、頻繁に使われるデータや最近使用されたデータを上位(記憶の上層)に保管している仕組みです。

著者:杉浦

javascriptのDOM操作の高速化に使える機能:DocumentFragment

 これはいくらかjavascriptを知っている人向けの記事で、javascriptの機能の一つDocumentFragmentの紹介です。
 DocumentFragmentはDOMツリーとほぼ同じ機能を持つ独立したノード、小型のdocumentの様なものを定義するインターフェースです。ルートであるdocumentのDOMツリーを操作した場合、レンダリングがしょっちゅう働きますが、DocumentFragmentに従って作成されたDOMツリー同然のノードを操作した場合はレンダリングが全く働きません。このためDocumentFragmentを用いてDOMツリーに連結する予定の木を作成、作成された木を連結、とすることで比較的高速にDOMツリーを操作できます。。
 DOMツリーとはHTMLドキュメントなどを木構造オブジェクトとして扱う際の木のことです。DOMツリー中のノードが削除、変更されたり、新たにノードが追加された場合、レンダリングが行われる場合があります。DOMの操作は重い動作である、という意見、記事がいくつも見られる理由の一つはおそらくこれでしょう。もっとも最近はブラウザも賢くなりレンダリング回数を少なくしようとしていますが、警戒するに越したことはないです。IEにおいてfor文中でappendChildを回す部分のあったプログラムを走らせたら、レンダリングの実行回数がえらいことになっていました。
 DocumentFragment – Web API インターフェイス | MDN
 使い方
var df = document.createDocumentFragment();
 このdfを好き勝手いじれます。dfをどこぞに連結する場合、DocumentFragmentの頂点ノードは削除され、一つの木として自然な形になります。
 レンダリングなどのブラウザの内部について述べられた記事:ブラウザのしくみ: 最新ウェブブラウザの内部構造 – HTML5 Rocks

著者:杉浦

ボトルネックの考え方

 ボトルネックは一つのアプリケーションの様な何かのまとまりを改善する時に使用できる考え方です。ボトルネックのおおまかな意味は次の通りです。

物事がスムーズに進行しない場合、遅延の原因は全体から見れば小さな部分が要因となり、他所をいくら向上させても状況改善が認められない場合が多い。このような部分を、ボトルネックという。

(5/14wikipediaより引用)
 例えば一連の処理、A-Zがあり、合計で52秒の実行時間がかかるとします。この一連の処理の実行にかかる内訳を、処理Kにかかる実行時間が30秒、他の処理は合計22秒で実行可能とします。この一連の処理の実行時間を50%短縮する、という課題が出た場合、処理Jの実行時間を短縮しなければ他所をいくら向上させても状況改善が認められません。この場合、処理Jをボトルネックな処理と言います。自分はあまり広い分野を知りませんがプログラミングなどの情報科学、料理などの日常生活の様な場面でボトルネックは往々にして現れます。またボトルネックがある問題の場合、ボトルネックの解決こそが問題の解決そのものとなる時がままあります。問題を分割し単純な小さな複数の問題に分けて考えるという手法(分割統治法)が複雑な問題を解決をしようとする場合に有効とされるのには、物事を考えやすくする他にもボトルネックである部分を見つけるという理由もあります。

著者:杉浦

ライフゲームの紹介

 ライフゲームは格子状の世界の上に置かれたセル達の模様がルールによって変化していく様を眺めるゲームです。
 お手軽に遊ぶならJohn Conway’s Game of Lifeがおすすめです。ライフゲームでgoogle検索をすると検索画面の背景でライフゲームが始まります。がっつりと遊ぶならGolly Game of Life Home Pageのフリーソフトがおすすめです。また、プログラムの練習として自分で作ってみるのもよいです。定番なのかハッカソンの課題として出されたことが何度かありました。
 ライフゲームの模様の変化(セルの生死)は次のルールに従います。(日本語版wikipediaより引用)
ライフゲームでは初期状態のみでその後の状態が決定される。碁盤のような格子があり、一つの格子はセル(細胞)と呼ばれる。各セルには8つの近傍のセルがある (ムーア近傍) 。各セルには「生」と「死」の2つの状態があり、あるセルの次のステップ(世代)の状態は周囲の8つのセルの今の世代における状態により決定される。

誕生 死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生存 生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
過疎 生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
過密 生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

下に中央のセルにおける次のステップでの生死の例を示す。生きているセルは■、死んでいるセルは□で表す。

 ライフゲームでは面白い、興味深いとされる定番のパターンがいくつもあります。チューリングマシンを再現したパターンもあります。詳しくは調べてみてください。

グライダー(消えずに移動し続けるパターン) ブロック(最小の静的状態の一つ)
著者:杉浦

HTMLの勧告とCSSの仕様

 HTML、CSSを始めとする様々なWWW(World Wide Web)上で用いられる技術の標準化を進める団体としてW3C(World Wide Web Consortium)という団体があります。W3Cの活動にはWHATWF(Web Hypertext Application Technology Working Group)が開発しているHTMLの仕様の勧告とW3C自身が開発しているCSSの仕様書の公開も含まれています。
以下はW3Cの公開している資料へのショートカットです。

HTML & CSS – W3C:HTMLとCSSについての基点になるページ
All Standards and Drafts – W3C:文字通り、全ての標準と草稿。仕様や技術文書が色々

 和訳がない文書が多数、文章量が多量、といったため読むのは結構な苦労ですが、情報はとても多く、ブラウザ依存の問題以外は網羅されているはずです。詳しく調べたい時にあたる資料として使えます。

著者:杉浦

phpにおけるsort

phpのsort関数の説明です。
 phpの説明書:原文和訳
 phpに備え付けのソート関数はここにある以下の表の通りです。

ソート関数の特性
関数名 ソートの基準 キーと値の相関関係 ソート順 関連する関数
array_multisort() 連想配列の場合は維持し、数値添字配列の場合は維持しない 最初の配列、あるいはソートオプション array_walk()
asort() 維持する 昇順 arsort()
arsort() 維持する 降順 asort()
krsort() キー 維持する 降順 ksort()
ksort() キー 維持する 昇順 asort()
natcasesort() 維持する 大文字小文字を区別しない自然順 natsort()
natsort() 維持する 自然順 natcasesort()
rsort() 維持しない 降順 sort()
shuffle() 維持しない ランダム array_rand()
sort() 維持しない 昇順 rsort()
uasort() 維持する ユーザー定義 uksort()
uksort() キー 維持する ユーザー定義 uasort()
usort() 維持しない ユーザー定義 uasort()

 キーと値の相関関係はキーAなら値a、キーBならbといった関係のことです。マップ的に使っていて配列のキー名に意味があるなら相関関係を維持するべきで、配列のキー名が順番を表すただの数字の様なものなら維持は不要になるでしょう。
 自然順は1A,10A,100Aと並ぶことです。不自然な辞書順は’0’は’A’より小さいからと100A,10A,1Aと並べることです。詳しくはNatural Order String Comparisonを参照するとよいです。
 配列中配列などの複雑なソートをしたいときはユーザ定義ソートを使用することで解決でき安栖。任意の比較関数$value_compare_funcを定義してusort ( array &$array , callable $value_compare_func )と記述します。比較関数の定義にはstrcmp()の様な備え付けの比較関数を利用すると楽です。
 phpのソートはC言語の関数であるsort()を拡張したものです。phpのソースコード中のext/standard/array.cに上記の関数の中身が色々書いてあります。さらにarray.c中のzend_hash_sort()、Zend/zend_hash.h中のzend_hash_sort()内のzend_hash_sort_ex()、zend_hash.c中のzend_hash_sort_ex()と追っていくことができます。

著者:杉浦

浮動小数点数

 浮動小数点数は01のみで少数のような細かい数からn^mの様な巨大な数までを表現する方法です。浮動小数点は図の様に、仮数部^(符号ビット*指数部)で表されます。赤が仮数部、青が符号ビット、緑が指数部です。図はIEEE 754 形式の単精度でPC上でよく使われています。

 それなりの精度の仮数部と仮数部を拡縮する符号ビットと指数部によって広い範囲の値を表現できます。また、仮数部をhoge乗するという点からわかるように一定の相対誤差を保ちます(相対誤差:x%の誤差というように表せる誤差。大きな数ほど誤差が大きく、小さな数ほど誤差が小さい。)。この誤差は値の表現を省略する誤差であり、丸め誤差と呼ばれます。常に誤差があるというのが特徴で、丸め誤差が積み重なるような計算(値を表現してから加算することを繰り返すなど)をするプログラムを書くと大きな誤差が生まれて惨事になりやすいです。