著者アーカイブ 杉浦

著者:杉浦

テキスト比較ツール difffの紹介

 difff
 gitにあるソースコード
 difffは手軽にweb上で差分によるテキストの比較ができるツールです。difffは文字単位での細かい差分表示をしてくれるため、人間の目で比較するような小さな文を比較するときに特に役に立ちます。web上のやりとりのため、あまり巨大な文字列を比較するとタイムアウトをもらったりするのが玉に瑕です。巨大なのはよくないと書きましたが10万文字同士ぐらいなら時間こそかかりますが、問題なく動きました。また、テキストエリアに文字列を入力する形なのでdifff単独で複数のファイル間の比較を行うのも手間です。
 windowsのコマンドラインにはfcという行単位でファイルを比較する命令があります。他のものにも同じようなものはあるでしょう。手軽さの他にも巨大なファイル、多数のファイル、行単位の比較で十分などなど目的に合わせて使い分けるとよいと思います。

著者:杉浦

documentFragmentをIEで使う方法

 DocumentFragmentは小型のdocumentの様なものを定義する関数です。DocumentFragmentで定義されたDOMは画面に反映されません。
DocumentFragment – Web API インターフェイス | MDN
 下の画像の表はDocumentFragmentの対応表です。

 見ての通りInternet Explorerは2018/05/22時点でBasic support、querySelector、querySelectorAllにのみしか対応していません。他にも内部にDocumentFragmentを作成するコンテンツテンプレート要素であるタグにも対応していません。このためgetElementIDのようなdocumentに対してよく使用する関数すらDocumentFragmentにかけようとするとエラーないし予期せぬ動作を招くことがあります。基本サポートの範囲がよくわからなかったので、実装していないのではないかと疑い同等の機能を他の記述で試すぐらいしか解決法がわかりませんでした(W3Cの仕様書なり技術書なりにあるはず)。querySelector、querySelectorAllには対応しているので要素探索は楽なので、対象の要素に対してappendChild等の基本的であろうコードを書くのがコーディングの方針になると思います。
 InternetExplorerはFirefox、chromeなどの他ブラウザよりも律義にレンダリングを頻繁にしてくれます。そのためDOMの追加が大量にあるような場合は一度DocumentFragmentなどの画面に影響しない部分でDOMをまとめて構成、一括してdocumentにつなげる方がとても良いです。以下はtable_masterというIDのついた親を持ち、hoge_tableというIDのついたtable内のtbody_topというIDのついたtbodyを、tbody内のHTMLコードを表す文字列hoge_strで置き換える例です。


var df = document.createDocumentFragment();
df.appendChild(document.getElementById("hoge_table"));
df.querySelector("#tbody_top").innerHTML = "";
var tbd = document.createElement("tbody")
hoge_str = "abc";
tbd.innerHTML = hoge_str;
while(tbd.firstChild){
	df.querySelector("#tbody_top").appendChild(tbd.firstChild);
}
document.getElementById("table_master").appendChild(df.firstChild);
著者:杉浦

画像処理の初歩

 コンピュータの世界において画像中の色はよく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:文字通り、全ての標準と草稿。仕様や技術文書が色々

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