2009/11/22

Lisp備忘録 リストを利用したその他の形式

ツリー構造
リストの各コンスセルの中にリストを押し込んでいけばいい

CL-USER> (list (list 1 2) (list 3 4) (list 5 6))
((1 2) (3 4) (5 6))

ツリーを丸ごとコピーするにはcopy-tree.
copy-listでは内部の(1 2)などのセルはコピーせずに参照になる.

集合
adjoinを使って作成できる.
adjoinは非破壊的関数なので,直接元の値を変更する場合はpushnewを使う.

CL-USER> (defvar *x* nil)
NIL
CL-USER> (setf *x* (adjoin 1 *x*))
(1)
CL-USER> (adjoin 1 *x*)
(1)
CL-USER> (pushnew 2 *x*)
(2 1)
CL-USER> *x*
(2 1)


集合操作関数
リストを一つだけとる関数
member - 集合にあるアイテムが含まれているかどうか.

リストを2つ引数に取る関数
intersection - 両方の集合に含まれている要素のリストを返す.
union - 2つのリストに含まれているユニークな値のリストを返す
set-differece - 最初のリストに含まれていて二つ目のリストには存在しないもののリストを返す.
set-exclusive-or - 両方のリストのどちらか一方にだけ存在している要素のリストを返す.
上記4つの関数は頭にNの付く破壊型関数がある.

連想リストと属性リスト
連想リストはassocを使用してアクセスできる.

CL-USER> (assoc 'a '((a 1) (b 2) (c 3)))
(A 1)


通常通りconsを使用して連想リストを作成できるがCommon Lispにはacons関数もある.
非破壊的関数なのでsetfやpushを利用して値を変更する.

CL-USER> (acons 'a 1 *x*)
((A . 1))


属性リストはキーと値が順にならんだリスト構造.
A,B,Cを1,2,3に対応させた属性リストは(A 1 B 2 C 3)といった構造になる.
getf関数でキーに対応した値を取り出せ,setfで値を変更できる.キーと値の両方を削除するにはremfを使用する.

destructuring-bind
マクロのパラメータリストを受け取る時と同様に任意のリストの構造を分配できる.

CL-USER> (destructuring-bind (x y z) (list 1 2 3)
(list :x x :y y :z z))
(:X 1 :Y 2 :Z 3)




2009/11/21

Lisp備忘録 リストについて

リストの基礎
consで作成されるコンスセルでリストは作られる.
コンスセルの前をcar部, 後ろをcdr部を呼び,同名の関数でコンスセルにアクセスできる.

CL-USER> (defvar *x* (cons 1 2))
*X*
CL-USER> (car *x*)
1
CL-USER> (cdr *x*)
2


コンスセルの中でcdr部が他のコンスセルやnilでないものを特別にドットペアと呼ぶ.

;ドットペア
CL-USER> (cons 1 2)
(1 . 2)
;リスト
CL-USER> (list 1 2)
(1 2)
CL-USER> (cons 1 nil)
;リスト
(1)
;(list 1 2)をconsで生成する
CL-USER> (cons 1 (cons 2 nil))
(1 2)


コンスセルをリストとして扱うときにはcar, cdrだけじゃなくfirst, restで扱おうと書いてある.
多分後でそのプログラムを見たときに何を扱っているのかが明確になるからだろうか.


破壊的,非破壊的
appendは最後に与えられた引数以外をコピーして新しいコンスセルを作り,最後の引数をそのコンスセルにくっつける.
最後の引数だけはappendが返すリストと最後の引数ので同じコンスセルを参照するようになる.

破壊的な関数の頭にはNがつくことが多い.
reverseとnreverse, appendとnconc

CL-USER> (defvar *x* (list 1 2 3 4))
(1 2 3 4)
CL-USER> *x*
(1 2 3 4)
CL-USER> (reverse *x*)
(4 3 2 1)
CL-USER> *x*
(1 2 3 4)
CL-USER> (nreverse *x*)
(4 3 2 1)
CL-USER> *x*
(4 3 2 1)


破壊的関数は引数を後で使うつもりがなければ使用してもいい.
たとえば関数内でのレキシカル変数など.

(defun upto (max)
(let ((result nil))
(dotime (i max)
(push i result))
(nreverse result)))

よく使われる組み合わせはsetf, deleteとpush, nreverse.

consp, listp, atom,null
この三つの区別がいまいちわからなかったのでまとめ.

conspはオブジェクトがコンスセルかどうか.
listpはオブジェクトがコンスセルかnilかどうか.
atomはオブジェクトがコンスセルではないかどうか.
nullはオブジェクトがnilかどうか.notと等価だが真偽の評価ではなく空リストのテストとしてはこちらを使うべきらしい

mapcar, maplist
mapcarはリスト専用なのでmapのように型を指定する必要がない.

2009/11/13

Lisp シーケンス操作関数の続き

シーケンス反復関数
count, find, position, remove, substituteがある
指定できるキーワードとしてeqlで比較されるが、testキーワードに2引数関数を渡すことで比較関数を変更できる
from-endキーワードで逆順に処理、keyに1引数関数を渡すこともできる。
start, endキーワードで開始位置や終了位置の変更が可能

それぞれの関数にsuffixとして"-if, -if-not"をつけたものがある。
remove-if-notはPerlのgrepと同様の処理になる
下記は#\fから始まる文字列を取得

* (remove-if-not #'(lambda (x) (char= (elt x 0) #\f)) #("foo" "bar"))

#("foo")


重複を取り除くremove-duplicatesもある

シーケンス全体を一度に扱う関数
concatenate, copy-seq reverse
concatenateは1引数目に作成するタイプを入れる

* (concatenate 'string "abc" '#(#\d #\e #\f))
"abcdef"

* (reverse #(1 2 3 4))
#(4 3 2 1)

* (defvar *x* nil)
*X*

* (setf *x* (copy-seq #(1 2 3)))
#(1 2 3)

* *x*
#(1 2 3)


ソートとマージ
sort, stable-sort, mergeがある
sortとstable-sortの違いは述語によって等価と判断された要素の順番がかわるかどうからしい。
sort, stable-sortは破壊的関数なので必ず返り値を使用すること
(sort シーケンス 述語)
(merge シーケンス1 シーケンス2 述語)

部分シーケンス操作
(subseq シーケンス 開始インデックス 終了インデックス)
Perlのsubstrと一緒

部分シーケンスを見つける関数
search

(position #\b "foobarbaz") → 3
(search "bar" "foobarbaz") → 3

二つのシーケンスから異なる部分を見つけるのに[I]mismatch[/I]が利用できる。
キーワードとしてstart1, end1, start2, end2を利用可能
[CODE]
* (mismatch "foobarbaz" "bar")
0
* (mismatch "foobarbaz" "foom")
3
* (mismatch "foobarbaz" "bar" :start1 6)
8


シーケンス述語
every, some, notany, notevery

* (setf *x* #(1 2 3 4 5))
#(1 2 3 4 5)
* (every #'evenp *x*)
NIL
* (some #'evenp *x*)
T
* (notany #'evenp *x*)
NIL
* (notevery #'evenp *x*)


マッピング関数
map, map-into, reduce
map-intoは第1引数のシーケンスに第2引数のシーケンスをセットする

Perlに比べるとすげー多い。
List:MoreUtilsを標準で組み込んだ感じ

ハッシュテーブル
make-hash-table, gethash,remhash, clrhash
gethashの返り値は多値なのでmultiple-bind-valueで多値を受け取れる

(defparameter *h* (make-hash-table))
(gethash 'foo *h*) → NIL
(setf (gethash 'foo *h*) 'quux)
(gethash 'foo *h*) → NIL
(multiple-bind-value (value present) (gethash 'foo *h*))

setfとgethashでキーにnilを設定すると値がnilになる
remhashでキーを削除できる。
clrhashですべてのキーと値を削除できる

2009/11/12

Lisp写経 2回目

ベクタの作成
vector, make-arrayで作成できる

(vector 1 2 3) → #(1 2 3)
(make-array 5 :initial-element 1 :fill-pointer 0) -> #(1 1 1 1 1)


vectorで作成したベクタはvector-pop, vector-pushで変更できない。
make-arrayに:fill-pointerオプションを指定するとvector-pop, vector-pushで要素の変更が可能なベクタを作成できる。
#(1 2 3)とリテラル表記でもベクタは作成できるが、リテラルオブジェクトを変更した場合の処理は定義されてないので変更すべきではないらしい。

可変サイズのベクタを作成するにはmake-arrayで:adjustable tを追加する。
vector-push-extendを使用する。vector-pushと違い要素が一杯の場合は自動的に領域を拡張する

fill-pointerが設定されていなくてもeltで要素を指定してsetfすることができる

(defvar *x* #(1 2 3))
(setf (elt *x* 1) 20) → #(1 20 3)



EmacsだからなのかSlime環境だからかはわからないが、ミニバッファに関数の取れる引数が表示されることに今ごろ気づいた
こんな感じ

(make-array arg0 &key adjustable element-type initial-element initial-contents
fill-pointer displaced-to displaced-index-offset)

2009/11/11

Lisp写経 文字と数字の関数

文字
スペース等の特殊な文字の入力

#\Space


どんなものがあるかリスト
  • Space
  • Newline
  • Tab
  • Page
  • Return
  • Linefeed
  • Backspace


数字
incf, decf

(incf x) ≡ (setf x (1+ x)) ≡ (setf x (+ x 1))


続きは後で書く

Lispの今日の写経

Emacs+SlimeのCheetSheetを発見
http://www.pchristensen.com/blog/articles/public-beta-open-for-ultimate-n00b-slimeemacs-cheat-sheet/

やっとEmacsのコピペのやり方覚えた
C-@でマークセットして、M-wで範囲コピーできる
一行だけコピーするにも同じようにやらんといかんのかな


(defvar *test-name* nil)

(defmacro deftest (name parameters &body body)
`(defun ,name ,parameters
(let ((*test-name* ',name))
,@body)))

(deftest test-+ ()
(check (= (+ 1 2) 3)
(= (+ 1 2 3) 6)
(= (+ -1 -3) -4)))

2009/11/10

Lisp備忘録

今日写経したコード

(defun report-result (result form)
(format t "~:[FAIL~;PASS~] ... ~a~%" result form)
result)

(defmacro with-gensyms ((&rest names) &body body)
`(let ,(loop for n in names collect `(,n (gensym)))
,@body))

(defmacro combine-results (&body forms)
(with-gensyms (result)
`(let ((,result t))
,@(loop for f in forms collect `(unless ,f (setf ,result nil)))
,result)))

(defmacro check (&body forms)
`(combine-results
,@(loop for f in forms collect `(report-result ,f ',f))))

(defun test-+ ()
(check (= (+ 1 2) 3)
(= (+ 1 2 3) 6)
(= (+ -1 -3) -4)))



わからない場所のメモ
* formatの書式

; ~:[偽の場合~;真の場合~]
(format t "~:[FAIL~;PASS~] ... ~a~%" result form)


* loopの書式
ループキーワードというものがある
for, collect, sum, count, do, finally
collectはリストを返すようだ

; in前置詞句
* (loop for var in '(1 2 3 4) collect var)
(1 2 3 4)

; ベクタの場合はinではなくacross
* (loop for x across "abcd" collect x)
(#\a #\b #\c #\d)

;複数指定可能
(loop
for item in list
for n from 1 to 10
do (something))

2009/11/09

Emacsの備忘録

普段はVimを使用してプログラムやテキストを書いているけど、今はCommon Lispの勉強中でEmacsを利用しているので備忘録

マジックコメント
1行目にshebangがある場合は2行目に書く。

;;; -*- mode: lisp; coding: utf8 -*-


バッファ操作
  • C-x C-f ファイルを開く
  • C-x C-s 保存
  • C-x o 次のbufferに移動
  • C-x 1 分割されているウィンドウを一つにする
  • C-x 2 ウィンドウを分割
  • C-x C-b buffer list表示
  • C-x b buffer名を指定して開く

2009/05/31

Catalyst::View::HTML::Template::Pro

テンプレートにHTML::Template::Proを愛用しているんだけど、
Catalyst::View::HTML::Template::ProがCPANになかったのでC::V::HTML::Templateからcopyして作成した

cpanへの登録はよくわからんのでおいといて、とりあえず外部から取得できるようにgithubで公開。
これで職場で使いたくなっても大丈夫!

2009/03/13

Data::ObjectDriverは遅いのか

ネットをうろうろしてて、こんな記事を見つけた
ObjectDriver使えねえ。。

Data::ObjectDriverのあまりの遅さにビックリして自分で同じ機能を書き直したら、速度にして約10倍以上に跳ね上がった。そもそもmemcachedを使わずに裸のDBIでやった方がmemcachedアリのObjectDriverより速いんだから。読み込みループがですよ。すなわち300回実行したら299回はmemcachedを使っている筈のObjectDriverが、300回DBアクセスするDBIより遅いわけ。キャッシュの意味がねぇ(;´Д`)y-~ 言語を絶する。バカどもは最低でもベンチマーク取ってから人に勧めろよ



2008年10月の記事なので大分古いけど、日本ではDODの使用例とか感想がさっぱりないので気になった。
上の記事にベンチマーク結果もコードも貼ってないので、自分でベンチマークを取ってみた。

MySQL, memcached共にlocalにある環境でbenchmarkを実行し、結果は以下の通り。
ついでなので、DBICも一緒に計測した。DBICでcacheする場合のスマートに書く方法を知らべるのが面倒だったので、愚直に書いた。
_poolが付いているものは、MySQLとの接続を1度しか行わないもの。


Rate DBIC DBIC_pool DOD DBI DOD_MemCached DBI_pool DBIC_MemCached DBI_MemCached
DBIC 435/s -- -59% -75% -76% -92% -95% -96% -97%
DBIC_pool 1058/s 143% -- -40% -41% -80% -87% -89% -93%
DOD 1751/s 302% 65% -- -3% -67% -78% -82% -88%
DBI 1805/s 315% 71% 3% -- -66% -77% -82% -88%
DOD_MemCached 5263/s 1109% 397% 201% 192% -- -34% -47% -65%
DBI_pool 8000/s 1738% 656% 357% 343% 52% -- -19% -46%
DBIC_MemCached 9901/s 2174% 836% 465% 449% 88% 24% -- -34%
DBI_MemCached 14925/s 3328% 1310% 752% 727% 184% 87% 51% --


素のDBIよりDOD+memcachedの方が全然早いじゃん。
DBICで透過的にcacheする状態だと、DOD+memcachedのどっちが早いのか気になるところ。


以下にbenchmark用コードを貼っておく

#!/usr/bin/env perl

# 2009/03/13
# MySQL 5.0.27
# memcached 1.2.6
# perl v5.8.8
# Data::ObjectDriver 0.06
# DBIx::Class 0.08012
# Cache::Memcached::Fast 0.14

package DOD;
use strict;
use warnings;
use base qw(Data::ObjectDriver::BaseObject);
use Data::ObjectDriver::Driver::DBI;

__PACKAGE__->install_properties(
{ columns => [ 'id', 'word', 'text' ],
primary_key => ['id'],
datasource => 'test',
driver => Data::ObjectDriver::Driver::DBI->new(
dsn => 'dbi:mysql:dod',
username => 'dod',
password => '',
reuse_dbh => 1,
),
}
);

package DODMemCached;
use strict;
use warnings;
use base qw(Data::ObjectDriver::BaseObject);
use Data::ObjectDriver::Driver::DBI;
use Data::ObjectDriver::Driver::Cache::Memcached;
use Cache::Memcached::Fast;
__PACKAGE__->install_properties(
{ columns => [ 'id', 'word', 'text' ],
primary_key => ['id'],
datasource => 'test',
driver => Data::ObjectDriver::Driver::Cache::Memcached->new(
cache => Cache::Memcached::Fast->new(
{ servers => ['localhost:11211'] }
),
fallback => Data::ObjectDriver::Driver::DBI->new(
dsn => 'dbi:mysql:dod',
username => 'dod',
password => '',
reuse_dbh => 1,
),
),
}
);

package DBIC::Schema::Test;
use strict;
use warnings;
use base qw/DBIx::Class/;
__PACKAGE__->load_components("Core");
__PACKAGE__->table("test");
__PACKAGE__->add_columns(
"id",
{ data_type => "INT",
default_value => undef,
is_nullable => 0,
size => 11
},
"word",
{ data_type => "TEXT",
default_value => undef,
is_nullable => 0,
size => 65535,
},
"text",
{ data_type => "TEXT",
default_value => undef,
is_nullable => 1,
size => 65535,
},
);
__PACKAGE__->set_primary_key("id");

package DBIC::Schema;
use strict;
use warnings;
use base qw/DBIx::Class::Schema/;

__PACKAGE__->load_classes(qw/Test/);

package main;
use strict;
use warnings;
use DBI;
use Cache::Memcached::Fast;
use Benchmark qw(cmpthese);
my @connect_info = ( 'dbi:mysql:dod', 'dod', '' );
my $count = shift || 10_000;
my $pool = DBI->connect(@connect_info);
my $schema = DBIC::Schema->connect(@connect_info);
my $cache = Cache::Memcached::Fast->new( { servers => ['localhost:11211'] } );

cmpthese(
$count,
{ 'DBI' => sub {
my $dbh = DBI->connect(@connect_info);
my $sth
= $dbh->prepare(
'SELECT test.id, test.word, test.text FROM test WHERE id = 1'
);
$sth->execute;
my $row = $sth->fetchrow_hashref;
$sth->finish;
$dbh->disconnect;
},
'DBI_pool' => sub {
my $sth
= $pool->prepare(
'SELECT test.id, test.word, test.text FROM test WHERE id = 1'
);
$sth->execute;
my $row = $sth->fetchrow_hashref;
$sth->finish;
},
'DBI_MemCached' => sub {
my $row = $cache->get('DBI_MemCached-Test-1');
unless ($row) {
my $dbh = DBI->connect(@connect_info);
my $sth
= $dbh->prepare(
'SELECT test.id, test.word, test.text FROM test WHERE id = 1'
);
$sth->execute;
my $row = $sth->fetchrow_hashref;
$sth->finish;
$dbh->disconnect;
$cache->set( 'DBI_MemCached-Test-1', $row );
}
},

'DOD' => sub { my $row = DOD->lookup(1); },
'DOD_MemCached' => sub { my $row = DODMemCached->lookup(1); },

'DBIC' => sub {
my $s = DBIC::Schema->connect(@connect_info);
my $row = $s->resultset('Test')->find(1);
},
'DBIC_pool' => sub {
my $row = $schema->resultset('Test')->find(1);
},
'DBIC_MemCached' => sub {
my $row = $cache->get('DBIC_MemCached-Test-1');
unless ($row) {
my $s = DBIC::Schema->connect(@connect_info);
$row = $s->resultset('Test')->find(1);
$cache->set( 'DBIC_MemCached-Test-1', $row );
}
},
}
);
$pool->disconnect;