d.y.d. - Boost.勉強会
13:54 09/12/31 年末まとめ 今年何をやったことや読んだものを振り返ろうと思います。 恒例のゲーム報告から行くと、 万歩 と 深遠HA クリアしました！ その後他のダンジョンには潜ってないけど、何かまたそろそろ始めようかな…。 ／ プログラミング関係は、ハッカソン的なもので 何個か 小ネタ を仕上げただけで、 ちゃんとしたものは作ってないですね。困った困った…。 どっちかというと、勉強会的なイベントで発表するネタを考える方が多かった。 特にFLTV での "真・自然言語プログラミング" の発表内容は割と個人的に会心の出来なのですが、多くの方に好評いただけたので嬉しいです。 なんだかもう、しばらくの間は、私はそういうキャラということでいいのではないかと思い始めてきました。 ものを作ることに全力をかけている人は多いけれど、 「一見難しく見えることをいかに簡単に噛み砕いて見せるか」を
MySQL 5.1.41リリース - SH2の日記
出ました。今回は機能の追加・変更が4件、バグ修正が62件あります。 MySQL 5.1.38から同梱されるようになったInnoDB Pluginですが、MySQL 5.1.41ではバージョンが1.0.5に上がり、ついにRC(リリース候補版)となりました。再掲になりますがInnoDB PluginはビルトインのInnoDBに比べて以下のような機能強化が施されており、非常に有用性の高いものです。そろそろ利用を検討しても良い時期に入ってきたのではないかと思います。 高速なインデックス作成。従来InnoDBのCREATE INDEXはテーブルの再作成を伴っていました テーブルとインデックスの圧縮 (検証結果その1、その2) INFORMATION_SCHEMAによるロック競合の検出 (検証結果) CPUスケーラビリティの向上 (1.0.3から) バックグラウンドI/Oスレッドの増加 (1.0.4か
DO++: 左傾赤黒木
漢字で書くと仰々しいが、赤黒木 (wikipedia) red-black tree (english wikipedia)という平衡二分木で最も多くつかわれているデータ構造の、改善版が出てたそうだ。 left-leaning red-black tree (pdf) 日本語に訳すと左傾赤黒木かな。簡単な漢字を並べている感じがしてしまう 赤黒木の詳細については、wikipediaなどをよんでもらうとして、これは更新時間が定数で更新箇所が局所的（これはマルチスレッドとかでロックする箇所をかなり細かい単位で、できるという強い利点もある）のだが、実装が結構面倒くさい。例えばC++ stl のmapとかの赤黒木の実装のstl_tree.h(google code search)は大変なことになっている（特にRb_tree_rebalance_for_eraseとか） 赤黒木というのは動的データ構造
DO++ : 透過的データ圧縮
可逆データ圧縮分野で、現在研究が盛んな分野の一つが、データを圧縮した状態のまま定数時間でランダムアクセスをサポートするデータ圧縮方式です（word RAMモデルでO(log n)サイズの復元が定数時間)。 これは、データをあたかも圧縮していないかのように扱えるため、透過的データ圧縮/構造と呼ばれています（英語だとまだ決まってない？)。 例えば1GBのデータを圧縮した状態で、途中300MB目から4Byteだけ復元しようというのが定数時間で実現できるわけです。これは理論的にもかなり強いことをいっていて，例えば今あるデータ構造やアルゴリズムが、O(T)時間である問題を解けるというのがあったら、それを全く同じO(T)時間のままデータ構造を圧縮し作業領域量を減らすことができます (一応データ構造に対し読み込み操作しか無い場合。書き込みもある場合はまたちょっと面倒になる） このデータを圧縮したまま扱う
mixi Engineers’ Blog » かんたん友人検索 その壱
朝7時30分に起きて駒沢公園をジョギングすること10日目のmikioです。だいぶ体が軽くなってきて、そろそろ体型にも変化が出てくるかなと期待する毎日です。さて、以前の記事で予告した通り、Tokyo Dystopiaを使ったmixi内の検索機能をインディーズ機能としてリリースしました。「かんたん友人検索」という名のとおり、mixiの登録ユーザを対象として友人や知人を簡単に検索する機能です。操作を簡潔にしながらも、マイミクシィのつながりなどを使って検索精度を高めているのが特徴です。 シンプルにした 見た目として最も大きな特徴は、従来の友人検索よりも入力フィールドの数を減らしたことです。従来では「姓」「名」「ニックネーム」「性別」「年齢（下限）」「年齢（上限）」「血液型」「現住所（都道府県）」「現住所（市区町村）」「出身地（都道府県）」「出身地（市区町村）」「趣味」「職業」「キーワード」「写真」
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
ルンゲクッタ法で2階連立微分方程式を解く - きしだのHatena
今回は、空気抵抗があるときの物体の軌跡を描いてみました。下のプログラムでは、実際にはアニメーションさせてます。 ※追記 2023/4/30 動画を投稿しました 空気抵抗がある中でモノを投げるシミュレーションhttps://t.co/zd6SCX8qE1 pic.twitter.com/IM2HbKomzc— きしだൠ(K1S) (@kis) 2023年4月30日 2階以上の微分方程式は、 を、 と置くことで という1階連立微分方程式に分解して、ルンゲクッタ法を使います。 このとき物体の位置x,yの微分方程式は、空気抵抗の係数をT、重力加速度をgとすると となります。 ここで と置くことで のような１階微分方程式に変形して計算を行います。 プログラム中では、funcw・funcvメソッドが変形後の式にあたります。 こうやって2階微分方程式が解けるようになると、いろいろな物理現象がシミュレート
期待値最大化法などのあれこれ - DO++
実装よりの話。 近年、Nonparametric Bayes手法が自然言語処理やら機械学習で流行っているのですが測度論とかからスタートするのは大変で、恩恵にあずかりたいがなかなか大変。 で教師無し学習で頻出する期待値最大化法(EM法[英語 wikipedia])を使っている場合、そのコードをちょっと変えるとDPを近似できますよというのを実際試してみると結構うまくいく （ACLのtutorialとかが詳しい） 期待値最大化法では、Mステップでを各パラメーターを正規化する部分があるが、 zのパラメータ = C_{z} / \sum_{z'} C_{z'} (C_{z}はEステップで数えたzの出現回数）、 ここを zのパラメータ = exp Ψ(C_{z}) / exp Ψ(\sum_{z'} C_{z'}) と置き換えるだけでDirichlet Processを使ったものと同じ効果（大きいクラ
"comb sort" Motoyuki's Diary:2000年5月下旬
昨日から延々とサーバ構築。 SCSI HDD の騒音に耐えかねて再インストール決行。 旧おうちサーバで使っていた 20GB IDE HDD を入れて IDE 10GB + 20GB 体制にする。 データの転送に時間をとられた *1ため、ほぼ二日間の間メールの読み書きができなかった。
高速な算術圧縮を実現する「Range Coder」（データ圧縮, 算術圧縮, Range Coder）
はじめに 本記事では、全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。 算術圧縮は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号法です。各文字に固定の符号を割り当てるHuffman法とは違い、符号化を状態更新とみなし、すべての文字を符号し終わった後の状態を保存することで符号化を実現します。これにより1文字単位の符号長を1bitより細かく調整することが可能となります。 算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化、復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは、算術符号の処理をバイト単位で行うことで高速な処理を可能にします。 また、算術圧縮については概要から説明します。対象読者 C++の利用者を対象としています。データ圧縮の基礎を知っていることが望まし
C10N
Please note we may provide content or links from or to other web sites through our web site. This privacy policy does not apply to these other web sites and we recommend that you review the privacy policy at each web site to determine how that site protects your privacy. The Information We Collect We do collect web site usage information from visitors to our site. This information is used for stat
Javascriptでdiffる ( with 形態素解析 ) (nakatani @ cybozu labs)
Javascript で diff というのはいくつか試された例はあるようですが、まだこれといった決定打は出ていない様子です。 実は diff は見た目ほど軽い処理ではないので、Javascript にやらせるのはこれが結構大変…… diff の計算量は、おおざっぱに言うと比較対象の要素数の二乗に比例し（実際にはそれより小さくすることができるのですが、まあ話のイメージとして）、かつメモリを大量に消費するので、バッチ的な処理に最適化されていない Javascript にはどうしても荷が重いものとなってしまいます。 比較対象の要素数を減らせば当然計算量は減りますが、行単位で比較してもあまり嬉しくない（わざわざ Javascript で処理するということは自然文が対象と思って良いでしょう）。最小の文字単位だとギブアップ。 ということは形態素解析で分かち書きして、単語単位で diff するのが J
Azul Systems - Cliff Click Jr.’s Blog: A Non-Blocking HashTable, Part 2
A Non-Blocking HashTable, Part 2 April 2, 2007 In a previous blog I talked about my Non-Blocking Hash Table, and how to implement 'get()'. This blog will focus on 'put()' and all variations. The hard part will be figuring out how to include state machine diagrams in a blog! Quick recap: the HashTable is a closed power-of-2 sized table. The table holds Key/Value pairs in even/odd entries in a
Computer Laboratory – Systems Research Group – NetOS: Practical lock-free data structures
Introduction Through careful design and implementation it's possible to build data structures that are safe for concurrent use without needing to manage locks or block threads. These non-blocking data structures can increase performance by allowing extra concurrency and can improve robustness by avoiding some of the problems caused by priority inversion in local settings, or machine and link failu
Ross Bencina » Some notes on lock-free and wait-free algorithms
Over the past two decades the research community has developed a body of knowledge concerning “Lock-Free” and “Wait-Free” algorithms and data structures. These techniques allow concurrent update of shared data structures without resorting to critical sections protected by operating system managed locks. A number of wait-free and lock free algorithms for simple data structures such as LIFO stacks a
tips - MD5のコスト : 404 Blog Not Found
2007年03月27日23:30 カテゴリTips tips - MD5のコスト 同一ファイルかどうかを調べるのにMD5を使うというのは、比較するファイルが両方手元にある場合はおすすめ出来ません。 重複ファイルを消すPythonスクリプト 「ファイル名が違っても中身が同じファイルを探してくれる『NoClone』 | P O P * P O P」と 「404 Blog Not Found:perl - File::Find::Identical」にインスパイヤされた話ですが、 プログラム自体は数年前にPerlとmd5sumで書いて、 去年Pythonで書き直しました。 ダウンロードはこちら。その一番の理由は、コストです。 ファイルどおしの単純比較の倍以上します。 以下は、FreeBSD 6.2、Xeon 2.66GHz x 2、400GB ATAPI 7200rpmにおいて、FreeBSD
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
fmath
B-link-tree
Consistent Hash - A Diary Which Heads for Convergence (Naist branch).(2008-09-30)
http://www.ya.sakura.ne.jp/~moro/resources/ngram/morogram.html