けけずんセルフハッキング

エンジニアっぽい雰囲気を醸しだしているかのようなブログです！

情報工学レクチャーシリーズ：アルゴリズムとデータ構造 第三章「アルゴリズムにおける基本概念」

木

  • ”グラフと呼ばれる数学的抽象概念の特殊系” ← 難しいな
  • 木はノード（接点）とそれらを結ぶエッジ（辺）から構成される
  • ノードにはルート（根）と呼ばれる木の起点が一つだけ存在する
  • 子を持たないノードを リーフ（葉） と呼ぶ
  • リーフ以外のノードを内部節点と呼ぶ

k分木

  • 木の中のどのノードも子をk個以下しか持たないとき、その木を k分木 と呼ぶ
  • 全てのリーフのレベルが同じで、かつ全ての内部節点にk個の子を持つ場合、この木を 完全k分木 と呼ぶ

完全2分木

  • レベルがkの節点数は2^(k)
  • 高さをhとすると、リーフの数は2^(h-1)
  • リーフの数をmとすると1+log(m)
  • 高さをhとすると、ノードの数は2^(h)-1
  • ノードの数をnとするとlog(n+1)

再帰

Ruby on Rails の routing で使う match について

Rails4のルーティングの記述やら挙動がいまいちよくわからなかったので、ちょっと調べてみた。

ルーティングとは

  • config/routes.rbに記述する

  • URLから「どのコントローラー」の「どのアクション」に「どういうパラメータ」を与えて処理を実行するかを定義する

シンプルな例

「/tests/17 に HTTP GET すると、TestsController の hoge アクションを id=17 のパラメータで実行する」という設定。

# config/routes.rb
match "/tests/:id" => "tests#hoge", as: "tests", via: "get"

こっちは「/tests/17 に HTTP POST すると、TestsController の hoge アクションを id=17 のパラメータで実行する」という設定。

# config/routes.rb
match "/tests/:id" => "tests#show", as: "tests", via: "post"

上記のシンプル版

こっちが簡単で分かりやすい。

# config/routes.rb
get "/tests/:id" => "tests#show", as: "tests"
post "/tests/:id" => "tests#show", as: "tests"

Rails3の時のルーティング

:viaで HTTP METHOD を指定しなくてもデフォルトで HTTP GET になってたらしい。

# config/routes.rb
match "/tests/:id" => "tests#show", as: "tests"

なお、Rails4では指定してあげないと以下のようなエラーが出る。

You should not use the `match` method in your router without specifying an HTTP method.
If you want to expose your action to both GET and POST, add `via: [:get, :post]` option.
If you want to expose your action to GET, use `get` in the router:
  Instead of: match "controller#action"
  Do: get "controller#action"

情報工学レクチャーシリーズ：アルゴリズムとデータ構造 第二章「アルゴリズムの基本データ構造」

配列

  • メモリ上に連続した領域を確保する
  • データの追加・削除は先頭から走査する必要があるのでO(n)
  • 書き込み、読み込み共に O(1)
  • 配列は宣言時の長さから変更が出来ない = いわゆる静的配列

連結リスト

  • メモリ上に連続して領域を確保するわけではなく、必要に応じて確保する
  • {データ、次のレコードを指すポインタ}という構造の構造体と、リストの先頭を指すポインタから構成される
  • リスト先頭に対するデータの追加、削除はO(1)
  • 連結リスト内の要素の探索は時間がかかる
  • リストの構造上、使用するメモリ領域は配列よりも大きくなる

スタック

  • LIFO(Last In First Out)
  • 後から入れたものが先に出て行く構造
  • pushでデータの追加、popでデータの取り出しを行う
  • push, pop のどちらもO(1)

キュー

  • FIFO(First In First Out)
  • 先に入れた奴が先に出て行く構造
  • enqueueでデータの追加、dequeueでデータの取り出しを行う
  • enqueue, dequeueのどちらもO(1)

情報工学レクチャーシリーズ：アルゴリズムとデータ構造 第一章「アルゴリズムの基礎」

アルゴリズムとは

  • ある問題に対して、正しい解を得るための手順を定式化した形で表したもの

アルゴリズムの評価基準

  • 得られた解の質の良し悪し
  • 解を得るまでの計算時間・計算量

計算量の漸近的評価

  • 漸近的な時間計算量をオーダ記法を用いて表す
  • 漸近的な大小関係の参考：
{
\log{n} < n^{1/2} < n < n*\log{n} < n^{2} < n^{3} <...< 2^{n} < n! 
}

用語

  • 漸近的：徐々に近づくが、永遠の時間をかけても到達できない

「どうぞよろしく」と「どうかよろしく」

「どうぞ」と「どうか」の使い分けがよく分からなかったので、調べてみた。知恵袋などで質問が上がっていたのでそれを参照した。

「どうぞ」は丁寧な依頼

「どうか」は強い依頼

切羽詰って本当にお金を貸して欲しい時には、「どうぞお金を貸してください」ではなく、「どうかお金を貸してください」 　

丁寧なあいさつ という意図であれば、「どうぞよろしくお願いします」

ぜひよろしく という意図であれば、「どうかよろしくお願いします」

ログファイルをリアルタイムで監視するコマンド

出力されたログをリアルタイムで追っていく際に使用できる。 tail コマンドにオプション f を追加するだけ。

tail -f [file name]

たまに less だったか more だったかなってなるから書いておく。