正規表現はお好き? - steps to phantasien
積んであった Beautiful Code を読んでみる. 第一章はカーニハンによる正規表現の話. 数十行のコードで簡単な正規表現を実装してみせる. パターン文字列を内部表現に変換せずマッチに使うぜ, コードも短い, ビューティホー! ...という主張なのだが, それはほんとにビューティホーなのか. UNIX 人の感覚にはついていけない. それにしても彼らは正規表現が好きだ. いつものその話ばかりしている. artu はいうまでもなく プログラミング作法 にも正規表現が出てきた. まったくこのマンネリめ. そう斜に構えつつ読み直してみると, 案外ラディカルな話も載っているのに気付く. 9.7 "オンザフライコンパイル" より: Ken Thompson はまさにこの方法によって 1967 年に IBM7094 上に正規表現を実装した. 彼のバージョンは, 正規表現に含まれる様々な処理を小さ
noocyte のプログラミング研究室
「生涯一プログラマ」志望の中年プログラマ noocyte (ヌーサイト) です． 主にプログラミングやアルゴリズムの話題と，自作フリーソフトを扱っています． 自分で考案したことを中心として，なるべくここにしかない情報を書くようにしています． よそに書いてあることは，そこを見ればすむことなので， わざわざここで同じことを書く気力が湧きません． (私はズボラなので．) 自分で考案したアルゴリズムやデータ構造を中心に解説します． メモリ管理 アラインメントの大きなメモリ領域を確保する方法 アラインメントの大きなメモリ領域を用いて， 高速かつメモリ効率の良い多数の集合を実現する方法 幾何学・CG のアルゴリズム集 ３点の座標から簡単に角度と回転方向を求める．(2・3・N次元，外積を用いる方法) 多角形の面積，重心(図心)，断面Ｎ次モーメントの公式と，向き (頂点列の回転方向) の判別方法 (Win
株式会社エス・スリー・フォー » State Map Compiler
このState Mapはゲートの制御モデルを表現しています。ゲートは2つの状態Locked(閉じている)とUnlocked(開いている)をもち、2つのイベントCoinとPassを受け付けます。 Coinイベント 門番が入場料を受け取った Passイベント 誰かがゲートを通過した また、ゲートには4つのアクションが定義されています。 Unlock ゲートを開ける Lock ゲートを閉じる Alarm 警報を鳴らす ThankYou 余分なお金をもらったことに礼を言う このState Mapの読み方は以下のとおりです: ゲートがLocked状態のとき: Coinイベントが発生したら、Unlocked状態に遷移してUnlockアクションを起こす。 Passイベントが発生したら、閉じているゲートを無理矢理誰かが通過したことに対しAlarmアクションを起こす ゲートがUnlocked状態のとき: P
フリーティケットシアター全サービスが終了
フリーティケットシアター全サービス終了 誠に勝手ながら、「フリーティケットシアター」のサービス提供を 2016年3月31日をもちまして終了させていただきました。 これまで長らくご愛顧を賜り、誠にありがとうございました。 http://www.freett.com/
fisheye view の計算式とプログラム - まめめも
fisheye view とは、なんかインターフェイスの世界では常識っぽい、フォーカスとなる点を中心に座標をぐにょーんと引き延ばす方法です。日本語が不自由ですみません。要するにこういう変換です。 皇居あたりを中心に線路地図をぐにょーんと引き延ばしています。これを実装しようと思って計算式やサンプルプログラムを探したのですが、意外に情報が少なくて手間取りました。なので記録を残しておきます。 種類 参考文献 *1 を眺めたところ、cartesian fisheye と polar fisheye の二種類があるようです。左が cartesian で右が polar です。でもこの例だとほとんど区別が付かないですね。よく見ると端っこの方のつぶれ方が違います。 cartesian fisheye view フォーカスの座標を 、引き延ばしたい点の座標を 、壁の位置を とするとき ( になる) 、引き
Network Flow
ネットワーク 定義 G：有向グラフ V：点の集合 E(G)={e=(u,v)|u,v∈V}：Gにおける辺の集合 cap(e)：各辺eの容量 s：湧出点、入口, t：流入点、出口 (s,t∈V) N=(G,cap,s,t)：ネットワーク f:E(G)→R+（辺集合E(G)から非負実数集合への関数） δ-(v)：vを終点とするNの辺の集合 δ+(v)：vを始点とするNの辺の集合 ただし、fは次の二つを満たす
lucille development blog » Blog Archive » Xorshift RNGs
G. Marsaglia. Xorshift RNGs. Journal of Statistical Software, 8(14) :1 6, 2003 http://www.jstatsoft.org/v08/i14/xorshift.pdf George Marsaglia 氏により 2003 年に考案された、xor とシフトを使うだけの超高速な擬似乱数生成器(Random Number Generator, RNG)です。周期は 2^k-1(k = 32, 64, 96, 128, 160, 192)。ランダム性のテストにも十分合格するとのこと。たとえば、周期が 2^128-1 の場合のルーチンは以下のようになり、乱数値の計算部分はわずか 1 行である。 unsigned long xor128(){ static unsigned long x=123456789,y
Webstemmer（クローラーツール）
日本語サイトでは、具体的な性能は測定していませんが、 以下のようなサイトで正しく動くことがわかっています: アサヒ・コム Nikkei NET Mainichi INTERACTIVE Yomiuri On-line IT media 東京新聞 日刊スポーツ 信濃毎日新聞 livedoor ニュース 使いかた Webstemmer をつかったテキスト抽出は以下のようなステップになります: まず、特定のニュースサイトから種となる HTML ページを多数取得する。 取得したページのレイアウトを学習する。 別の日に、同一のニュースサイトから新しい HTML ページを取得する。 2. で学習した結果をつかって、新しい HTML ページから本文を抽出する。 1. および 2. のステップが必要なのは最初の 1回だけです。 ひとたびサイトのレイアウトを学習してしまえば、 あとはレイアウトが大きく変更さ
ブロックアルゴリズムとB-Treeアルゴリズム
ファイルサーチを高速化するB-Treeアルゴリズム ext2、ext3がベースとするブロックアルゴリズムは、ブロック数が対応するディスクのジオメトリ数に制限されること、ファイルサーチにO（n）かかる（注）こと、ファイルサイズに関係するパフォーマンス低下など、いくつかの問題があった。 注：「O（n）」とは、実行時間が入力の大きさ「n」に比例するアルゴリズムである。O（n）は「nのオーダー」または「オーダーn」と読む。後述する「O（log n）」は、アルゴリズムの計算量に関する議論の場合logの底は常に2で、O（log n）の方がO（n）よりも効率が良い。例えばn＝8の場合、O（log n）は入力8に対して3回の実行で済むが、O（n）は8回の実行となる。 ReiserFS、JFS、XFSといったファイルシステムでは、こうしたブロックアルゴリズムの限界に対して、早い段階からデータベースの技術をフ
第5回 N-gramのしくみ | gihyo.jp
前回は形態素解析を使う検索エンジンのしくみについて説明しました。今回は、FINDSPOTで使用しているN-gramという検索エンジンのしくみについて説明します。 N-gramによる見出し語の切り出し 前回は、形態素解析による検索エンジンでは、検索可能な最小単位が分かち書きの切り分け単位となる点を説明しました。 一方、N-gramを使った検索エンジンでは、単純に文字の並びを見出し語としてインデックスを作成します。1文字を元にインデックスを作成する方法をユニグラム、2文字の並びを元にインデックスを作成する方法をバイグラム、3文字の並びを元にインデックスを作成する方法をトリグラムと呼んでいます。 1文字：ユニグラム 2文字：バイグラム 3文字：トリグラム N-gramによる見出し語の切り出しは、形態素解析のための文法解析を伴わないため、特定の自然言語に依存しないという特徴があります。 FINDS
Optimization of Computer Programs in C
Michael E. Lee Senior Programmer/Analyst Ontek Corporation 22941 Mill Creek Road Laguna Hills, CA 92653 USA Abstract: A substantial portion of a knowledge worker's life may be spent waiting for a computer program to produce output. Users and organizations control their wait time by purchasing faster computers, adding memory, or using faster network connections. Developers of application progra
つくってわか(った気にな)る STM - steps to phantasien t(2007-06-23)
最近みた TechTalks の中で STM (Software Transactional Memory) の話が面白かった. 紹介しようと思ったものの, まず STM の認知度はどれほどなのだろうか. 日本語でぐぐると CPU 会社の宣伝くらいしか見当たらない. 友達にたずねたら "そんなので騒いでいるのは君と Haskell ユーザくらいだよ" とのたまう. 私の脳内では STM 派とメッセージ通信派が激烈な争いを繰り広げていることになっているけれど, 気のせいなのかもしれない... 念のため TechTalks を眺める前に少し STM の話を書いてみる. そのあと話の肴に作ってみた STM のトイ実装 (500行くらい) を紹介したい. Software Transactional Memory の話 ではさっそく STM のことを簡単に説明してみよう. 専門家による一次資料を読
Lambda Animator : animated reduction of the lambda calculus
mode with Java Web Start or in an Applet Usage Screenshots Feedback Acknowledgements Related work Lambda Animator is a tool for demonstrating and experimenting with alternative reduction strategies in the lambda calculus. Eager languages reduce arguments before function application. Lazy languages reduce arguments, if needed, after function application. Reductions can also be performed within func
A Very Brief Introduction to the Pi-Calculus (in Japanese)
π-calculus 超入門 π-calculus は、80 年代の終わりごろに Milner らによって提案された並行計算のモデルの一つです。そこでは、プロセスと呼ばれる複数の独立した主体が、通信チャネルと呼ばれるデータの通り道を介して値をやりとりしながら、計算を行っていきます。π-calculus にはいろいろな変種があるのですが、ここではとりあえず次のような構成要素からなるものを考えましょう。 new x . P 新しいチャネル x を作ってから、プロセス P を実行する (channel creation) x![v1, ..., vn] チャネル x に値 v1, ..., vn を送る (asynchronous output) x?[v1, ..., vn] . P チャネル x から値 v1, ..., vn を受け取って、P を実行する (input guard) P |
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
IBM Developer
IBM メモリー管理の内側 - Japan
h-index を Ruby で書いてみた - まちゅダイアリー (2007-07-19)
サービス終了のお知らせ
データ圧縮の基礎
algorithm