きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
きまぐれ日記: Autolink: 前方最長一致ではなく最長キーワード優先一致を実現する
Hatena のキーワード置換アルゴリズムがTRIE ベースの手法に変更になったようです。以前に AC法でやる方法の記事を書いたのですが、それと似たことをやってるのでしょうか。 AC法のやり方は単純で、前方から最長一致でキーワードを見つけていきます。これまでは長いキーワードから順番に見つけていく方法(最長キーワード優先一致)だったそうですが、前方から見つけていく方法だと短いキーワードが優先される場合があります。 http://d.hatena.ne.jp/ita/20060119/p1 http://d.hatena.ne.jp/hatenadiary/20060119/1137667217 本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさし という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かき
きまぐれ日記: もっと SWIG を!
はてなでは XS を使い始めて処理速度が改善されつつあるようです。 スクリプト言語へのバインディングは、もはやミドルウェアには必須の機能だと思います。 しかし、最近気になっているのは、少なくとも日本では XS 直書きのようなスクリプト言語固有の機能を直接使ってバインディングを作成している開発者が圧倒的に多いということです。 正直なところSWIG をもっと使ってほしいです。 私が気に入っている点は以下です。 1. SWIG はスクリプト言語固有のバインディング作成バッドノウハウを エレガントにラップしてくれます。たとえば、例外処理などがいい例ですが、 SWIG のインタフェイス上で例外処理を書いておけば、 各言語の例外処理のシンタックスに適切に変換してくれます。 2. バンディングレベルで OOP の機能が無く、プリミティブな関数呼び出ししかできない スクリプト言語(perl,python,
MeCab: Yet Another Part-of-Speech and MorphologicalAnalyzer
MeCab に至るまでの形態素解析器開発の歴史等はこちらをご覧ください メーリングリスト 一般ユーザ向けメーリングリスト 開発者向けメーリングリスト 新着情報 2008-02-03 MeCab 0.97 マルチスレッド環境で辞書を開くときの排他制御がうまくいっていなかったバグの修正 Windows版でインストール時に辞書の文字コードを指定できるようになった 一部のコンパイラで正しくコンパイルできなかった問題の修正 部分解析モードを変更するAPI の追加 (Tagger::set_partial()) ラティスの生成レベルを変更するAPI の追加 (Tagger::set_lattice_level()) 温度パラメータを変更するAPIの追加 (Tagger::set_theta()) 全候補出力モードを変更するAPIの追加 (Tagger::set_all_morphs()) 2007-
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://chasen.org/~taku/blog/archives/2005/10/popularity_qual.html
http://chasen.org/~taku/blog/archives/2005/09/_swig_perlrubyp.html
きまぐれ日記: はてなキーワードを高速に付与
きまぐれ日記: SWIG で C++ の pure virtual を wrap
