www.global.toshiba › techReviewAssets › tech › review › 2001/07 モンゴメリ乗算は,除算処理を利用せずに剰余付き乗算. を計算する手法である。通常,多倍長整数での四則演算に. おいてもっとも処理時間が掛かるのが除算であるため,モン.
Whenever people start talking about NP-Complete problems, or even NP problems, one of the first examples they reach for is the classic Traveling Salesperson Problem. TSP makes sense because it intuitively can’t be solved quickly due to how difficult the problem sounds, so it’s reasonable for people to use it in discussions about P versus NP. The problem is, 99% of the time people discuss Traveling
SPIRE2012で発表したメモリー効率の良い文法圧縮のための可変長コードに関する論文を公開しました。 Y.Takabatake, Y.Tabei, H.Sakamoto: Variable-Length Codes for Space-Efficient Grammar-Based Compression, Symposium on String Processing and Information Retrieval (SPIRE), Cartagena, Colombia, 2012. Link to the PDF 上記の論文に基づくオンライ文法圧縮(online LCA)のC++による実装(olca++)を公開しました。 下のサイトからダウンロードできます。 https://code.google.com/p/olca-plus-plus/ 文法圧縮のアルゴリズムは@marugo
Levenberg-Marquardt法ってのは山あり谷ありの関数の谷の底を(=最小値)を見つけるアルゴリズムのこと。 骨子は (a) 関数の微分の微分が零になる場所を探す方法 (b) 二階微分を一回微分の二乗で近似する (Gauss-Newton法) (c) 安定性の向上の工夫を入れる(Levenberg-Marquardt法) というもの。 以下 (a) → (b) → (c) の順で記述する。 関数の最小値を見つけたいんだから、微分をして値が減る方向に進んでいく、というのが簡単な考え方だと思う。 これを最急降下法と呼ぶ。 この方法は関数の形が何であっても確実に値を減じることができるが、とにかく遅い。 然るに関数の形に関する事前知識がある場合に、この情報を積極的に利用できないか、ってのが出発点。 で、Levenberg-Marquardt法の場合は「山あり谷ありの関数」ってのは「(局所
先日、「『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
Ralf Hinze and Ross Paterson, Journal of Functional Programming 16(2):197–217, 2006. doi:10.1017/S0956796805005769 Summary We present 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece. Representations achieving these bounds have appeared
In computer science, the VList is a persistent data structure designed by Phil Bagwell in 2002 that combines the fast indexing of arrays with the easy extension of cons-based (or singly-linked) linked lists.[1] Like arrays, VLists have constant-time lookup on average and are highly compact, requiring only O(log n) storage for pointers, allowing them to take advantage of locality of reference. Like
A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations: Add a tree consisting of a single node to the forest. Given a node in one of the trees, disconnect it (and its subtree) from the tree of which it is part. Attach a node to another node as its child. Given a node, find the root of the tree to which it belongs. By doing this ope
A van Emde Boas tree (Dutch pronunciation: [vɑn ˈɛmdə ˈboːɑs]), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with m-bit integer keys. It was invented by a team led by Dutch computer scientist Peter van Emde Boas in 1975.[1] It performs all operations in O(log m) time (assuming that an bit operation can be performed in cons
It’s been a while since I last posted in this series. Today we look at the disjoint-set data structure, specifically disjoint-set forests and the complementary algorithm : union-find. In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that perfor
FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。 データは以下の実験で用いた住所データを使った。 http://d.hatena.ne.jp/echizen_tm/20120215/1329315913 データサイズは ウェーブレット行列: 5, 693, 256 byte ウェーブレット木: 5, 709, 560 byteとなった。ビット列のセパレータ数が少ないぶんウェーブレット行列のほうがやや小さい。 速度についてはsample/search_fm_indexを用いてインデックスした住所データ(118,073件)をシャッフルしたものをクエリとして全件検索にかかる時間を測った。 $$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.s
以前に載せたマージソート(をベースとしたもの)をSBCL(1.0.58)にコミットしてくれたPaul Khuongさんが、こんな記事を書いていて、なるほどなー、と思ったので、表題に関係する部分を参考にさせて貰って変更前後での比較を行ったメモ。 オリジナルのマージソート まず、SBCL(1.0.58)のリストに対する破壊的マージソートの実装*1: ;; 二つのソート済みリストのマージ関数 (declaim (inline merge-lists*)) (defun merge-lists* (head list1 list2 test key &aux (tail head)) (declare (type cons head list1 list2) (type function test key) (optimize speed)) (macrolet ((merge-one (l1 l
ACM/ICPC(プログラミングコンテスト)系列の問題を解くことを目標にして,各種アルゴリズムを C++ で実装してみた.極めて意地が悪い類の問題には対応していないし,特定の入力に対して高速に動くということもない.計算量も最良とは限らない. これらを参考にする方への注意とお願い: これらの記述は正確とは限りません.参考文献を参照することを強く推奨します.間違っている場合は是非教えてください. これらのプログラムは間違っているかもしれません.各人で検証することを強く推奨します.バグがあれば是非教えてください. 分類が怪しいので,これはこっちだろう,ということがあればコメントを下さると助かります. 注意! 現在書き換え中 TODO 分類を正しく行う. 全体的に説明と使い方を詳しく. Verify していないものを Verify. ボロノイ図(いつになることやら……) 基本 テンプレート グラフ
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
*月謝3500円のそろばん塾で出たチャレンジ問題(動的計画法で) [[この記事>http://www4.atwiki.jp/fsharpmaster/pages/32.html]]の続きです。 [[Arigataさんが書かれたエントリ>http://d.hatena.ne.jp/arigata3/20120519/1337439370]]をフムフムと呼んでいて、MSのソルバに興味を持ちつつ、そもそも「部分和問題」という言葉も「ナップザック問題」という言葉も知らなかった自分の不勉強に恥じ、ちゃんと勉強しないとなぁ・・・と考えているだけの日々を送っていたのですが、何の因果か「[[アルゴリズムを学ぼう>http://www.amazon.co.jp/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%82%92%E5%AD%A6%E
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く