はじめに はじめまして。開発エンジニアのCarboxyです。 ラク スに新卒で入社して、今年で２年目になります。 今回は、新卒（≒エンジニア初心者）が、効率の良いプログラムを書けるようになるきっかけになればと思い、プログラムの計算量の求め方とその比較方法をソート アルゴリズム （選択ソート）を例に紹介します。 計算量とは ある問題を解くためにどのくらい計算が必要かどうか（どのくらい時間がかかるか） → アルゴリズム の性能評価に使用できる。 O(オーダー)記法を用いて示す。 ※計算量には時間計算量と空間計算量があるが、この記事では時間計算量の事を指す。 O(オーダ）記法 計算量の一般的な記述方法。大まかな時間計算量を表す。 例として、入力サイズ n の関数として表される時間計算量T(n)が で与えられる場合、オーダー記法では最も次数の高い項の係数を省いて となる。なぜこのように最も次数の高い項（主要項）の係数を省くような、漸近的な評価が使われるかというと、入力サイズ n が十分に大きい場合は、時間計算量は主要項にのみ依存するからである。 選択ソート 選択ソートを例に計算量を考える。 選択ソートは最も基本的なソート アルゴリズム の１つで、次のようなア イデア に基づきソートを行っていく。 1,入力データの中から最大のデータを見つける。 2,見つけた最大のデータをソートの対象から除外する。 3, 1と2 の操作を n - 1 回繰り返す。 ソースコード 入力サイズ n の配列 D[0]、D[1]、・・・、D[n-1] for (i=n-1; i>0; i=i-1) { max = D[0]; maxIndex = 0; for (j=1; j<=i; j=j+1) { if(D[j]>=max) { max = D[j]; maxIndex = j; } } swap(D[maxIndex],D[i]); } この アルゴリズム は、２重のfor文により構成されている。変数 n に依存する i , j の２重ループなのだからO(n^2)になることは安易に想像できるが、計算すると次のようになる。 外側のfor文の繰り返し実行回数は n - 1 回であり、内側のfor文は外側のfor文の変数 i に依存し、i 回の繰り返しとなっている。したがって、この アルゴリズム の計算量は、以下の式で表される。 計算量の比較 複雑になるため詳細は省略するが、その他のソート アルゴリズム の計算量を計算すると、例えば クイックソート の場合はO(n logn)になる。オーダー記法の漸近的な大小関係は以下のようになることから、選択ソートと クイックソート を比較すると クイックソート のほうが計算量が小さい事が 数値的に わかる。 まとめ オーダ記法によって漸近的な時間計算量を示すことができる。 プログラムを実行して時間を測定しなくとも、入力サイズ n に対してどの アルゴリズム が一番速いか数値的に比較できる。

はじめに はじめまして。開発エンジニアのwest-cです。 ラク スに新卒で入社し、今年で3年目になります。 ラク スでもエンジニアブログをはじめることになりました。 記念すべき1エントリ目を書くことになり光栄です。 本題 そんな1エントリ目のテーマですが、現在、私自身が新卒メンバーの育成を担当していることもあり、今年入社した新米エンジニアを対象にお話をしたいと思います。 大学や会社の研修でプログラムは学ぶかと思いますが、ログの見方・調査方法についてしっかり学んだことのある方は少ないのではないでしょうか。 個人で作成したプログラムであればエラーが発生したとき程度しか見ないログですが、お客様に提供するアプリケーションとなると話はちょっと変わってきます。 ログは、ユーザがとった行動の証跡（証拠）となることから、利用状況の把握から問題が発生した場合の原因特定まで非常に重要な役割を担います。 ログの形式はソフトウェアによって異なるためそれぞれの公式ドキュメントに譲るとして、ここでは ログ調査にあたり知っておくと便利な Linux コマンド を紹介したいと思います。 なお、今回は Apache のアクセスログ を例として説明を行います。 リアルタイムでログを監視したい $ tail -f access_log ファイルの末尾が更新されると自動的に追加分が表示されます。 例えば、検証環境にて画面遷移をした瞬間のログを確認したい場合などに重宝します。 長い スタックトレース を確認する場合は、予めEnterキーでいくつか改行を入れておくとログの切れ目が分かりやすくなり便利です。 ログをスクロールして表示したい $ less access_log 行数の長いファイルの場合、 cat でファイルの中身を見ようとすると画面に収まり切らず、目的のログに辿り着くのにひと苦労します。 そのようなときに less を利用すると、スクロールしながら閲覧することができます。 less コマンド内で利用できる操作のうち、個人的によく使うものは以下になります。 キーバインド 説明 b 1画面分上にスクロール スペース 1画面分下にスクロール g ファイル先頭に移動 G ファイル末尾に移動 /文字列 ファイル内を文字列で検索 n 次にヒットした検索文字列の行に移動 N 前にヒットした検索文字列の行に移動 F リアルタイムで監視（ tail -f と同様） q less コマンドを終了する 表示する行を絞り込みたい 以降は、以下のような アクセスログ を前提として説明を行います。 （GET or POST の前の数値はリク エス ト処理にかかった時間（単位：秒）、末尾の数値はレスポンスサイズと解釈してください） $ cat access_log 192.168.10.11 - - [10/Oct/2000:13:55:36 -0700] 1 "GET /index.php HTTP/1.0" 200 2326 192.168.10.11 - - [10/Oct/2000:13:55:36 -0700] 0 "GET /top.jpg HTTP/1.0" 200 310 192.168.20.8 - - [10/Oct/2000:13:56:01 -0700] 10 "POST /login.php HTTP/1.0" 200 1793 192.168.30.50 - - [10/Oct/2000:13:57:11 -0700] 5 "GET /mypage.php HTTP/1.0" 200 831 192.168.30.50 - - [10/Oct/2000:13:57:11 -0700] 0 "GET /room.png HTTP/1.0" 200 4530 特定の文字列が含まれる行のみを抽出したい場合は grep の出番です。 $ grep "login" access_log 192.168.20.8 - - [10/Oct/2000:13:56:01 -0700] 10 "POST /login.php HTTP/1.0" 200 1793 ファイルから「login」という文字列が含まれる行のみが抽出されました。 逆に「login」という文字列を含まない行を表示する場合は、 -v オプションを付けましょう。 $ grep -v "login" access_log 192.168.10.11 - - [10/Oct/2000:13:55:36 -0700] 1 "GET /index.php HTTP/1.0" 200 2326 192.168.10.11 - - [10/Oct/2000:13:55:36 -0700] 0 "GET /top.jpg HTTP/1.0" 200 310 192.168.30.50 - - [10/Oct/2000:13:57:11 -0700] 5 "GET /mypage.php HTTP/1.0" 200 831 192.168.30.50 - - [10/Oct/2000:13:57:11 -0700] 0 "GET /room.png HTTP/1.0" 200 4530 grep -E または egrep を利用すると、検索文字列に 正規表現 を利用することができます。 上記を組み合わせると、画像ファイル（ *.jpg , *.gif , *.png ）を除外したログを表示したい場合に、以下のように記述することができます。 $ egrep -v "\.(jpg|gif|png)" access_log 192.168.10.11 - - [10/Oct/2000:13:55:36 -0700] 1 "GET /index.php HTTP/1.0" 200 2326 192.168.20.8 - - [10/Oct/2000:13:56:01 -0700] 10 "POST /login.php HTTP/1.0" 200 1793 192.168.30.50 - - [10/Oct/2000:13:57:11 -0700] 5 "GET /mypage.php HTTP/1.0" 200 831 表示する列を絞り込みたい 例えば以下の3つの情報がログ調査に必要であるとします。 アクセス日時 リク エス トURL リク エス トにかかった時間 この3つ以外の情報は今回は必要の無いノイズ情報ですので、 awk で表示する列を絞り込みましょう。 awk で列を絞り込む場合、デフォルトでは空白（スペース）またはタブ単位で区切られます。 今回の例だと、4列目（アクセス日時）・6列目（リク エス トURL）・8列目（リク エス トにかかった時間）だけを表示したいことになります。 $ awk '{print $4,$6,$8}' access_log [10/Oct/2000:13:55:36 1 /index.php [10/Oct/2000:13:55:36 0 /top.jpg [10/Oct/2000:13:56:01 10 /login.php [10/Oct/2000:13:57:11 5 /mypage.php [10/Oct/2000:13:57:11 0 /room.png 必要な情報のみが表示され、見通しが良くなりました。 $ の後の数字には、区切り文字で行を分割した際の順番が入ります（1始まり）。 区切り文字を変更したい場合は、 -F '区切り文字' とオプションを付与すれば良いです。 ちなみに cut コマンドでも同様のことは実現できますが、次に紹介する話との関連で、ログの確認時には awk を利用することをおすすめします。 条件に合致するログのみを抽出したい ひとつ前の例に追加して「リク エス トに3秒以上かかったログのみを抽出したい」場合を考えてみましょう。 awk は プログラミング言語 なので、条件分岐を記述することもできます。 $ awk '$6>=3{print $4,$6,$8}' access_log [10/Oct/2000:13:56:01 10 /login.php [10/Oct/2000:13:57:11 5 /mypage.php このように「○番目の項目が□□だった場合」と記述することができるため、単純な文字列一致の条件の場合でも grep よりも細かく絞り込みを行うことができます。 まとめ 私自身、入社したての頃にログファイルをviで開いて怒られたりログファイルを根こそぎ Excel に貼り付けてちまちま絞り込みを行ったりと苦い経験があったため、今回このテーマを選ぶことにしました。 今回取り上げた内容は基本的なものであり、さらに高度なログ集計を行おうとすると、 sort や uniq 、 sed なども必要になるかと思います。 まずはこの記事を足がかりに、その他のコマンドも習得してステップアップしてもらえると嬉しいです！ エンジニア 中途採用 サイト ラク スでは、エンジニア・デザイナーの 中途採用 を積極的に行っております！ ご興味ありましたら是非ご確認をお願いします。 https://career-recruit.rakus.co.jp/career_engineer/ カジュアル面談お申込みフォーム どの職種に応募すれば良いかわからないという方は、カジュアル面談も随時行っております。 以下フォームよりお申込みください。 rakus.hubspotpagebuilder.com ラク スDevelopers登録フォーム https://career-recruit.rakus.co.jp/career_engineer/form_rakusdev/ イベント情報 会社の雰囲気を知りたい方は、毎週開催しているイベントにご参加ください！ ◆TECH PLAY techplay.jp ◆connpass rakus.connpass.com