この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の20日目 の記事です。
どうもこんにちは。k.u.です。
本日と明日の2日間にかけて、Union Find Treeの紹介をさせていただきます。
Union Find Treeは、互いに素な集合を効率的に扱うことの出来るデータ構造で、
が、とても少ない計算量で出来ます。まぁ要するにグループ分けが効率良く出来るという代物です。
しかし、集合を木構造で扱うため、グラフ理論をかじっていない場合には少々勝手が難しいかと思います。 私の文章により、アルゴリズムやデータ構造に少しでも興味を持っていただけると幸いです。
というわけで早速、Union Find Treeにまつわる物語を紹介いたします。 最後までお付き合いいただけると幸いです。
続きを読むこの投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の15日目 の記事です。
こんにちはabeです。 今回のお話は、「クラーメルの公式がやばい」という一言に集約されます。
クラーメルの公式とは、一言で言えば連立方程式の解をシンプルに表す式で、 係数行列を、 定数項をとした場合、 ベクトルで表される解の第成分をとすると、
となります。これが、クラーメルの公式です、なお、は、「の第列をで置き換えたもの」、という意味です。
前回登場した連立方程式:
も
とすることで解けて、
となります。
何年も前にこの公式を教科書で見た時には、「連立方程式の解が一行で書けてる！超便利！」と思いました(解の存在と性質だけ確かめる時には実際に便利です。)。
で今頃になってjavaで実装してみたのですが、これが超やばい！前回紹介したガウスの消去法なら2/1000秒程度の時間で解けた問題を解くのに2秒弱かかりました。
主な原因はまあ、今まで説明を完全に省略していたの計算で、ここでも詳細は省略しますが、まず「未知変数と同じ数だけ用意した数字の全ての並べかえの数」だけ処理を回し、そのループの一つ一つの中で、「未知変数の数と同じ数の掛け算」を行う必要があります。ここからはjavaのコードでお見せしましょう。
public double getDeterminant(){ double determinant = 0; for(Permutation permutation:this.allPermutations){ determinant += permutation.getSigunature()*this.getElementProductBy(permutation); } return determinant; } private double getElementProductBy(Permutation permutation){ double product = 1; for(int row = 0; row < this.size(); row++){ product *=elements[row][permutation.getValue(row)]; } return product; }
例えば先ほどのを求める方程式では、未知の変数がこの3つですので、「未知変数と同じ数だけ用意した数字の全ての並べかえの数」は6つになります。それは、ここでいう、this.allPermutationsが[[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]なる配列となって反映されます(詳細は上のgitHubのコミット)。そして、double型の二重配列であるelementsに関して、elements[row][permutation[row]]をrow=0,1,2 に関して掛け算する・・・という流れになります。
変数3つであればあまり問題にならないのですが、9個まで増えると大変で、permutationは362 880通りになります。これにより、ガウスの消去法の1000倍もの時間がかかる機能が出来上がってしまいました。
この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の9日目 の記事です。
こんにちはabeです。 今回はLU分解を用いた連立方程式の解法とその応用・効力について書いていきます。
/** * 行列をLU分解する。Lを返し、this.coefficientMatrixがUとなる。 * * @return */ public SquareMatrix splitLU(){ double[][] lowerTriangleMatrix = new double[this.values.length][this.values.length]; //Lを求めるときはいいが、Lの逆行列を求める場合はこのロジックは使えないことに注意 for(int columnNumber = 0; columnNumber < this.values.length; columnNumber++){ double[] FrobeniusColumn = this.eliminateOnTheColumn(columnNumber); for(int rowCoordinate = 0; rowCoordinate < this.values.length; rowCoordinate++){ lowerTriangleMatrix[rowCoordinate][columnNumber] = FrobeniusColumn[rowCoordinate]; } } return new SquareMatrix(lowerTriangleMatrix); }
早速ですが次の、右辺だけやたらと字が汚い連立方程式を解いてくれと頼まれた場合を考えてみましょう。
この連立方程式は、(都合よく絶対値の大きな係数が斜めに並んでいるため)行列に書き換えてガウスの消去法で容易に解くことができます。
行列の左下の方にある数字を0にするために、中段に上段の2倍を足し、下段から上段の3倍を引きます。
次に、下段に中段の値を足します。
このまでくればがすぐにわかり、さらにからがわかり、さらにさらにからとなり、方程式が解けました。
あるいはLU分解を用いても同程度の手間で解くことができます。 先ほどの式変形を具体的に計算する前に行列で表してみます、
細かい説明は省きますが、今回新しく出てきた行列のが、先ほどの「中段に上段の2倍を足し」の部分を表し、は「下段から上段の3倍を引き」のことで、は、「下段に中段の値を足し」の言い換えとなっています。残りのは、元の数字を保持するためのパーツです。左辺は普通に計算すれば先ほどと同じであるため、
ここで、式を二つに分けて、
また、ここでは詳しく説明しませんがフロベニウス行列の性質を用いて、
と変形できます。 連立方程式が1問から2問に増えて、一見遠回りのようですが、下の式からはであることがすぐにわかり、上の式に代入して先ほどと同じ解が出ます。
さて、この解答を見せたに行ったところ、前提が違うから解き直してくれと言われてしまいました。右辺の一番上は6でなく0で、さらに二番目は1じゃなくて7だそうです。読めるかー！
ということで解きなおすことになるのですが、単純な消去法では左辺と右辺の式変形を同時に行わなければならなかったため、右辺の原型が早い段階で分からなくなります。これに対し、LU分解を用いた解法では途中まで右辺が原型を保っているため、そこで数字を入れなおすことでやり直すことができます。
ここから、であることがわかり、がいえます。
皆さんも学生時代に散々味わったと思いますが、連立方程式を解く際に苦労するのは係数の消去の部分です。専門家によるとこれには未知変数の数の3乗に比例するコストがかかる(つまり、未知変数が3つの連立方程式を解く手間は未知変数2つのそれの2倍以上である)そうです。これを乗り越えた後の部分の手間は2乗に比例ですので、係数の消去をスキップすることは大きなアドバンテージとなります。
ではそのようなアドバンテージを得る機会はどのようなところにあるのでしょうか。「出題者の字が汚いとき」は冗談として、熱に関する分析にヒントがあるんじゃないかと考えました。
金属の棒の片方を水につけてもう片方を火で焙る、あるいは、細長い部屋の端っこにストーブが置いてあってその近くは暑いが反対側は寒い、といった状況を想像してみてください。これからそれをモデル化します。
まず時間0の領域の様子がこれ。数字は一本の棒の温度を表していて、時間とともに変化します。時間が1進むたびに両隣の点に均等に「温度」が分かれます。各点が両隣から温度を受け取ると言ってもいいかもしれません。
これを数式に起こすと色々面白いことができるんですが、あまりLU分解の旨味がないということでまたの機会に。
その代わりに、一定時間後に欲しい温度分布を得るために必要な現在の温度分布を求めるプログラムを作成しましたため公開します。しっかり、連立方程式を解く回数が増えるごとに処理時間のアドバンテージが得られる作りになっています。
この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の8日目 の記事です。
フロントエンドの開発をしていると、リクエスト・レスポンスの中身を覗いたりすることが頻繁にあります。
綺麗なREST APIを設計してあればリクエスト単位でテスト出来るので苦はないんですが、
Webサービスで「入力画面」「確認画面」「完了画面」の様に遷移していく画面の検証をしていると、
「あれ、確認から完了に遷移する時にエラーになった。。入力画面から確認画面に遷移する時のパラメータどうしてたっけ…」という場面がしばしばあります。
ログファイルに出力していたとしてもわざわざ別画面でターミナルを開いて…なんて面倒ですよね。
そんな時に嬉しいChromeの機能の紹介です。
とてもニッチですね。
この投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の4日目 の記事です。
こんにちは、imamotoです。
突然ですが、皆さんGitの操作はGUI派ですか？それともコマンドライン派ですか？ 私はコマンドライン派です！
Subversionがメインだった頃はGUIのアプリケーションで操作をしていたのですが、 Gitに触れるようになってからはめっきりコマンドライン派になりました。
業務中もまるで魔法の呪文のようにgit add . git commit git push origin branch_nameとタイピングしています。
おそらく人と会話しながら余裕で打てるくらいには手に馴染んでいる愛すべきコマンド達です。
しかしふと振り返ってみると、私はこのコマンド達の本当の姿をきちんと知る努力をしてきてはいませんでした。
コミット間の差分をどのような形で保持し、どのようにコミットの履歴をたどり、どのように２つのブランチがマージされるのか。。
これらを知ることで、私はGitともっと仲良くなれるのではないかと考えました。
ということで、これからGitと仲良くなる旅に出ようと思います！
続きを読むこの投稿は インタープリズムはAdvent Calendarを愛しています。世界中のだれよりも。 Advent Calendar 2017の2日目 の記事です。
いきなりですが、
入力された値のバリデーションチェックや文字列を検索するときなど正規表現を使うことが良くあります。 私は正規表現を書いていると「これで欲しい値が全部とれているのかな」とか、「これって不要な値を正しく弾けているのか」と不安になることがよくありますが、みなさんはどうでしょうか？ 私を含め正規表現が不安な人のためにオススメのツールをいろいろ調べてみました！
続きを読む