サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
tociyuki.hatenablog.jp
SQL で木構造を扱う方法の一つ、 閉包表を SQLite3 をターゲットとして試してみます。 閉包表 (Closure Table Tree Encoding) は、 ノードの主キーと、 そのノードを根とする部分木中の主キーの集合を関連付けます。 この関連付けを逆写像で眺めると、 経路列挙をカラムに文字列で格納するのではなく、 別の多対多の表に切り出したものになります。 そのため、 入れ子集合、 経路列挙の 2 つの視点から木構造を利用できるようになっています。 閉包表の名称でこの手法の利用例が説明されだしたのは 2010 年ぐらいからです。 参考 ⇒ The simplest(?) way to do tree-based queries in SQL (dirtSimple.org) ⇒ Moving Subtrees in Closure Table Hierarchies - P
自宅の VDSL モデム(B-FLETS)がバースト状にリンク速度が低下し、高い割合でリンクダウンしていた現象が、冷蔵庫のアース線のつけなおしで収まりました。このアース線は、冷蔵庫を買った 12 年前にとりつけてもらって以来そのままの 12 年モノでした。長年の表面腐食のせいで端子との接触抵抗が高くなってしまい、ノイズ対策の用をたさなくなっていたのが原因のようです。 VDSL を不安定にするノイズ源に長らく思い当たらなかったのですが、1週間前、台所のカウンタに ibook を置いて料理の合間にアクセスしているとき、冷蔵庫のコンプレッサが動き始めたとたんにリンクダウンすることに気がつきました。5回以上の再現が確認でき、ノイズ源が確定しました。わかってしまえば、単純な理由だったわけです。 とはいっても、わかった当初、アース線の接触抵抗には思い当たらず、まずは電解コンデンサの経年劣化を疑いました
本棚を整理していたところ、原 通宏「Z80版 FIG-FORTHの解析」(1981年 CQ出版) が出てきました。懐かしくなってひととおり目を通した上で、懐古趣味にふけってみます。この文献は、8080 版 FIG-FORTH 1.1 (pdf) を原氏が Z80 に移植したソースコードに解説を加えたものです。 FORTH では手続きのことを語 (ワード) と呼びます。語は、仮想コードで記述された 2 次語と、ホスト・プロセッサの機械語で記述された 1 次語の 2 種類に加えて、様々なグローバル変数や配列も語になっています。実行定義を含む語は名前とコードの組で、名前は 7 ビット ASCII 文字列とビット・フラグ、次の語への単方向リンクからなります。FIG-FORTH 1.1 は、名前の長さフィールドは 5 ビット、つまり最大 31 文字で、1 ビットのフラグ 2 つからなります。名前フィ
Deflate のフォーマットは出回り始めたころに一通り調べたのですが、20 年以上前のことなので、細部を忘れてしまっていました。そこで、復習兼ねて、Ruby で内容をダンプするプログラムを書いてみました。Deflate を含んでいる圧縮データを作るのには gzip コマンドが手軽なので、gzip 形式をダンプするように作ってあります。 ⇒ gzipdump.rb - dump gzip file Gist 2015年2月25日 固定ハフマン・ブロックの距離コードをハフマン符号として読まないといけないのに、固定長ビットで読んでいたバグを修正しました。 2015年2月20日 gzip 形式の CRC32 欄の取得が正しくなかったバグを修正しました。 使い方: 標準入力から圧縮データを読み込んで、標準出力へ内容をダンプします。gzip とパイプでつなぐのがてっとり早くて楽です。なお、カスタム・
まとめてみるのも一興かと。抜粋した上で、自己コメントつきにしてみました。 1. 任意精度の高速除算と高速乗算 ⇒ Burnikel と Ziegler による再帰除算 (1) ⇒ 巨大整数の除算 Barrett 法 ⇒ Schönhage-Strassen による整数環フーリエ変換乗算 非フェルマー数版 ⇒ Schönhage-Strassen のフーリエ乗算 今年、最大級の難物でした。 プログラミングを身につけてから、一度は書いてみたいものだと考えていた、巨大整数の高速乗算である整数環フーリエ変換乗算を記述することができました。高速除算である再帰除算とニュートン除算はそれに取り組む前の巨大整数演算の基盤を作るための前フリですが、それにしても乗算・除算の両方とも細部まで理解しつくすまで多くの日数を費やしました。除算はそれほど苦しむことはなかったのですが、整数環フーリエ変換乗算はかなりの紆余
正規表現を非決定性有限オートマトン (NFA) に直訳したまま擬似並列スレッド実行することで文字列とのマッチングをおこなう Rob Pike の仮想マシンがあります。正規表現をマルチスレッド・バイトコードにコンパイルして動かす方式は Ken Thompson による先例があり、Rob Pike がグループによるキャプチャをおこなえるように改良しています。Rob Pike 版は Plan9 の sam テキストエディタのために書いたのがオリジナルで、Plan9 の正規表現ライブラリに採用されています。この正規表現は欲張りマッチングだけで、非欲張りマッチングは使えません。 ⇒ http://swtch.com/usr/local/plan9/src/libregexp/regexec.c Plan9 の regexp(3) ライブラリ 欲張りマッチングしかない それを Russ Cox が非欲
Ruby で記述してある LALR(1) 構文解析ツールといえば Racc だ、 と相場は決まっていて、私も便利に利用しています。ただし、Racc は実用性優先で、あまりに Bison を意識しすぎている上に、速度優先、内部のオブジェクトの構造がつくりこまれすぎときて、いじくって余計な機能をつけて遊んでみようとか、機能をちょっと変えてみようとかするには、まったくもって向いていません。 実用性よりも、内部をいじって遊ぶのに向いた小気味の良いピュア Ruby な LALR(1) 構文解析器もあって良いのではないかと考えて、作ってみました。構文解析表の生成部と駆動部をすべて組み込んで、500 行程度のコンパクトな解析器処理系です。構文記述はハッシュと配列に優先順位と生成規則のインスタンスを並べるだけで良いのですが、少しは記述性を上げてみようとの試みで、Ruby の組み込み演算子を使って生成規則を
半分ネタ半分本気のウェブ掲示板スクリプトです。名前の通り 1 万件 (N10K) を越えるエントリを投稿・閲覧可能な掲示板です。データは平文のテキスト・ファイルに保存する作りで、掲示板としては、とてもシンプルでたいしたことないのですが、莫大なエントリを食わせても余裕で閲覧・投稿・削除をおこなえるのがポイントです。といっても、速度が落ちないからと調子に乗って食わせていくと、データ・ファイルのサイズが数百メガバイトに膨れ上がっていくので、128メガバイトの容量制限と10万件のエントリ数制限をかけています。 このスクリプトはコンセプト・スクリプトでありエラー処理が甘いため、インターネットで公開して使わないでください。ローカルマシンで遊ぶ程度にしておいてくれた方が書いた私も安心します。 投稿制限は、ホワイト・リストによる URL 制限と、行数を漢字60文字を一行分として文字数と改行数から計算し、3
タグはスカラー、シーケンス、マッピングのそれぞれのノードにデータ型を指定します。一つのノードにタグ・プロパティを一つ指定でき、ノードに指定できるデータ型は一つだけに限定されています。 タグにはグローバル・タグとローカル・タグの2種類があり、前者は URI、後者はシンボルです。タグをどのようなデータ型へ当てはめるかは YAML ストリームとは別に定義されているだろうスキーマの存在を仮定しています。スキーマといっても、仕様とワンセットで定義されている JSON スキーマや YAML スキーマは人間向けの説明が記入されている HTML ページにすぎません。これらのスキーマのページは WWW 内から URL で参照できるようになっています。一方、タグには tag URI scheme RFC 4151 の利用が推奨されており、タグの URI とスキーマページの URL の関係は機械的に解決できませ
懐古趣味の続きです。 Kohlbecker が 1986 年に提案した健全なマクロ (Hygienic macro) の実装の仕方を見たとき、 「あれ、これ、どっかで見たことあるなぁ」と感じたものです。 当時、 何を頭に思い浮かべていたかというと、 Prolog の単一化処理の際におこなう変数のリネームのやりかたでした。 Prolog では一種の参照渡しをおこないつつ同じ節を再帰的に単一化するため、 独特のやっかいな問題が生じます。 単純に実装するには唯一の環境フレームを使う代わりに節をマクロ扱いして、 単一化する前の実行時に節内の変数に識別番号を追加するなりしてリネームし、新しい節へと丸ごとコピー生成する方法があります。 このやりかたを採用していた実装は 1980 年代にいくつかあり、 Prolog-KABA もその一つだったはずです。 Scheme での Prolog 風の処理系実装例
YAML 1.2 の仕様 http://www.yaml.org/spec/1.2/spec.html が 2009 年夏に公開されてから 3 年が経過しています。3年もたっているというのに、いまだに構文だけでもフルセットで扱える YAML プロセサは少ないので、手打ちで書くためのメモに意味がはたしてあるのだろうかと疑念をおぼえつつ、構文読解完了記念をかねて作っていくことにします。 %YAML 1.2 # これが YAML ディレクティブ。最初のドキュメントの開始行 %TAG !! tag:example.com,2000:app/ # これがタグ・ディレクティブ --- !!int 1 - 3 # !! の URI を切り替えてしまったので、YAML Core の整数ではなくなる # 最初のドキュメントはこの行まで --- # この行から2番目のドキュメント !!int 1 # これは
git のオブジェクト・データベースはファイル・ベースのハッシュ・キー・バリュー・ストアになっています。2形式あり、キーをファイル名にしてエントリごとファイルに格納する単純なものと、複数のエントリをファイルにパックしたものとがあります。git の最近のコミットは単純形式で格納されているため、まず、単純形式を読み取ってみます。 ⇒ http://git-scm.com/book/ja/Gitの内側-Gitオブジェクト さて、Perl からは CPAN モジュールの Git-PurePerl-0.48 を使って読み書きできますけど、このモジュールは Moose ウェアなので動かせる環境を選ぶのが難点です。少なくとも、共用レンタルサーバの CGI や、Arm ベースの低クロック少メモリ・サーバで動かすには向いていません。ざっと読んで受けた印象では、Moose 使わずに、Class-Accesso
「RSpec の入門とその一歩先へ - t-wadaの日記」は素晴らしいのですけど、ruby-1.8 と rspec-1 が対象です。 ruby-1.9 と rspec-2 では仕様が変更になっているため、そのまま試そうとしても動きません。 rspec-2 のライブラリ名とコマンド名は rspec に名称変更されています。 ruby-1.9 で相対パスから require するときは、require_relative を使うのが推奨されています。 ふるまい記述ファイルと、コマンド名をちょっと変更するだけで、これらのバージョンの組み合わせでも試すことができるようになります。 message_filter_spec.rb への差分 require 'rubygems' # この行不要だが、あっても害はない +require 'rspec' -require 'spec' +require_re
リファレンス The Official YAML Web Site YAML Version 1.2 YAML 1.2 BNF from Specification Web Page HackageDB: YamlReference-0.9.3 PyYAML LibYAML – PyYAML PythonTagScheme – PyYAML PerlTagScheme – PyYAML YAML 1.2 メモのインデックス YAMLドキュメント ドキュメントのインデント・レベル リテラル 行の折りたたみ プレイン ブロック・シーケンス ブロック・マッピング フロー・シーケンス フロー・マッピング エイリアス タグ ピュア Perl YAML 1.2 構文解析器 tociyuki/libyaml-parser-btrack-perl GitHub YAML 1.2 のバックトラック構文解析器
「富豪的 CLOSURE 計算結果使い捨て型シフト還元解析おもちゃ」は、プログラミング言語用の構文解析器で使うのには向いていません。どちらかというと、左再帰があるテキスト処理やデータ処理の構文解析器に使えないものかと考えています。 ところで、プログラミング言語で上向き構文解析したい箇所と言えば、左再帰になっている二項演算子式の生成規則がまっさきに思い浮かびます。他は下向き構文解析向けの部分が大半です。それならば、下向き用の定番、再帰下降型解析器の中に上向き構文解析器を組み込めると何かと便利でしょう。そのような用途に、演算子優先順位構文解析器 (Operator-precedence parser) がうってつけです。yacc/bison のように優先順位と左結号か右結合かを指定するだけで望みのままに二項演算子を利用できる解析器を、再帰下降型構文解析器へシームレスに組み込むことができるように
「B Tree をいけにえの技法で 」書いたなら、B+ Tree も同様に。 さて、B Tree の木構造をリストで表現した場合、左から右へデータ・レコードが順序良く並んでおり、それを括弧で入れ子に区切った形をしています。一方、B+ Tree は、リーフの中に左から右へ順序良くデータ・レコードが並び、リーフ中の右端のキーの複製をリーフ間に 1 つずつ挟んだ形をしています。ノードのキーはインデックスの役割に徹するようになり、ノードとリーフがそれぞれインデックスとデータ・コンテナに役割分担をするようになったとも見れます。インデックスのため、余計にキーの格納回数が増えているのですけど、それを補って余りあるほど、扱いが容易になりますし、なんといってもデータ・レコードが全部リーフに収まるようになったおかげで削除処理がシンプルになるのがうれしいところです。 + # B+ Tree example: +
単方向連結リストの中から eq で一致する要素を削除するとき、リストの頭にダミーのセルをくっつけておいてから、ループを回すのは常識の部類に属します。そうしておけば、一つ先が一致したところで、手前のセルからのリンクをすげかえることができるからです。 ⇒ 竹内郁雄「初めての人のためのLISP」, 1986, サイエンス社、ISBN4-7819-0454-8、141 ページ これをよく「いけにえの技法」と呼びます。 でも、それを「いけにえの技法」と呼ぶのか、それも「よく」呼ぶのかどうか。この本の元になった連載で初めてこの名称を目にした当時、御大のジョークの可能性高しと疑ったものです。実は今でも疑っています。名称についての真相はともかくとして、基本的には単方向連結リストのリンクのつけかえをするときに使う手法です。それでは、あまりに当たり前すぎておもしろくないので、ここではひとひねりして B Tre
誰かさんのモットーの「やらなくてもいいことなら、やらない。やらなければならないことは手短に」の見本のような、ガベージ・コレクションのアルゴリズムの一つが 1980 年代初頭に Hughe が提唱した lazy sweep です。このアルゴリズムの目的は、1960 年代から使われてきた伝統的な mark & sweep が、1980 年代に入りメモリを潤沢に使えるようになってきた頃、でもまだプロセッサのメモリアクセスが絶望的に遅かった頃、ガベージ・コレクションが処理の長時間中断をひきおこすのが懸念されていた頃、それを回避する手法の一つとして提唱されたものです。mark フェーズの方は 1970 年代からインクリメンタルな方法がいくつか提唱されてきたのに対して、Hughe は sweep フェーズに手をつけました。sweep フェーズの欠点は、他の処理を中断させておいて、ガベージ・コレクション
mruby のインタープリタ Reit VM をじっくりと読んでいる最中です。 Riet VM のオブジェクト・コードの逆アセンブルリストは、bin/mruby に verbose オプションをつけると標準出力にパーサ出力の構文木出力に続いて表示されます。既存のオブジェクト・ファイルの逆アセンブルリストも、それで表示できます。最適化処理がないため、構文木からどのようにコード生成するのか、出力眺めるだけで手にとるようにわかりやすいです。 $ bin/mruby --verbose prime.rb構文木は LISP の cons を使った連結リストになっていて、car、cdr がそのままソース中に記述されているので、LISP 慣れしている自分にとってはすごく src/codegen.c が読みやすくなっててうれしいことです。できれば、verbose の出力も括弧リストで表示してくれたら、Em
先読み機能付き左選択肢優先の正規表現用 NFA にプッシュダウン・スタックをつけてリエントラントに書き直し、欲張りマッチングの後戻りバックトラッキングを止めにすると、そのままwikipedia:解析表現文法 (Parsing Expression Grammar, PEG と略す) を解釈できるオートマトンになります。 さて、Perl は 5.8 の頃から既にバックトラック抑制機能をもっており、さらに 5.14 の組み込みエンジンは解析表現埋め込みの Perl 実行文含めてリエントラントに動くように書き直されたものになっています。ということで、Perl-5.14 なら PEG をそのまま正規表現感覚で実行可能になっているというわけです。PEG は正規表現にかなり近い記法ではあるのですけど、それでも慣れ親しんだ正規表現の記法そのままで PEG できるのは素晴らしく、さすがに、まだ CPAN
はてなブックマークのホットエントリに、「Cでのポインタの読み方 c_pointer」が上がっているのを見つけて、この前の秋、デニス・リッチー死去の方に接した折に、C 言語の宣言を Go 言語風(PASCAL 言語風とも言えます)に変換するスクリプトを Ruby/Racc で作成したことを思い出しました。このスクリプトでは、struct や union は扱えませんが、リンク先にある例題程度なら難なく解釈してくれます。 $ racc pcdecl.y && ruby pcdecl.tab.rb input declaration of ANSI C. "quit" or "." for end. > int (*p[5])[3]; p: array[5] of pointer to array[3] of int. > char (*(*fp)(void))(int); fp: pointe
次の環境で表題のような挙動をしており、はまってしまったので備忘録を残します。 perl-5.14.1 built for i686-linux DBI-1.616 DBD-mysql-4.0.19 MySQL-5.1.41 DBD::mysql ドライバで $dbh->{mysql_enable_utf8} = 1 にすると、MYSQL_TYPE_STRING なカラムを自動的に utf8::decode() してくれます。 DBD-mysql-4.0.19/dbdimp.c 3827行目より case MYSQL_TYPE_STRING: if (DBIc_TRACE_LEVEL(imp_xxh) >= 2) PerlIO_printf(DBILOGFP, "\t\tst_fetch string data %s\n", fbh->data); sv_setpvn(sv, fbh->da
glibc の strftime(3) は、日本ロケールになっていると、%E で年号を、%O で漢数字で日付時刻を表す機能があります。Perl からも、strftime(3)を POSIX モジュールや Time::Piece モジュールから使うとデフォルトで現在のロケールを setlocale してますので、これらの表示をさせることができます。 $ perl -e 'use Time::Piece; say localtime->strftime("%%Ec = %Ec\n (略)")' %Ec = 平成23年08月02日 00時38分48秒 %EC = 平成 %Ex = 平成23年08月02日 %EX = 00時38分48秒 %Ey = 23 %EY = 平成23年 %Od = 二 %Oe = 二 %OH = 〇 %OI = 十二 %Om = 八 %OM = 三十八 %OS = 四十八
木構造を入れ子区間モデルで扱う方法のうち、挿入と削除をおこなう SQL 文を考えてみました。SQLite 3 でのみ動作検証しています。 ネタ元その1⇒「SQLアタマアカデミー:第6回 SQLで木構造を扱う〜入れ子区間モデル (1)もしも無限の資源があったなら |gihyo.jp … 技術評論社」 ネタ元その2⇒「SQLで木と階層構造のデータを扱う(1)―― 入れ子集合モデル」 テーブル作成 入れ子集合モデルの lft と rgt を INTEGER から REAL へ変更するだけです。 CREATE TABLE IF NOT EXISTS org ( person VARCHAR(32) PRIMARY KEY ,lft REAL NOT NULL ,rgt REAL NOT NULL ,CHECK (lft < rgt) ); CREATE INDEX IF NOT EXISTS or
東京電力でんき予報の CSV ファイルが 2011年7月1日よりリニューアルしていたので、Perl で扱いやすいデータに加工するモジュールをお試しで書いてみました。ソースは GIST に置いています。 ⇒ https://gist.github.com/99f1c5571662af5abd70 (Net/Tepco/Forecast.pm) 2011年7月2日バグ修正: 0.003 epoch の計算に timelocal ではなく timegm を使い、JST のタイムゾーン・オフセットの補正をおこなうようにしました。これにより JST 以外のタイムゾーンに設定してあるマシンであっても、正しい epoch が得られます。 2011年7月2日バグ修正: 0.002 tomorrow_capacity と tomorrow_estimate の period と period_to が当日の
Mockへの接続。 use Test::More; use DBI; plan 'no_plan'; my $dbh = DBI->connect('dbi:Mock:', '', ''); my($stmt, $sth, $history, @param, $rows); SQL 文とパラメータが期待している通りに渡されたかどうかをテストするには。 ($stmt, @param) = ('UPDATE foo SET bar = ? WHERE baz = ?', 1, 'test'); $dbh->{mock_clear_history} = 1; $sth = $dbh->prepare($stmt); $sth->execute(@param); $history = $dbh->{mock_all_history}; is_deeply { stmt => [map { $_->
MacOS X 10.5.8 ppc 添付の curl に問題があり、perlbrew が curl を検出してくれません。curl --version がステータス・コード 2 を返すためです。問題があるのは curl の方であり、こちらをアップデートするのが筋でしょうけど、perlbrew に応急処置を施して動かしています。 { my @command; sub http_get { my ($url, $header, $cb) = @_; if (ref($header) eq 'CODE') { $cb = $header; $header = undef; } if (! @command) { my @commands = ( [qw( curl --silent --location )], [qw( wget --no-check-certificate --quiet
Google App Engine では Python を使ってみようと手をだしています。Ruby を使った経験があれば、1時間もすれば、Python で App を記述できるほどで、それほど大きな差はありません。ただし、もちろん異なるポリシーで作られている言語ですから、違いはあります。私が大きく違うと感じたのはリストの操作でした。 試しにフィボナッチ数列を Ruby で作ってみるとこんな感じになるでしょう。 $ irb irb(main):001:0> fib = [0, 1] => [0, 1] irb(main):002:0> fib[2] = fib[1] + fib[0] => 1 irb(main):003:0> fib[3] = fib[2] + fib[1] => 2 irb(main):004:0> (4..20).each do |i| irb(main):005:1*
Secure Remote Password プロトコル (略号は SRP) 総本山のサイト http://srp.stanford.edu/ で公開されている Javascript による SRP-6a のオンライン・デモ http://srp.stanford.edu/demo/ を Ruby に訳してみました。モジュラスは1024ビットのみに対応しています。 ⇒ https://gist.github.com/790048 SRP-6a の特徴は以下の通りで、Diffie-Hellman 鍵交換に似た数学モデルを使って一連のチャレンジ・レスポンスをおこないます。 ユーザ名 username と共通鍵である平文パスワード password を使って、クライアントとサーバ間でユーザ認証をおこなうプロトコルである。 サーバは平文パスワードをサーバは保存しない。ハッシュ値から求めた巨大整数を
次のページ
このページを最初にブックマークしてみませんか?
『Tociyuki::Diary』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く