Subscribed unsubscribe Subscribe Subscribe

SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

両替の話.

本当にこれ動くのかと思いつつ動かしてみたら動いた。SICPの再帰手続きを使った両替の話。 50セント、25セント、10セント、5セント、1セントがあるとして、1ドルの両替にはどのくらいの場合があるか、という問い。再帰的手続きを用いて、下記のようなベース…

Udacity「Intro to Theoretical Computer Science」を修了した.

エンジニアとしてキャリアをスタートさせて3年半が経つが、コンピュータサイエンスの理論をしっかり学ばないと今後辛くなっていくな、という勝手な思い込みがあった。特に自分は文系出身なのでその思いは強く、今年に入ってからSICPを始めとしてコンピュータ…

複雑なプログラムは納得するものではない.

プログラムを書くようになってから数年経つが、初心者でひたすらいろんなコードを真似て書いていた頃に一番感動的だったものは再帰処理だった。関数自身がその関数を呼び出す、入れ子のような処理なのだが、初めてこれを組んだ時は頭の中で想像出来ない無数…

NP完全性について.

NP完全性について勉強したのでまとめる。今回は妙にコンピュータサイエンスちっくな話。 TL;DR まず全ての問題に効率的なアルゴリズムが存在するとは限らない。指数関数的に膨大な計算量を必要とする問題も存在する。ざっくりと効率性という観点から問題を二…

Tips RSA, 合同式の逆元を求める.

僕は暗号化あたりのアルゴリズムが好きなんだけれど、RSAの合同式の逆元の求め方ってなんだっけ?と年始早々ど忘れしたので改めて勉強し直そうと思う。 合同式(モジュラー算術、時計算術とも言う)とは以下の定義のものを指す。 二つの整数aとbにおいて、そ…

NativeとRussian Peasantsの処理速度の差。

アルゴリズムで全然処理速度違ってくるよ、という基本的な話。 乗算演算のNative AlgorithmとRussian Peasants Algorithmで処理速度の差を見ていく。 Native Algorithm 一番シンプルな掛け算。xの数分yの値を足していく。 def native(a, b): x = a; y = b z …

差分統計処理のための平均計算。

データを定期的に収集して統計計算を行うシステムを書いている際に、差分処理を行いたい場合がある。データはどんどん蓄積されていき、インプットとなるデータが巨大となった時、処理速度はそれに比例して遅くなってしまうためである。そういった時は逐次計…