@blog.justoneplanet.info

日々勉強

単一方向リストと双方向リスト(singly linked list and doubly linked list)

JavaScriptを使って連結リスト(単一方向リストと双方向リスト)を考える。

■一般的なリスト

以下の例を考える。

function Person(name){
    this.name = name;
}
function List(){
    this._ary = new Array();
}
List.prototype = {
    "push" : function(name){
        var person = new Person(name);
        this._ary.push(person);
        return person;
    },
    "insertAfter" : function(personRef, name){
        var person = new Person(name);
        var counter = this._ary.length;
        while(counter > 0 && this._ary[counter] != personRef){
            this._ary[counter] = this._ary[counter - 1];
            counter--;
        }
        this._ary[counter + 1] = person;
        return person;
    },
    "toString" : function(){
        var str = '';
        for(var i = 0; i < this._ary.length; i++){
            str += this._ary[i].name + ', ';
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

ここに新しいPersonインスタンスを配列の特定の位置に挿入する。

var list = new List();
var john = list.push('John');
var mike = list.push('Mike');
alert(list.toString());//[John, Mike]
var nick = list.insertAfter(john, 'Nick');
alert(list.toString());//[John, Nick, Mike]

■単一方向リスト

配列で特定の位置pに挿入した場合、p以降の要素を全て+1側にコピーする必要がある。これは配列が大きくなったとき、コピーのコストも比例して大きくなる事を意味する。そこで以下の単一方向リストを考える。

function Person(name, personRef){
    this.name = name;
    this.next = personRef;
}
function List(){
    this._size = 0;
    this._first = null;
    this._last  = null;
}
List.prototype = {
    "push" : function(name){
        var person;
        if(this._size === 0){
            person = new Person(name, null);
            this._first = person;
            this._last  = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, null);
            this._last.next = person;
            this._last = person;
            this._size++;
            return person;
        }
    },
    "insertAfter" : function(personRef, name){
        if(personRef === this._last){
            personRef.next = new Person(name, null);
            this._last = personRef.next;
            this._size++;
            return personRef.next;
        }
        else{
            personRef.next = new Person(name, personRef.next);
            this._size++;
            return personRef.next;
        }
    },
    "toString" : function(){
        var r1 = '';
        var str = '';
        r1 = this._first;
        while(r1 != null && r1 != r){
            str += r1.name + ', ';
            r1 = r1.next;
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

Personクラス(のインスタンス)に次の順序のPerson(クラスのインスタンスのリファレンス)を保持している事で結果的にリストが完成するというものである。

var list = new List();
var john = list.push('John');
var mike = list.push('Mike');
alert(list.toString());//[John, Mike]
var nick = list.insertAfter(john, 'Nick');
alert(list.toString());//[John, Nick, Mike]

挿入部分だけ操作すれば良いので計算コストが下がる。重要なポイントは以下の2点だ。

任意のPersonインスタンスの後に挿入する場合で、それがリストの最後だった場合

Personインスタンス(A)のプロパティnextに新しいPersonオブジェクト(B)を挿入する。その時、Personオブジェクト(B)のプロパティnextは何もないのでnullとなる。listの最後の要素を表す_lastを書き換えるのを忘れないように。

personRef.next = new Person(name, null);
this._last = personRef.next;

任意のPersonインスタンスの後に挿入する場合で、それがリストの最後ではない場合

最後ではない任意のPersonインスタンス(A)のプロパティnextに新しいPersonオブジェクト(B)を挿入する。その時、現在の(A)のプロパティnextをPersonオブジェクト(B)のプロパティnextに保持する。結果的にリストに挿入した事になる。

personRef.next = new Person(name, personRef.next);

参考

連結リスト

コンピュータプログラミングと設計におけるほとんどの選択と同様、あらゆる状況に適した方法は存在しない。連結リストというデータ構造も状況によってはうまく機能するが、別の状況には適さない。以下では、連結リスト構造に関するトレードオフについて説明する。一般に動的に変化するデータの集まりがあって、要素の追加・削除が頻繁に行われ、新たな要素を追加する位置が重要となる場合、連結リストが適しているといえる。

ふむふむ

配列はランダムアクセス性に優れており、連結リストがシーケンシャルアクセスを得意とするのと対照的である。片方向リストは一方向にしか辿れない。従って、ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向きである。シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。これは、キャッシュメモリの効果と参照の局所性によるものである。連結リストはキャッシュメモリからはほとんど何も恩恵を受けない。

ふぇー

ここで一つ前の要素を得るメソッドgetPrevを考える。

■通常のリスト

function Person(name){
    this.name = name;
}
function List(){
    this._ary = new Array();
}
List.prototype = {
    "push" : function(name){
        var person = new Person(name);
        this._ary.push(person);
        return person;
    },
    "insertAfter" : function(position, name){
        var person = new Person(name);
        for(var i = this._ary.length; i >position + 1; i--){
            this._ary[i] = this._ary[i - 1];
        }
        this._ary[position + 1] = person;
        return person;
    },
    "getPrev" : function(position){
        return this._ary[position -1];
    },
    "toString" : function(){
        var str = '';
        for(var i = 0; i < this._ary.length; i++){
            str += this._ary[i].name + ', ';
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}

■単一方向リスト

function Person(name, personRef){
    this.name = name;
    this.next = personRef;
}
function List(){
    this._size = 0;
    this._first = null;
    this._last  = null;
}
List.prototype = {
    "push" : function(name){
        var person;
        if(this._size === 0){
            person = new Person(name, null);
            this._first = person;
            this._last  = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, null);
            this._last.next = person;
            this._last = person;
            this._size++;
            return person;
        }
    },
    "insertAfter" : function(personRef, name){
        if(personRef === this._last){
            personRef.next = new Person(name, null);
            this._last = personRef.next;
            this._size++;
            return personRef.next;
        }
        else{
            personRef.next = new Person(name, personRef.next);
            this._size++;
            return personRef.next;
        }
    },
    "getPrev" : function(personRef){
        var r0 = null;
        var r1 = this._first;
        while(r1 != null){
            if(r1 == personRef){
                return r0;
            }
            r0 = r1;
            r1 = r1.next;
        }
        return null;
    },
    "toString" : function(){
        var r1 = '';
        var str = '';
        r1 = this._first;
        while(r1 != null && r1 != r){
            str += r1.name + ', ';
            r1 = r1.next;
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}
var list = new List();

getPrevの計算コストがO(n)に増えてしまった。これは単一方向リストが要素の前への参照を持たないためである。

■双方向リスト

前後の参照を保持することによりgetPrevの計算コストがO(1)に下がる。

function Person(name, personRefPrev, personRefNext){
    this.name = name;
    this.prev = personRefPrev;
    this.next = personRefNext;
}
function List(){
    this._size = 0;
    this._first = null;
    this._last  = null;
}
List.prototype = {
    "push" : function(name){
        var person;
        if(this._size === 0){
            person = new Person(name, null, null);
            this._first = person;
            this._last  = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, this._last, null);
            this._last.next = person;
            this._last = person;
            this._size++;
            return person;
        }
    },
    "insertAfter" : function(personRef, name){
        var person;
        if(personRef === this._last){
            person = new Person(name, this._last, null);
            personRef.next = person;
            this._last = person;
            this._size++;
            return personRef.next;
        }
        else{
            person = new Person(name, personRef, personRef.next);
            personRef.next.prev = person;
            personRef.next = person;
            this._size++;
            return person;
        }
    },
    "insertBefore" : function(personRef, name){
        var person;
        if(personRef === this._first){
            person = new Person(name, null, this._first)
            personRef.prev = person;
            this._first = person;
            this._size++;
            return person;
        }
        else{
            person = new Person(name, personRef.prev, personRef);
            personRef.prev.next = person;
            personRef.prev = person;
            this._size++;
            return person;
        }
    },
    "getPrev" : function(personRef){
        return personRef.prev;
    },
    "getNext" : function(personRef){
        return personRef.next;
    },
    "toString" : function(){
        var r1 = '';
        var str = '';
        r1 = this._first;
        while(r1 != null && r1 != r){
            str += r1.name + ', ';
            r1 = r1.next;
        }
        str = '[' + str + ']';
        str = str.replace(/,\s\]/i, ']');
        return str;
    }
}
var list = new List();
var john = list.push('John');
var mike = list.push('Mike');
alert(list.toString());//[John, Mike]
var nick = list.insertAfter(john, 'Nick');
var jack = list.insertBefore(nick, 'Jack');
alert(list.toString());//[John, Jack, Nick, Mike]

microformat

検索のリッチ化が進む中、GoogleはRDFaとmicroformatに対応した。RDFaやmicroformatが埋め込まれたサイトでは検索結果が以下のように表示される。

リッチスニペット

■hCard(vCard)

人物に関する情報を記述する。

<div class="vcard">
<img class="photo" src="/wp-content/uploads/2009/12/1261861644_user_48.png" />
<p><strong class="fn">Mitsuaki Sample</strong></p>
<p><span class="org">Nutex Inc.</span>:<span class="title">Engineer</span></p>
<p><span class="adr">
<span class="postcode">141-0022</span><br />
<span class="region">東京都</span><span class="locality">品川区</span>
<span class="street-address">東五反田2-8-8</span><br />
</span></p>
</div>
name(fn) 名前
photo 写真
url URL
org 組織
title 役職
role 役割
adr 住所
>postcode 郵便番号
>region 都道府県
>locality 市町村
>street-address 番地

サンプル

Mitsuaki Sample

Nutex Inc.:Programmer

1410022
東京都品川区東五反田2-8-8

会社(組織情報)だと以下のようになる。

<div class="vcard">
<dt><span class="fn org">株式会社Nutex</span></dt>
<dd><span class="url">http://nutex.jp</span></dd>
<dd><span class="tel">03-5422-8684</span></dd>
<dd class="adr"><span class="postal-code">141-0022</span><br />
<span class="region">東京都</span><span class="locality">品川区</span><span class="street-address">東五反田2-8-8</span></dd>
</div>

サンプル

株式会社Nutex
http://nutex.jp
03-5422-8684
141-0022
東京都品川区東五反田2-8-8

■hReview

レビュー情報を記述する。

<div class="hreview">
<p><span class="item"><strong><span class="fn">NutexのCMS</span></strong></span> - Score:<strong><span class="rating">4.0</span></strong></p>
<p><span class="summary">凄く使いやすい。</span></p>
<p>written by <span class="reviewer">Mitsuaki Sample</span>(<span class="dtreviewed">2009-12-20</span>)</p>
</div>
item 対象アイテム
>name(fn) 名前
rating 評価点
reviewer 評価した人
dtreviewed 評価した日時
summary レビュー概要
description レビュー本文

サンプル

NutexのCMS – Score:4.0

凄く使いやすい。

written by Mitsuaki Sample(2009-12-20)

■hProduct

製品情報を記述する。

<div class="hproduct">
<h5><span class="fn">Rabit</span>(<span class="url">http://nutex.jp</span>)</h5>
<p><span class="price">\100</span></p>
<p class="ta-center"><span class="photo"><img src="http://blog.justoneplanet.info/wp-content/uploads/2009/12/1261863826_computer.png" alt="cms" width="128" height="128" /></span></p>
<p><span class="description">簡単CMS。</span></p>
<p>Brand: <span class="brand">Nutex</span> - Category: <span class="category">CMS</span></p>
</div>
name(fn) 製品名
price 値段
photo 製品写真
url 製品ページ
description 製品説明
brand ブランド
category カテゴリ

サンプル

Rabit(http://nutex.jp)

\100

cms

簡単CMS。

Brand: Nutex – Category: CMS

■応用

レビュー情報と製品情報を組み合わせる。

<div class="hreview">
<div class="item hproduct">
<h5><span class="fn">Rabit</span>(<span class="url">http://nutex.jp</span>)</h5>
<p><span class="price">\100</span></p>
<p class="ta-center"><span class="photo"><img src="http://blog.justoneplanet.info/wp-content/uploads/2009/12/1261863826_computer.png" alt="cms" width="128" height="128" /></span></p>
<p><span class="description">簡単CMS。</span></p>
<p>Brand: <span class="brand">Nutex</span> - Category: <span class="category">CMS</span></p>
</div>
<p><span class="summary">凄く使いやすい。</span> - Score:<strong><span class="rating">4.0</span></strong></p>
<p>written by <span class="reviewer">Mitsuaki Sample</span>(<span class="dtreviewed">2009-12-20</span>)</p>
</div>

サンプル

Rabit(http://nutex.jp)

\100

cms

簡単CMS。

Brand: Nutex – Category: CMS

凄く使いやすい。 – Score:4.0

written by Mitsuaki Sample(2009-12-20)

参考

チェックボックスの使い方

以下のコードよりも

<ul>
<li><input type="checkbox" name="check[]" value="1" />1</li>
<li><input type="checkbox" name="check[]" value="2" />2</li>
<li><input type="checkbox" name="check[]" value="3" />3</li>
<li><input type="checkbox" name="check[]" value="4" />4</li>
<li><input type="checkbox" name="check[]" value="5" />5</li>
</ul>
array(1) {
  ["check"]=>
  array(2) {
    [0]=>
    string(1) "2"
    [1]=>
    string(1) "4"
  }
}

以下のコードの方が

<ul>
<li><input type="checkbox" name="check[1]" value="1" />1</li>
<li><input type="checkbox" name="check[2]" value="1" />2</li>
<li><input type="checkbox" name="check[3]" value="1" />3</li>
<li><input type="checkbox" name="check[4]" value="1" />4</li>
<li><input type="checkbox" name="check[5]" value="1" />5</li>
</ul>
array(1) {
  ["check"]=>
  array(2) {
    [2]=>
    string(1) "1"
    [4]=>
    string(1) "1"
  }
}

なんか好きだ。

ちなみにvalue属性が無かったときは

<ul>
<li><input type="checkbox" name="check[1]" />1</li>
<li><input type="checkbox" name="check[2]" />2</li>
<li><input type="checkbox" name="check[3]" />3</li>
<li><input type="checkbox" name="check[4]" />4</li>
<li><input type="checkbox" name="check[5]" />5</li>
</ul>
array(1) {
  ["check"]=>
  array(2) {
    [2]=>
    string(2) "on"
    [4]=>
    string(2) "on"
  }
}

『on』という文字列が入る。(IE6~8,FF)

■参考

17.2 Controls

DBにバイナリで保存したjpegをファイルとして書き出すスクリプト

勿体ないので掲載。

$id = (int) $_GET['id'];
define('DB_HOST', 'localhost');
define('DB_USER', 'username');
define('DB_PASS', 'password');
define('DB_NAME', 'dbname');

$column = 'data';
$table = 'table';

$dbh = mysql_connect(DB_HOST, DB_USER, DB_PASS);
mysql_select_db(DB_NAME, $dbh);
$result = mysql_query("SELECT `{$column}` FROM `{$table}` WHERE `id` = '{$id}'", $dbh);
$row = mysql_fetch_array($result);

header("Content-type: image/jpeg");
print($row[0]);

以上。

PHPとGDで画像を指定サイズに丸める

イメージの縦横の長い方を指定のサイズにし、はみ出した部分はサンプリングしない感じだ。また、容量に制限を設け10KB以内になるように処理した。

$width         = 240;
$height        = 320;
$filename      = '0008.jpg';
$max_file_size = 10 * 1024;
$bg_quality    = 90;
$size       = getimagesize($filename);
$img        = imagecreatefromjpeg($filename);
$resizedImg = imagecreatetruecolor($width, $height);
if($size[1] < $size[0] * ($height / $width)){//horizontal
    $imageWidth = (int) (($height / $size[1]) * $size[0]);
    imagecopyresampled(
        $resizedImg,
        $img,
        0, 0,
        ($size[0] - ($width / $height * $size[1])) / 2, 0,
        $imageWidth, $height,
        $size[0], $size[1]
    );
}
else{//vertical
    $imageHeight = (int) (($width / $size[0]) * $size[1]);
    imagecopyresampled(
        $resizedImg,
        $img,
        0, 0,
        0, ($size[1] - ($height / $width * $size[0])) / 2,
        $width, $imageHeight,
        $size[0],
        $size[1]
    );
}
$counter = 0;
while(true){
    imagejpeg($resizedImg, $filename, $bg_quality - (10 * $counter));
    clearstatcache();
    $counter++;
    if(filesize($filename) < $max_file_size || $counter > 9){
        break;
    }
}

JavaScriptで挿入ソート

挿入ソートとは、配列Aのx番目の追加要素aをxから先頭に向かって比較し、挿入位置を特定する方法。

■実装

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}
console.log(a);
ary = a.concat();

// sort
for(var i = 1; i < ary.length; i++){
    var val = ary[i];
    for(var i2 = i - 1; i2 >= 0; i2--){
        if(ary[i2] > val){
            ary[i2 + 1] = ary[i2];
        }
        else{
            break;
        }
    }
    ary[i2 + 1] = val;
}

console.log(ary);

■特性

  • 最初から集団がほぼ整列しているような場合に適している
  • ランダムなデータに対しては効率が悪い
  • 計算量が最小となるのは集団が完全に整列していた場合でO(n)である
  • 計算量が最大となるのは集団が完全に逆順だった場合でO(n ^ 2)である
  • 平均時性能はO(n ^ 2)である。

Pythonで内部エンコーディングを指定する

■コード

先頭に以下の記述をする。

# -*- coding: utf-8 -*-
import sys
reload(sys)
sys.setdefaultencoding('UTF-8')

エラー

以下のようにreloadしないとエラーになる。

# -*- coding: utf-8 -*-
import sys
sys.setdefaultencoding('UTF-8')
"""
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
AttributeError: 'module' object has no attribute 'setdefaultencoding'
"""

ちなみにPHPだと以下のようになる。

mb_internal_encoding('utf-8');

■入出力の文字コード

標準入出力の文字コードだって指定したい。

import sys
import codecs

sys.stdin  = codecs.getreader('utf_8')(sys.stdin)
sys.stdout = codecs.getwriter('utf_8')(sys.stdout)

まぁ、コンナ感じ。

■ファイル

あとはファイルの文字コードがあるね。

import codecs

fin  = codecs.open('hoge.txt', 'r', 'utf_8')
fout = codecs.open('fuga.txt', 'w', 'utf_8')

PHPだとmb_convert_encodingだよね。

■結論

日本語ってめんどい。。。゜(´□`。)°゜

Compositeパターン

Composite(コンポジット・パターン)を使うと木構造のような再帰的なパターンを表現することができる。

■コード

Component.php

abstract class Component
{
    abstract public function add(Component $branch);
}

Branch.php

枝のクラス。

class Branch extends Component
{
    private $_children;
    public function __construct()
    {
        $this->_children = array();
    }
    public function add(Component $branch)
    {
        return array_push($this->_children, $branch);
    }
}

Leaf.php

葉っぱ。

class Leaf extends Component
{
    public function add(Component $branch)
    {
        throw new Exception('leaves cannot have any leaves');
    }
}

■クライアントコード

$branch = new Branch();
$branch->add(new Leaf());
$branch->add(new Leaf());
$branch->add(new Leaf());

var_dump($branch);
/*
object(Branch)[1]
  private '_children' => 
    array
      0 => 
        object(Leaf)[2]
      1 => 
        object(Leaf)[3]
      2 => 
        object(Leaf)[4]
 */

Interpreter Pattern

言語の文法

<Job> ::= begin <CommandList>
<CommandList> ::= <Command>* end
<Command> ::= diskspace | date | line
interface Command {
    public function execute(Context $context);
}

JobCommand.php

<Job> ::= begin <CommandList>
class JobCommand implements Command {
    public function execute(Context $context) {
        if($context->getCurrentCommand() !== 'begin') {
            throw new RuntimeException();
        }
        $commandList = new CommandListCommand();
        $commandList->execute($context->next);
    }
}

CommandListCommand.php

<CommandList> ::= <Command>* end
class CommandListCommand implements Command {
    public function execute(Context $context) {
        while(true) {
            $currentCommand = $context->getCurrentCommand();
            if(is_null($currentCommand)) {
                throw new RuntimeException();
            }
            else if($currentCommand === 'end') {
                break;
            }
            else {
                $command = new CommandCommand();
                $command->execute($context);
            }
        }
        $context->next();
    }
}

CommandCommand.php

<Command> ::= diskspace | date | line
class CommandCommand implements Command {
    public function execute(Context $context) {
        $currentCommand = $context->getCurrentCommand();
        if($currentCommand === 'diskspace') {
            // 空き容量を計算して出力
        }
        else if($currentCommand === 'date') {
            // 日付出力
        }
        else if($currentCommand === 'line') {
            // 罫線を出力
        }
        else {
            new RuntimeException();
        }
    }
}

Context.php

class Context {
    private $commands;
    private $currentIndex = 0;
    private $maxIndex = 0;
    public function __construct($command) {
        $this->commands = split(' +', trim($command));
        $this->maxIndex = count($this->commands);
    }
    public function next() {
        $this->currentIndex++;
        return $this;        
    }
    public function getCurrentCommand() {
        if(!array_key_exists($this->currentIndex, $this->commands)) {
            return null;
        }
        return trim($this->commands[$this->currentIndex]);
    }
}

■クライアントコード

$job = new JobCommand();
$job->execute(new Context('begin date line diskspace end'));