spindle

dekosuke@twitter


Reblogged from otsune

動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のためにゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)と呼ばれるアルゴリズムを利用することにした。このアルゴリズムを開発したのは北大の湊先生で、ZDDによりすべての経路を見つけ出すアルゴリズムとしてクヌース先生のSIMPATHを使った。ZDDについてはクヌース先生も強い関心を持っていて、 The Art of Computer Programming Volume 4, Fascicle 1(TAOCP 4-1)ではBDD/ZDDの詳細な解説を読むことができる。演習問題の解説だけで書籍の半分を使っていることからしても気合の入れようがわかるだろう。

実際に自分のノートPCでZDDアルゴリズムを使ったコードを走らせたら、ほんの10秒程度で10×10マスの問題を解いてしまった。おねえさんがスパコンで25万年かかった問題をノートPCでたった10秒である。約8千億倍の高速化だ。これだけ劇的に変わるとやっぱり楽しい。そして、アルゴリズムの重要性を再認識させられた。

良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた (via otsune)

(via peckori)

Reblogged from defenestrador
defenestrador:

Elven Passage, by George Rushing.

defenestrador:

Elven Passage, by George Rushing.

(via wizardblue)

Reblogged from giggleplz
次期iPhoneの生産が追いつかないFoxconnが、中国で大学生数千人をインターンシッププログラムと称して強制的に工場で働かせているという( Shanghai Dailyの記事The Vergeの記事MOTHERBOARDの記事本家/.)。

ある学生によると、学生たちをFoxconnの工場に送るよう当局から命令があったという。本人の同意なくバスでFoxconnの工場に送りこまれた学生たちは、週6日、1日12時間の強制労働をさせられているそうだ。中国国営放送のリポートによれば、教師たちも1~2か月休講にすることに同意しているとのこと。学生たちには1か月あたり1,550人民元(およそ19,000円)が支払われるが、食費や宿泊費に数百人民元が必要だという。学生たちの不満は高まっており、Foxconnや当局を訴えるべきだという意見もみられる。しかし、過去に工場での労働を拒否した学生が大学で処罰の対象になったこともあり、卒業できなくなることを恐れる学生もいるとのことだ。
スラッシュドット・ジャパン - 中国の大学生数千人、次期iPhone製造のためFoxconnの工場で強制労働?
Reblogged from semi


(via usaginobike, semi)露伴。。

(via usaginobike, semi)

露伴。。

Reblogged from knightking

Reblogged from yuroyoro
「ハァ…ハァ…」だがここにきて明らかに Vim ニンジャの息が 乱れている。それもそのはず Vim ニンジャはその身に宿るニンジ ャ・ソウル=Vim スクリプトと融合していない。ある意味で付け焼 刃なのだ。 一方の Emacs ニンジャはニンジャ・ソウル=LISP と融合するた めに遺伝子サイバネティクス技術により生み出された。まさにニ ンジャの中のニンジャと言える。ニンジャ・ソウルにより生み出されるエディット・アトモスフィアを巧みに操る Emacs ニンジャ は実際ヤバイ。 files.kaoriya.net/docs/C82/SpartanVim-2.0-online.pdf (via mcsgsym)

(via higure)

Reblogged from gtokio
gtokio:

世界初の業務用レーザープリンタ、IBMの3800。印刷スピードはそこそこ早かったとか。

レーザープリンタのための書体

さて、それではArialがいかに生まれたかを見ていきましょう。1975年にIBMは最初の業務用レーザープリンタ「3800」をリリースしましたが、その初期モデルに搭載されていた書体はタイプライター由来の字幅固定のものばかりでした。ちなみに一般家庭用冷蔵庫を5個並べたほどの大きさで解像度は240dpiという代物です。これのバージョンアップ機「3800-3」をリリースするにあたりIBMは字幅がプロポーショナルであるTimes New RomanとHelveticaの二書体を搭載するためMonotypeに接触します。Helveticaを所有していなかったMonotypeは、IBMにHelveticaに替わるカスタム書体の製作を提案、これが許可されてArialプロジェクトがスタートしました。ちなみにHelveticaを持っていれば話は楽だったかというとそうではなく、どのみち3800-3用にビットマップデータを新規に書き起こすことになっていましたので、いずれにせよ書体の新規製作と同等の作業量は必要だったのです。これについては後編にて解説します(たぶん)。

こうして1982年に生まれた新しいサンセリフ体ArialはIBMのプリンタではSonoran Sans Serifという名前で搭載されました。アリゾナ州のIBM Tusconの目の前にあるソノラ砂漠にちなんで付けられた名前です*¹。Times New RomanはSonoran Serif、他にも搭載されたプロポーショナル書体はどれもSonoranで始まる名前です(このプロジェクトはMonotypeにとっては相当な儲け話であり、IBMに独自の名前を使わせるぐらいはあっさり認めたそうです)。その後にMonotypeは、同様のニーズを持つ顧客にHelveticaの安価な代替書体という魅力をより明確にアピールするためにArialを完全にHelveticaと同じ幅に設定しました(1989年完成にPostScript版が完成)。これに乗った顧客の中で最も有名なのがMicrosoftです*²。1990年にWindows3.0にTrueTypeフォントとして搭載されたArialはその後OSの普及とともに爆発的に使用頻度を増していき、1996年にはコアフォント(インターネット用の標準フォントパック)に指定され、今ではVerdanaやGeorgiaなどとともにWebページ上でMacでもWindowsでも確実に表示できる書体の一つとなっています。

*¹ 以前Lucidaの回でSonranと記載していましたが、正しくはSonoranです。失礼致しました。
*² このことを例に「Helveticaのライセンス料をケチったからMicrosoftはArialを搭載した。Microsoftはタイポグラフィへの関心が薄い」といわれることが多いのですが、これは違います。最終的にはWindows用のArialの開発、ライセンスにMicrosoftが投じた予算は小国を賄えるほどだったそうです(それでもHelveticaで同じことをやるよりは安かったのかもしれませんが)。何にせよArialが現在かくも人気なのは偏にMicrosoftの手厚いサポートのおかげです。

» 身近な書体: Arial Toshi Omagari

gtokio:

世界初の業務用レーザープリンタ、IBMの3800。印刷スピードはそこそこ早かったとか。


レーザープリンタのための書体

さて、それではArialがいかに生まれたかを見ていきましょう。1975年にIBMは最初の業務用レーザープリンタ「3800」をリリースしましたが、その初期モデルに搭載されていた書体はタイプライター由来の字幅固定のものばかりでした。ちなみに一般家庭用冷蔵庫を5個並べたほどの大きさで解像度は240dpiという代物です。これのバージョンアップ機「3800-3」をリリースするにあたりIBMは字幅がプロポーショナルであるTimes New RomanとHelveticaの二書体を搭載するためMonotypeに接触します。Helveticaを所有していなかったMonotypeは、IBMにHelveticaに替わるカスタム書体の製作を提案、これが許可されてArialプロジェクトがスタートしました。ちなみにHelveticaを持っていれば話は楽だったかというとそうではなく、どのみち3800-3用にビットマップデータを新規に書き起こすことになっていましたので、いずれにせよ書体の新規製作と同等の作業量は必要だったのです。これについては後編にて解説します(たぶん)。

こうして1982年に生まれた新しいサンセリフ体ArialはIBMのプリンタではSonoran Sans Serifという名前で搭載されました。アリゾナ州のIBM Tusconの目の前にあるソノラ砂漠にちなんで付けられた名前です*¹。Times New RomanはSonoran Serif、他にも搭載されたプロポーショナル書体はどれもSonoranで始まる名前です(このプロジェクトはMonotypeにとっては相当な儲け話であり、IBMに独自の名前を使わせるぐらいはあっさり認めたそうです)。その後にMonotypeは、同様のニーズを持つ顧客にHelveticaの安価な代替書体という魅力をより明確にアピールするためにArialを完全にHelveticaと同じ幅に設定しました(1989年完成にPostScript版が完成)。これに乗った顧客の中で最も有名なのがMicrosoftです*²。1990年にWindows3.0にTrueTypeフォントとして搭載されたArialはその後OSの普及とともに爆発的に使用頻度を増していき、1996年にはコアフォント(インターネット用の標準フォントパック)に指定され、今ではVerdanaやGeorgiaなどとともにWebページ上でMacでもWindowsでも確実に表示できる書体の一つとなっています。

*¹ 以前Lucidaの回でSonranと記載していましたが、正しくはSonoranです。失礼致しました。
*² このことを例に「Helveticaのライセンス料をケチったからMicrosoftはArialを搭載した。Microsoftはタイポグラフィへの関心が薄い」といわれることが多いのですが、これは違います。最終的にはWindows用のArialの開発、ライセンスにMicrosoftが投じた予算は小国を賄えるほどだったそうです(それでもHelveticaで同じことをやるよりは安かったのかもしれませんが)。何にせよArialが現在かくも人気なのは偏にMicrosoftの手厚いサポートのおかげです。

» 身近な書体: Arial Toshi Omagari

(via voqn)

Reblogged from wizardblue