頻出典型アルゴリズムの演習問題を解く

暇だから下を解いていく。
http://d.hatena.ne.jp/kyuridenamida/20111009/1318087144

C言語で動作確認したやつを書く問題の下に張っていきます。

二問目

終了条件とかは端折った。

整数の和 | Aizu Online Judge
答え

三問目

かなり力技

島の数 | Aizu Online Judge
答え

「次回から自動でログイン」の実装考察

ログインする必要があるWebサービスを構築する上でよく見る「次回から自動でログイン」の実装について考察してみようと思う。

クライアント側に記憶させる情報

次回からログインを省略するということは、クライアント側に何らかのユーザ情報を覚えさせておく必要があると思う。だから、Cookieを使うのは必須で、ここに何を登録するか?というのが一番重要だと思う。ユーザ情報を登録するんだから、以下の二つは必要

  • ユーザを識別できる情報(ユーザIDとか、ユーザ名とか)
  • それが本人と識別できる情報(パスワード)

ここで、重要になるのがパスワードだと思う。単純にログインするときに使用するパスワードを使ってしまうと、Cookieにパスワードをそのまま入れることと等しくなるので、これはセキュリティ上よろしくない。Cookieなんて見ようと思えば誰でも見れる場所であって、そこにパスワードを入れるなんてもってのほかだと思う。

じゃあ、どうするかって考えると、普通に思いつくのがワンタイムパスワードだと思う。Cookieからログイン処理を行うたびに新たなワンタイムパスワードを作成して、Cookieに新たに登録する。こうすることで、Cookieからログインした際のパケットを見られたとしても、ログイン後にすぐにそのパスワードは変更されてしまうため、セキュリティ上も問題ないと思う。万全を期すならユーザ情報すらもワンタイムとして作成すべきだと思うけど、パスワードのみの場合とあまり堅牢性は変わらないし別にそこまでやる必要も無いのかと思う。

情報を保持する期間

ずっとCookie上に保存し続けるのも僕としてはありなのかと思う。まず、CookieがあるPCからアクセスされたということは、本人であると考えて問題ないんじゃ無いかと思う。複数人が使うPC上で「次回から自動でログイン」にチェックを入れるということは、他の人からアクセスされても問題ないと思っていいんじゃないかな。ただし、大体は他の人にPCをさわらせる気は無かったけど、何らかの事情で他の人の手にPCが渡ってしまってアクセスされるってことも考えられるから、ベストは1週間から1ヶ月程度で消すのが一般的だと思う。Cookieを消すということは自動でログインすることが出来ないので、ユーザから見ると利便性は下がる。ここの期間は各サービスのログイン情報の重要性からケースバイケースで考えるべき点だと思う。

Cookieを消すタイミング

ログアウト処理を行ったときにCookieを消すか否か。これは結構悩ましい。ユーザはその時に使用する操作が完了したからログアウトを行っただけかもしれない。それなのに、Cookieを消してしまうとログイン処理を行わなくていいつもりだったユーザに対してログイン処理を行わせる必要性が出てくる。これはユーザは意図せぬ処理だからちょっとしたストレスになるかもしれない。

けど、ちょっと考えてみるとログアウト処理を行った際にCookieを消さないと、Cookieが削除される処理が行われるタイミングがTimeoutによる削除しか行われなくなってしまう。情報を保持するタイミングを無期限でよいと考えてしまった場合、そのPCからのアクセスはいつでも誰でもアクセスできてしまうことになる。これがよいかどうかは各ユーザによるといえばよるが、僕はアマリよろしくないと思う。なので、ログアウト処理を行った際にCookieは消すべきだと思う。まぁ、ユーザ操作でCookieを削除することは可能だからそこまで考える必要も無いのかもしれないけど。

実装

上記を踏まえて実装してみたとする。適当に書いてるから参考程度に・・・。

<?php

function logincheck() {
    /* ログイン情報はセション変数で管理しているものとする */
    $user_info = $_SESSION['login_info'];

    /* 値が入ってたらログイン中とする */
    if( !$user_info ) {

        /* Cookieからログイン情報を取得する */
        $login_info = $_COOKIE['login_info'];

       /* Cookieの値が入ってたら次回から自動でログインをチェックされたものと判断 */
       if( !$login_info ) {

           /* ワンタイムパスワードとIDからユーザ情報を取得 */
           $user_info = get_user_info($login_info);

           /* ワンタイムパスワードを作成 */
           $one_pass = md5( $user_info . rand() );

           /* あらたなCookieを登録 */
           setcookie("login_info", $user_info->id . "," . $one_pass);
       }
    }

    /* ユーザ情報返答してNULLなら未ログインとして処理 */
    return $user_info;
}

?>

感想

たぶんどこもこんな感じの考え方で実装してるんじゃないかな。これなら手軽にセキュアに成るのかと思う。突込みがある方はよろしくお願いします。

OpenIDとOAuthの違い

以下を読んでの雑感。もうちょっと簡単に書けると思う。

どういうサービス?

ウェブサービスで共通して使えるアカウントを提供するサービス。

利点

AというサイトでもBというサイトでもCというサイトでも新たにアカウントを作成することなくサービスを使うことが出来る。アカウントを一つに出来ることでパスワードの管理が煩雑にならずにならないし、アカウントを作る手間が省けて便利。

仕組み

アカウントを管理している認証を行うサイトが一つだけあって、それに対してA・B・Cっていうサイトが認証をしにいくって感じ。

OAuth

どういうサービス

Aっていうサイトが提供しているサービス内容をBっていうサイトでも使えるようにするサービス。説明するのに便利だからここからはTwitterを例に書いてみる。

利点

Twitterを例にとるとBっていうサイトから認証したアカウントに対してTwitterが提供しているサービス(タイムラインの取得だとか、つぶやきの投稿だとか)を使うことが出来る。

仕組み

Bっていうサイトに対してTwitterを更新したり出来る権限を与えているようなもの。Bは信頼できますよーっていうのをユーザがTwitterに対して保障する。

違い

OpenIDはユーザを管理していて、OAuthはサイトが提供しているサービスを管理している。僕の認識では似て非なるものって言うよりも全然違うもの。



まとめ

簡単に書いてみたけど、OAuthとOpenIDの違いは僕の中でこんなもん。
最近TwitterのOAuthを使ってユーザ管理をして簡単にウェブサービスをつくろうみたいなのがよくあるけど、Twitterのサービスを使わないのにOAuthをつかって認証しようとしてるとかいうサイトがもしあるんであれば使い方を間違ってると思うよ。

カンニングしちゃいけないっていう前提条件が無い

以下を読んでの雑感

どちらも読んでみたけど、調べれる力が必要でこれからそういう人が重要でしょ?みたいに読めてしまったんだけど、それって全然違うよね。テストの前提条件として「ネットを使って調べてよい」っていうものがあったんだったら、この子は頭がいいんだと思うよ。みんなが一生懸命解き方を調べてる間に、「知ってる人に聞く」っていう待ったく別の発想で問題の解決方法を導き出したんだから。

でも現実は違うよね。

テストの前提条件で持ち込んでいいものは無いんだよ。「僕のところは何でも持ち込んでよかったけど調べる時間なんて無かったよ。」とか、そういう話じゃなく前提としてなにも持ち込んじゃいけないんだよ。何かを計るときにはルールがあって、そのルールの中でどれだけできるか?っていう採点基準で計るんであって、その前提条件を崩してしまったら何も成り立たないと思うんだ。

例えば100メートル走とかでもさ。ドーピングしちゃいけなくて自分の体だけを使って走るっていう前提条件があるから勝負が成り立つわけよ。その前提条件を破っていいんだったら車とか使ったほうが絶対早いわけじゃない。カンニングが頭がいいって言うのは、その車を使った人を、「あいつはみんなが走ってるときに車を使うなんて頭いい。これからは自分では知る時代じゃないよね。」とか言ってるのと一緒だと思うんだ。

僕は何事も前提条件があるから力を計れるんだと思うんだ。同じ土俵でその人がどれだけの力を出せるかではかるべきで、別の土俵で勝負したらそもそも勝負が成り立たない。ま、どっちもいい材料が出たから調べるってことがこれから重要になるよね?っていうことを言いたいだけの釣り記事だと思うけど、まんまとつられてみました。

MySQLでSQLのみを使用してランダム取得を劇的に早くする方法

MySQLでランダムに20行をとるためには以下のようにやればいい。

SELECT * FROM table_name ORDER BY RAND() LIMIT 0, 20;

簡単に取得できるのはいいんだけど、行数が増えると劇的に遅い。どれくらい違うかって言うと10万行のデータベースでも↓ぐらい違う。

表示中の列 0 - 19 (20 合計, クエリの実行時間 0.0070 秒)
SELECT * FROM table_name LIMIT 0 , 20

表示中の列 0 - 19 (20 合計, クエリの実行時間 1.1884 秒)
SELECT * FROM table_name ORDER BY RAND() LIMIT 0, 20;

なんでこんなに時間がかかるのかと調べてみると、どうも*を使うから遅いらしい。ということで、列名に主キーを指定して試してみる。

表示中の列 0 - 19 (20 合計, クエリの実行時間 0.0745 秒)
SELECT table_id FROM table_name ORDER BY RAND() LIMIT 0, 20;

確かに劇的に早くなってる。それならこれでサブクエリを作成して引っ掛ければ早くなるのでは?と試してみた。

表示中の列 0 - 19 (20 合計, クエリの実行時間 0.0740 秒)
SELECT * FROM table_name AS tbl,
  ( SELECT table_id FROM table_name ORDER BY RAND() LIMIT 0 , 20) AS randam
  WHERE tbl.table_id = randam.table_id LIMIT 0 , 20

これならRAND()を使用しない検索と同じくらいの速さになるみたい。主キーだからインデックスで早くなるのかなぁ。よくわかってないけど、RAND()を使う場合はサブクエリで取得してから使ったほうがいいみたいです。

PHPでHTML解析 - パート2

久しぶりに週末プログラミングをして、HTML解析をやろうとしたんだけど、自分の記事がGoogle先生のTOPに出てきてちょっとびっくり。前に書いたのよりももっといい方法が見つかったから備忘録がてら書いておきます。
以下のサイトが参考になる。

使い方

とりあえず、以下のサイトからモジュールをダウンロードして、includeする。それで、解析したいやつのHTMLファイルを指定してとってくるだけで、jQueryチックにかける。

  include('./inc/simple_html_dom.php');

  $html = file_get_html('http://yahoo.co.jp');

  // 子要素のテキストを取得
  $html->children(0)->plaintext;

  // IDで検索
  $html->find('#test_id')->plaintext;

  // 全てのクラスを取得
  foreach($html->find('.test_class') as $element){
    $element->children(0)->plaintext;
  }

  // titleをとってみる
  $html->find('title')->plaintext;

  // aのlink先をとってみる
  $html->find('a')->getAttribute('href');

すごい便利。使いそうな関数は以下の関数とかかな。

  • innertext
  • plaintext
  • getAttribute
感想

まえのより絶対こっちのほうが便利!

MacBook Air 11インチ欲しい!

今年は一年間、ウェブサービスを作る年にしようかと思ってる。

なんか色々自分の道を模索して考えた結果、とりあえず物を作るしかないかなーって結論になったし、エンジニアとしてこれから先ウェブサービスって避けて通れない道だと思ってるから、いままで作ってきたウェブサービスより少しでもいいものを作っていけたらいきたい。

とりあえず目標は月1個のウェブサービスを作ることかなー。

なんかウェブを触る上ではMacがいいって話しだし、Macのノートパソコンがほしかったところでちょうどいいキャンペーンが。

ってことで、『MacBook Air 11インチ欲しい!

あたるといいなー。