計算アルゴリズム【�U】

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 844 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 03:53:27 ] ノイズのある入力列の中から A->B->C->A => 1 A->B->C->B => 2 A->C->C->C->D => 3 とかの並びが含まれていたら、それをパターンと識別して =>の後の値に変換する処理を書いています。 今はパターンをトライ木に登録していて速度は問題ないのですが、 共通パターンが少ないとメモリを食うのが気になります。 もう少し効率の良い方法はあるでしょうか。 パターンの候補であるかはインクリメンタルに読み取れる必要があります。 845 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 04:41:33 ] wiki見たら 基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、 トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。 だとか。もう少し見たら HAT-trie は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。 時間計算量も領域計算量もハッシュテーブルに匹敵する。 とか。 846 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 06:33:09 ] >>844 パトリシアではダメ？ 847 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 08:28:21 ] パトリシア木でもいいんですが、 何か別の方法がないか聞いて見ました。 HAT-trieは初めて聞きました。調べてみます。 848 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 12:02:22 ] >>847 自分もかなり興味があるので調べているのですが、難しいです。。。 とりあえず、HAT-trieの発案者の一人であるDr. Nikolas Askitisのホームページを張っておきます。 goanna.cs.rmit.edu.au/~naskitis/ 調べた結果を少しずつでも書いていったらうれしいです。人任せモードに入ってそばで見ております。。。 849 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 21:53:25 ] 見た目はB-trieという(B木の変形の)変形で、ノードに該当するキーの 代わりに、キーの一部の文字そのものを使い、キーの残りに共通部が なければ衝突のない小さな順序付きテーブルを作って葉に残りの 文字列を入れる。平衡木が深くなるのを避けつつ、 ハッシュ表と違い順序構造も維持できるって事でしょうかね。 テーブルの入れ方の指定とかチューニングとか書いてありますが、 実際に比較した実装も見せないで他のアルゴリズムとの比較グラフが 載ってるのは胡散臭いです。複雑さによる速度低下はありそうだし、 都合の良いデータなのかもしれません。 1つ言えることは、メモリは減るのかもしれないけど、 平衡木が絡んでくるだけでコード量は数倍に増えると思います。 今使ってるトライのコードは登録検索だけですが60行程度です。 パトリシアにするだけでコードは2倍以上に増えました。 メモリは半分以下になりますが速度は3割減ぐらいです。 850 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 02:43:00 ] とりあえず、論文を概要まで翻訳してみました。(翻訳サイトありがとう) 間違いがあるかもしれませんが。。。 ----------------------------------------------------------- HAT-trie: キャッシュを考慮したトライベースの文字列のデータ構造 Nikolas Askitis Ranjan Sinha School of Computer Science and Information Technology, RMIT University, Melbourne 3001, Australia. Email: {naskitis,rsinha}@cs.rmit.edu.au 概要 トライは文字列を扱うツリーベースの最速のデータ構造だが、メモリ食いである。 burst-trieはほとんど同じぐらい速いが、バケツの中へトライチェーンを押し込む事でメモリを節約する。 しかしながらこれは、キャッシュを考慮したアプローチではなく、現在のプロセッサでは 不十分なパフォーマンスにつながり得る。 この論文では、既存の手法とうまく組み合せたキャッシュを考慮した トライベースのデータ構造であるHAT-trieを提案する。 いくつかの現実のデータセットを使用したり、他の高性能なデータ構造と比較して性能を評価する。 ほとんどの場合、キャッシュを考慮したハッシュテーブルに匹敵するぐらいの 実行時間とメモリ使用量の改善が見られた。 HAT-trieはソート順を維持した可変長文字列を扱う最も効率的なトライベースのデータ構造と思われる。 851 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 11:22:50 ] 引き続き翻訳してみます。 初めて本格的な翻訳作業をしますがなかなか面白いですね。 段落ごとにまったりとやっていきますので。。 ---------------- 3 The HAT-trie 現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001) これらのデータ構造は検索と更新に必要な命令を最小にするので速いが とくにキャッシュを考慮しているわけではない。 我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。 852 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 11:24:46 ] 最後の「原因」は「問題」の方が良さそうです。 853 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 20:03:11 ] アクセス時にmove-to-frontする ってどういう事？ 854 名前：デフォルトの名無しさん mailto:sage [2008/12/12(金) 20:08:11 ] あ、文字列のMTFじゃなくて自己組織化探索の方か。 855 名前：デフォルトの名無しさん mailto:sage [2008/12/13(土) 01:06:00 ] 論文の英文和訳なんてこんなところでやらんでくれ。 856 名前：デフォルトの名無しさん mailto:sage [2008/12/13(土) 09:13:33 ] >>853 翻訳が怪しくなりそうなところは英単語のままにしてあります。 アクセス時にmove-to-frontするというのは良く分かりませんが、直訳ぐらいにはなってるでしょうか。 >>855 すみません。今回は翻訳は置いといて（継続！？） お詫びに、昨日お風呂の中でふと思いついたネタを投下します。 はじめに（論文っぽく） ハッシュは完全ハッシュしか良いとは思っていません。例えば、>>844でいうと 1 <= A->B->C->A 2 <= A->B->C->B 3 <= A->C->C->C->D という処理をハッシュでやると、右側を文字列として int[][][][][] pattern; pattern['A']['B']['C']['A'][0] = 1; pattern['A']['B']['C']['B'][0] = 2; pattern['A']['C']['C']['C']['D'] = 3; という感じでやります。 しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。 そこで最小完全ハッシュを考えます。最小完全ハッシュとはハッシュ値を 0からデータ数-1に割り振る事です。例えば'A'を1、'B'を2、'C'を3にする事を考えますと すぐに思いつくものはkey['A'] = 1という感じでやれば出来ます。 このまま終わればそっちのネタになってしまいますが、ここからが本題です。 最小完全ハッシュの為のキーを返す処理にただの完全ハッシュを使うのでは本末転倒ですが その処理を量子演算、量子アルゴリズムを使えば簡単に出来てしまうのではないか という事を思いつきました。ただの思いつきではなくて見込みのある思いつきだと思います。 そこで量子演算、量子アルゴリズムについて話題を振りたいと思います。（おれ誰？）あ、出掛けます。。。 857 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 04:24:47 ] ハッシュはキー全体が定まらないと使えないから>>844の条件には合わないよ 858 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 06:01:04 ] >>856 そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ！」みたいなドツボにはまるだろう。 ＞しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。 だってこの発想からだろｗ 続きはブログでやれ。ブログぐらい持ってるよな？ｗ 859 名前：デフォルトの名無しさん mailto:sage [2008/12/14(日) 11:40:59 ] ふつーにBM法？ 860 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:18:46 ] >>857 その通りでした。でも、完全ハッシュを説明する為の例なので、言いたい事が伝わればいいかなと思います。 >>858 ブログありますよ。だいぶ書いてないので、仕様で少し大きめの広告をのせられてますが。。。 >>859 BM法は今まで使う機会が無かったですが、>>844には良さそう（？）です。良く分かりませんが。 量子アルゴリズムには一匹も釣れ・・誰も反応しませんねぇ。改めてWebで調べたら思っていたのと ちょっと違う感じでしたが、少し考えを進ませました。量子アルゴリズムは厳密ではなくても高速で 結果を知りたい場合に有効らしいので、それを元に考えてみました。例えば、キーが3bitで表せるとして 101, 000, 010のデータに最小完全ハッシュを施すのに、3bitの全パターンの全並び（順列）の中から データがなるべく始めの方に固まっているパターンを見つけます。 例えば100 000 010 101 001 111 110 011 という並びは、始めの4つまでに全データが現れるので、ハッシュの大きさは4つ分ですみます。 次に、全並びに番号をつけたとしてその並びの番号を覚えます。この場合は0〜!(2^3)-1の番号をつけて974を 覚えます。そして、例えば000のキーが知りたい場合は、番号から並びをほぼ正確に復元して データのある位置がキーになり、なるべく正しい位置を探します。 この処理のどこかに量子アルゴリズムを適応できるか。あと、格納は置いときます。 翻訳>>851のつづき ------------------------------------------------------------------------------- burst-trieのボトルネックを解決する為、トライ走査のコスト(作成されるだろうトライノードの数)を かなり削減しなければならないが、より重要なのはbucketsを探すコストであるが、 それらが現在アクセスする中で最もコストのかかる要素だからである。 そのような削減はbucketsの表現をlinked listからキャッシュを考慮した巨大な配列に 変える事でしか達成できない。したがって、それはキャッシュを考慮したハッシュテーブルの bucketsの構造化を考えるとよい(Askitis & Zobel 2005)。 シンプルな配列と対照させてハッシュ配列を使う利点は、bucketsがはるかに効率的にscale muchでき、 さらに保持されるトライノード数を減らせることである。 861 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:47:32 ] >>860 ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。 862 名前：デフォルトの名無しさん mailto:sage [2008/12/15(月) 04:56:42 ] 多少自分の英語に自身があるからといって、日本人は英語が出来ないとか見下している奴だろ。そのオーラがビンビンしてるじゃんｗ なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。 863 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 12:04:51 ] >>862 から僻み野郎の気配がビンビン感じられる件 864 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 16:41:59 ] 流れはよく判らんけど訳すなら全部訳してくれると嬉しい 中途半端はよくないよ 865 名前：デフォルトの名無しさん mailto:sage [2008/12/16(火) 20:58:14 ] 全部訳してテキストか pdf にしてどこかのアップローダにあげてくれ。 多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。 866 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:29:56 ] 木構造の葉ノードをIteratorパターンで順々に得る方法を実装したいのですが、どのようにすればいいでしょうか？ ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします 現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、 もっと効率よい方法があるんじゃないのかなー？って思ったんです 867 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:44:55 ] 自分でスタック作ってそのハンドルをイテレータのインスタンスとして持ちまわる。 木構造のイテレータは全部それで実装したよ。 効率が良いとされる方法はB+木みたく葉を全部末端に集めて 線形に辿らせるぐらいしかないんじゃないの。 構造に依存するし付け替えも面倒だけど。 868 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:46:22 ] あと昔のアルゴリズム事典に紐付き2分木というのがあったな。 末端の空きノードを利用するって事だったけど忘れた。 869 名前：デフォルトの名無しさん mailto:sage [2008/12/17(水) 18:49:46 ] まあ何も考えずスタックで組んだほうが保守も楽だし、 追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。 870 名前：デフォルトの名無しさん mailto:sage [2008/12/20(土) 01:36:40 ] 昔GCのマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。 あれと同じようにすればいいんじゃないか。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef