Displaying posts written in

3月 2010

Python  | 2010 年 3 月 31 日 By | No comments yet

Pythonでリストのflatten・高階関数を使って

Python には組み込みの flatten がない。そこで次のように実装した。 

def traverse(f, x):
    if isinstance(x, (list, tuple)):
        for e in x:
            traverse(f, e)
    else:
        f(x)
 
def flatten(listOfList):
    arr = []
    traverse(arr.append, listOfList)
    return arr

「Python flatten」でググると様々な実装例が見つかるのだが、妙に凝った実装が多くて、こういうシンプルな実装はあまり見当たらなかった。

ただしこの実装は再帰を使っているので、ネストが深すぎるとオーバーフローする。 

x = []
for i in xrange(1000):
    x = [x, i]
print flatten(x)
# => RuntimeError: maximum recursion depth exceeded

オーバーフローを避けるには traverse をループを使って書き下す。Pythonでは末尾再帰の最適化は行われない。 

def traverse(f, x, isSeq = lambda y: isinstance(y, (list, tuple))):
    if not isSeq(x): return f(x)
    pos = depth = 0
    stack = { depth: [x, pos, len(x)] }
    while depth >= 0:
        lis, pos, size = stack[depth]
        if pos < size:
            stack[depth][1] = pos + 1
            if isSeq(lis[pos]):
                depth += 1
                stack[depth] = [lis[pos], 0, len(lis[pos])]
            else:
                f(lis[pos])
        else:
            depth -= 1

これで100000とかネストしても平気。 

x = []
for i in xrange(100000):
    x = [x, i]
print flatten(x)
# =>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
...省略...
, 99977, 99978, 99979, 99980, 99981, 99982, 99983, 99984, 99985, 99986, 99987, 99988, 
99989, 99990, 99991, 99992, 99993, 99994, 99995, 99996, 99997, 99998, 99999]
プログラミング  | 2010 年 3 月 5 日 By | No comments yet

PHP5.3の__callStaticをエミュレートする

PHP 5.3.0 ではマジックメソッド __callStatic が追加された。グローバルに使用されるユーティリティクラスで、動的にメソッド名を生成したいときに便利。 

class FooUtil {
  static protected $_inc = array('test1' => 1,
				 'test2' => 2);
 
  public static function __callStatic($method, $args) {
    return isset(static::$_inc[$method])
      ? static::$_inc[$method] + $args[0] : $args[0];
  }
}
echo FooUtil::test1(100); // => 101
echo FooUtil::test2(100); // => 102
echo FooUtil::testxxx(100); // => 100

同等の機能を PHP 5.2 より前の環境で再現したい場合、シングルトンパターンと __call を組み合わせるのが最も普通のやり方だと思う。 

class FooUtil2 {
  protected $_inc = array('test1' => 1,
			  'test2' => 2);
  static private $__singleton = null;
 
  public static function getInstance() {
    if(self::$__singleton === null) {
      self::$__singleton = new self;
    }
    return self::$__singleton;
  }
 
  public function __call($method, $args) {
    return isset($this->_inc[$method])
      ? $this->_inc[$method] + $args[0] : $args[0];
  }
}
echo FooUtil2::getInstance()->test1(100); // => 101
echo FooUtil2::getInstance()->test2(100); // => 102
echo FooUtil2::getInstance()->testxxx(100); // => 100

この方法の欠点は「呼び出し時のコードが長い」ことである。そこで個人的にはクラス名と同じ名前のグローバル関数を使う方法を提案したい。 

function FooUtil3() {
  static $singleton = null;
  if($singleton === null) {
    $singleton = new FooUtil3();
  }
  return $singleton;
}
 
class FooUtil3 {
  protected $_inc = array('test1' => 1,
			  'test2' => 2);
 
  public function __call($method, $args) {
    return isset($this->_inc[$method])
      ? $this->_inc[$method] + $args[0] : $args[0];
  }
}
echo FooUtil3()->test1(100); // => 101
echo FooUtil3()->test2(100); // => 102
echo FooUtil3()->testxxx(100); // => 100

この方法ならば __callStatic を使うのと比べて2文字長いだけだ。しかも他2つの方法よりもカプセル化の面では優れている。関数とクラスは「名前が同じ」というごく緩やかなつながりを持っているだけなので、静的な意味でも動的な意味でも、あとから自由に実装を切り替えられる。staticメソッドでなければならない、シングルトンでなければならない、といった制約はない。

これはグローバル変数や単純なレジストリ（CakePHPにおけるConfigureのような）を使うのとも違う。関数なので、どんな処理でも差し挟むことができる。関数の方がパラメータを持ってもいい。 

FooUtil4($context)->test($parameters);

グローバル関数というと問題になるのは名前の衝突だが、関数名とクラス名では名前の傾向が異なるので、クラス名が衝突しないのであれば同じ名前の関数も衝突しない可能性が高いと考えられる。

あまり公のプロジェクトで採用する気にはならないが、内々に使うにはそれなりに便利なテクニックだと思う。

CakePHP  | 2010 年 3 月 2 日 By | No comments yet

CakePHP 1.3RC1の新機能：プラグインdriver

せっかく私のpatchが採用されたので、ブログにも書いておきます。

CakePHP 1.3からはプラグイン内の DataSource が使えるようになりますが、1.3RC1からは DataSource の driver もプラグインから読み込めるようになりました。

たとえばGithubのCakePHP datasources pluginでは、Cakeコアに含まれない様々なデータベースに対するDboドライバが提供されていますが、RC1ではこれを次のようにして読み込むことができます。 

class DATABASE_CONFIG {
  var $sqlite3 = array('driver' => 'Datasources.DboSqlite3',
                       ...);
 
}

また driver を使用する DataSource をプラグインとして提供することも可能です。拙作のKeyValueSourceは次のように使用できます。 

class DATABASE_CONFIG {
  var $memcache = array('datasource' => 'KeyValueStore.KeyValueSource',
                        'driver' => 'KeyValueStore.KeyValueMemcache',
                        ...);
}

プラグインが読み込む driver を app/models/datasources 内に作ることもできます。たとえば memcache ドライバを拡張した my_memcache ドライバを作った場合、次のように読み込みます。 

// app/models/datasources/key_value/key_value_my_memcache.php
 
class DATABASE_CONFIG {
  var $memcache = array('datasource' => 'KeyValueStore.KeyValueSource',
                        'driver' => 'my_memcache',
                        ...);
}