Monthly Archives: 11月 2013

あっ、急に素数が必要!でも大丈夫

日常生活で、急に大きな素数が必要になることってありますよね。
でもこれで安心!いつでもツイッターアカウントさえあれば、すぐに素数が手に入ります。

primenumber_profile

そうです。あなたは@primenumber_botにメンションを投げさえすればいいのです!

そしてこれが動作例:


例えばこんなときに:

  • RSA暗号の鍵ペアを手動で作りたくなったとき(公開でツイートするからセキュリティ筒抜けですけどね!)
  • おしゃれな自作Tシャツのデザインに
  • お守りに入れて魔除けに

クリスマスに素数のプレゼントはいかがですか?

以下解説

これは有名なMiller-Rabinのアルゴリズムというのを使っています。大きな数の素数判定でもわりと高速に計算できます。Miller-Rabinのアルゴリズムについては、ウィキペディアの解説がわかりやすいのでお勧めです。

ウィキペディア:ミラー-ラビン素数判定法

さらに詳細な解説、とくに計算量については、こちらの本をお薦めします。


Randomized Algorithms (Cambridge International Series on Parallel Computation)

なんでこんなものを作ったのかというと、理由は主に2つで、1)世の中素数萌えというジャンルの人たちが結構な数いる。2)Miller-Rabinアルゴリズムはほぼソラでかけるので、実装コストが低い(つまりツイッターボットのHello Worldをやったような感覚)。

ソースコードはこちらです(BSDライセンスにしておきました)
http://github.com/hamukazu/primenumber_bot

これを期に、素数芸人としての地位を確立していこうかと思う。

【論文紹介】 A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems

先日Gunosy新オフィスにて「RecSys2013論文読み会」というものに参加してきました。全体の様子はこちらで紹介していただいているので、ここでは私担当分の論文だけ簡単に解説したいと思います。

一応説明しておくと、RecSysというのは、レコメンデーションシステム(自動推薦システム)に関する国際会議で、毎年行われています。「RecSys2013論文読み会」というのは、その国際会議で今年発表された論文を各自選んで解説するものです。

紹介した論文はこちら:

Zuang et al., A Fast Parallel SGD for Matrix Factorization in Shared Memory Systems

ユーザによるレイティング(点数)の予想については、matrix factrization(行列積分解)という手法がよく知られていて、その開放としては確率的最急降下法(Stochastic Gradient Descent, SGD)というアルゴリズムが使わている。SGDによる解法では、ランダムにi,jの組を選んで、行列のi,j成分に注目してパラメータ(積分解したときの行列の要素)を動かすのだが、これを共有メモリを使って並列に計算するのを効率的にやるのがこの論文。

クラスタなどの分散環境については、既存のDSGDというアルゴリズムが知られている。これだと分散ということで通信量が少なくなるようにうまく工夫されているが、CPUの負荷のアンバランスが発生して、待ち状態が発生してしまう。そこでFPSGD(提案手法)ではDSGDを修正してロックフリーに動くようにしている。

DSGD:行列をs×s(sはノード数)のブロックに分割して、各スレッドに更新場所が重ならないようにブロックを割り当てる。更新箇所が重ならないという条件は、ちょうど将棋の飛車(チェスのrook)がお互いに取り合えないという配置。
FPSGD:行列をs×sより細かいブロック(つまりM×M, M>s, sはスレッド数)に分割して、開いているブロックの中から更新回数が少ないものをスレッドに割り当てる。

キャッシュヒット率を上げるため、ブロック内のアクセスはランダムにせずにシーケンシャルにし、しかしブロック選択をランダムにすることでランダム性を確保。

アルゴリズムの詳細は図解のほうがわかりやすいと思うので、上記スライド参照。

参加者の人たと色々とディスカッションしましたが、このような計算スピードを追求するような論文はRecSysでは珍しいようです。なのに(だからなのか?)この論文はベストペーパー賞受賞だそうです。

すべてのソフトウェア開発者にとって英語ができることが重要なのはなぜか

(Tumblrからの転載です)
(これはWhy knowing English is important for every software developerの翻訳です。)

まず、私はこのポストを英語で書くべきかロシア語で書くべきか迷った。ある考え方だと、これは十分に英語ができない人に向けた文章なのでロシア語で書くべきかとも思う。その一方、ロシア出身ではなく英語ネイティブでもない友人が私には沢山いるし、そういう人たちだって私がここに書く考えをながめることに興味があるだろうと思われる。そしてここでは後者の考えを採用することにした。このブログポストは、すべてのソフトウェア開発者にとって少なくとも中級レベルの英語ができることがとても重要だと私が考えるのはなぜかについてのものであり、非口頭のコミュニケーション(読み書き)と口頭のコミュニケーション(会話)を含めて述べている。

自分をやりくりする方法として

日常で英語を使わなくても全く問題ない人(ソフトウェア開発者)を私は沢山知っている。彼らは母語に翻訳された本(大抵は電子版ではなくて紙の本)を読み、地域化された(翻訳された)ソフトウェア(例えばロシア語版のWindowsやVisual StudioやSQL Serverなど)を使い国内のコンテンツアグリゲータやニュースポータルからニュースを読み、もし困ったときは国内のコミュニティ(地域化されたドキュメントやQ&Aサイトやフォーラムなど)に目を向ける。それは全く問題ないし、普段は完全にうまくいく。しかし、このことの短所も見てみることにしよう。

まず翻訳された本について考えてみよう。一番の問題点は、翻訳が市場に出回るまでに時間がかかることだ。私の友人の一人が最近Jon Skeetの「C# In Depth 第2版」翻訳を買ったが、私は(ほとんど同時期に)その第3版を買った。第2版の内容がもうすでにひどく時代おくれというつもりはない。しかし最近のテクノロジーの進化はとても早いので場合によっては紙の本を出版する意味すらないことがあるかもしれない。紙の本を出版していたのでは本が売り出される頃には変更や追加が沢山あって次の版を書き始めなければいけないかもしれないからだ。もうひとつの問題は、翻訳者が主題について十分な理解がないかもしれないし、新しい言語に知識を適切に投影できないかもしれないということだ(例えば、「C# In Depth 第2版」については翻訳の品質について多くの苦情を聞いている)。

次に地域化されたソフトウェアについて考えてみよう。翻訳された本を買う理由は理解できる一方、私が全く理解できないのはなぜソフトウェア開発者が専門的なソフトウェアの地域化されたバージョンをインストールするのかということ(例えば.NETエンジニアがロシア語版のVisual Studioを使うこと)だ。一番大きな問題は、地域化されたエラーメッセージしかないのだとしたら、特定のツールやフレームワークに関する問題(例えば.NETの変な例外や、プロジェクトのビルドの失敗など)の解決が困難になってしまうことはよくあることだ。オリジナルのドキュメントは常に地域化版より良くできているし、その上、Stack Overflowのようなサイトは大きく時間を節約してくれるし神経細胞の節約にもなる。

自分を表現する方法として

ここで重要なことを言う。英語で自分を表現する能力は、周りの人があなたの専門技能のレベルを判断する可能性に直接影響するということだ。このことは私自身が個人的に体験したことでもあるし、横で見ていて観察したことことでもある。私が以前いた会社では、遠隔地にいるウクライナ人のグループと一緒に仕事をしていた。Skypeでのミーティングは頻繁にあり、そこでは次のイテレーションの計画をしたり、現在抱えている問題についての議論などをしていた。そのウクライナ人の中にはまともに英語を話せる人はいなく、私の同僚が彼らとどのようにコミュニケーションをとってるか(ボイスチャットだけでなくメールでも)を私は知っていた。そのウクライナ人たちは、熟練したプロフェッショナルというよりは経験の浅い開発者のように扱われているように見えた(基本的なことがいつも確認され、リーダーやマネージャーによる厳しい管理が普通であったなど)。面白いことは、彼らには十分に能力があることがわかったことだ。彼らと私はロシア語で会話することができるので、彼らには十分な知識があって、今やっていることについて十分な経験があることがわかったのである。私の見解では、プロフェッショナルな開発者としての彼らの印象が悪くなったのは彼らの英語のせいだ。しかもこれは唯一の例ではなく、同じようなケースをたくさん見てきた。

ポール・グレアムが最近、人をYコンビネータに受け入れることができないときの理由について目立つことを言った。文字通り彼が言ったのは「悪いことを示す一つの資質は、CEOが強い外国語なまりであることだ」ということだ。彼の言ったことに反対する人もたくさんいる(彼の言ったことに人種差別的な匂いを見出す人すらいる)のだが、一般的には彼は正しいと思う。私が投資家だとしたら、なぜ自分のアイデアを少なくとも誰にでも理解できるように的確に説明できない人に信頼して自分のお金を預けることができるだろうか。英語がひどい開発者についても同じ論理を当てはめることができる。もし自分の考えを適切な専門用語を使って表現できなければ、だれもそんな人をアーキテクトやチームリーダーとして雇おうとはしないだろう。

いま何をするべきか

ここまでを読んできて自分のことを考えたなら、自分の英語を向上する必要があることがわかったと思う。ここでは何かを提案するするつもりはない。人によってうまくいく手法が違うと思うからだ。字幕付きの映画を見るのがいい人もいるし、授業を受けて先生から習ったほうがいい人もいる。もしネイティブな英語話者と話す機会が毎日(あるいは毎週、毎月)あるのならば素晴らしい、それはとても役に立つだろう。私は個人的には少しずつ英語のコンテンツに移っていった(地域化されたソフトウェアをアンインストールする、国内のニュースチャンネルからThe VergeTechCrunchHacker Newsなどに移るなど)。