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

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

eps形式のファイルをpdf形式に

ps2pdfを使う

変換にはps2pdfコマンドを使用するらしい。

$ ps2pdf [input file] [output file]

これでpdf形式に変換出来るが，キャンバスサイズの大きいepsイメージだと画像が切れてしまう。

しかも用紙の形式（a4かな？）になるから謎の余白が出来てしまう。

これを回避するために，epsファイルのBounding Boxに合わせてファイル生成するオプションを加えるのだとか。

$ ps2pdf -dEPSCrop [input file] [output file]

これで元のeps形式のイメージがpdf形式になって綺麗に出力される。

追記

pstopdfコマンドというのもあるらしく，これを使うとBounding Boxのサイズそのままで出力されるらしい。

試しに使ってみたが，綺麗に出力されていた。

しかし，変換後ファイルサイズが大きすぎる...。

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

探索

  • 多くのデータの中から目的のデータを見つけること

線形探索法（Linear search）

  • 配列の先頭から順番に探索を行う
  • 平均時間計算量は

二分木探索法

  • 配列の中身がソートされていることが前提条件
  • 配列の真ん中の値（mid）が目的の値（x）と一致しているか調べる。一致しているのなら出力して処理終了
  • mid < xなら探索する範囲を配列の後半部分に、mid > xなら探索する範囲を配列の前半部分にし、再度処理1を行う
  • 処理1, 2を繰り返し行った結果、探索する範囲の配列長が1以下になったら配列の中にxは存在していないので、処理終了
  • 平均時間計算量はO(log(n))

ハッシュ法

データの格納方法

  • ハッシュ関数を用いて目的のデータの格納場所を決定する
  • ハッシュ化した値が重複した場合は、ハッシュ化した値に1を加えた場所に格納するなどの処理を行う

データの探索

  • データの格納方法同様、ハッシュ関数を用いて目的のデータの探索場所を決定する
  • 探索場所に目的の値がない場合はハッシュ化した値に1を加えるなどの処理を行い、再度探索を行う
  • 最良時間計算量はO(1)、最悪時間計算量はO(n)
  • データの個数がn個、配列長がmのとき、平均時間計算量はO(m/(m-n))、基本的にはO(1)になる

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

木

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

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! 
}

用語

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

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

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

「どうぞ」は丁寧な依頼

「どうか」は強い依頼

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

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

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