08/12/02 13:40:19
トポロジカルソート：
（１）DAGに対して、DFSを実行する。
（２）Finishing timeの大きい順に頂点を並べる。
というものですが、いかがでしょうか。
831:デフォルトの名無しさん
08/12/02 17:21:09
>>830
それを定義に採用するなら，DAGでなくてもいいよ．
ただ，普通はそれを定義にはしない．
（それは，トポロジカルソートのひとつを求めるアルゴリズム）
普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで，
u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど，
これだと u → v → w → u なるサイクルがあると
σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する．
832:デフォルトの名無しさん
08/12/03 04:53:21
>>831
なるほど。わかったような気がします。
ありがとうございます。
833:初心者プログラマ
08/12/03 16:31:24
突然すみません。これからプログラミングで一辺に対して指定した数分の円を正六角形の中に敷き詰めるプログラムを
書こうとしています。例えば１と指定した場合は六角形内に１個の円が描かれます。例として９を指定した場合の図を
添付します。
URLﾘﾝｸ(kansai2channeler.hp.infoseek.co.jp)
聞きたいのは、nの辺の数に対してどのような法則性があるかということです。
１辺の長さを仮に１とした場合、n=1なら中心から半径√3/2の円が描かれると思いますが、
n>=2のときはどのように半径は決まって行くのでしょうか。nが何個であっても普遍的な
法則などあるのでしょうか。アホな質問だったらすみません。
834:デフォルトの名無しさん
08/12/04 00:19:45
>>833
数学板へどうぞ。
835:デフォルトの名無しさん
08/12/04 00:48:43
>>833
(√3/2)/n
836:デフォルトの名無しさん
08/12/04 01:02:08
>>833
>>835は間違い。
(√3/2)/(1+n√3)
837:デフォルトの名無しさん
08/12/04 01:02:56
>>836
さらに間違えてた。orz
(√3/2)/(1+ (n-1)√3)
838:デフォルトの名無しさん
08/12/04 14:49:49
有り難うございました。
839:デフォルトの名無しさん
08/12/07 04:37:19
ビッグ・オー記法の問題ですが、
a(n)=n^(1/2)
b(n)=10*log[2]n
どちらが大きいですか？導き方を教えて下さい。
840:デフォルトの名無しさん
08/12/07 07:34:40
>>839
十分大きな n に対しては n^{1/2} > 10 log n．
lim_{x→∞} x^{1/2} / (10 log x) をロピタルなり何なりで示して
εδで書いてε = 1 にでも取れば良い．
841:839
08/12/07 13:57:54
>>840
limがわかっていないのですが、limを使わずに導くことは可能でしょうか？
842:デフォルトの名無しさん
08/12/07 14:14:55
δε論法
843:デフォルトの名無しさん
08/12/11 01:52:02
わからないなら
a^n >> n^b >> log(n)
とでも暗記しておけ。
大概はこれだけ覚えてりゃ問題ない
844:デフォルトの名無しさん
08/12/11 03:53:27
ノイズのある入力列の中から
A->B->C->A => 1
A->B->C->B => 2
A->C->C->C->D => 3
とかの並びが含まれていたら、それをパターンと識別して
=>の後の値に変換する処理を書いています。
今はパターンをトライ木に登録していて速度は問題ないのですが、
共通パターンが少ないとメモリを食うのが気になります。
もう少し効率の良い方法はあるでしょうか。
パターンの候補であるかはインクリメンタルに読み取れる必要があります。
845:デフォルトの名無しさん
08/12/11 04:41:33
wiki見たら
基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、
トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。
だとか。もう少し見たら
HAT-trie は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。
時間計算量も領域計算量もハッシュテーブルに匹敵する。
とか。
846:デフォルトの名無しさん
08/12/11 06:33:09
>>844
パトリシアではダメ？
847:デフォルトの名無しさん
08/12/11 08:28:21
パトリシア木でもいいんですが、
何か別の方法がないか聞いて見ました。
HAT-trieは初めて聞きました。調べてみます。
848:デフォルトの名無しさん
08/12/11 12:02:22
>>847
自分もかなり興味があるので調べているのですが、難しいです。。。
とりあえず、HAT-trieの発案者の一人であるDr. Nikolas Askitisのホームページを張っておきます。
URLﾘﾝｸ(goanna.cs.rmit.edu.au)
調べた結果を少しずつでも書いていったらうれしいです。人任せモードに入ってそばで見ております。。。
849:デフォルトの名無しさん
08/12/11 21:53:25
見た目はB-trieという(B木の変形の)変形で、ノードに該当するキーの
代わりに、キーの一部の文字そのものを使い、キーの残りに共通部が
なければ衝突のない小さな順序付きテーブルを作って葉に残りの
文字列を入れる。平衡木が深くなるのを避けつつ、
ハッシュ表と違い順序構造も維持できるって事でしょうかね。
テーブルの入れ方の指定とかチューニングとか書いてありますが、
実際に比較した実装も見せないで他のアルゴリズムとの比較グラフが
載ってるのは胡散臭いです。複雑さによる速度低下はありそうだし、
都合の良いデータなのかもしれません。
1つ言えることは、メモリは減るのかもしれないけど、
平衡木が絡んでくるだけでコード量は数倍に増えると思います。
今使ってるトライのコードは登録検索だけですが60行程度です。
パトリシアにするだけでコードは2倍以上に増えました。
メモリは半分以下になりますが速度は3割減ぐらいです。
850:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/12/12 11:22:50
引き続き翻訳してみます。
初めて本格的な翻訳作業をしますがなかなか面白いですね。
段落ごとにまったりとやっていきますので。。
----------------
3 The HAT-trie
現在可変長文字列を扱う(格納、検索)利用可能な最も速いデータ構造はburst-trieと
アクセス時にmove-to-frontするチェーンハッシュテーブルである。(Zobel et al. 2001)
これらのデータ構造は検索と更新に必要な命令を最小にするので速いが
とくにキャッシュを考慮しているわけではない。
我々は資料からlinked lists(bucketsやchainsとしてそれぞれ利用される)が原因である事を知っている。
852:デフォルトの名無しさん
08/12/12 11:24:46
最後の「原因」は「問題」の方が良さそうです。
853:デフォルトの名無しさん
08/12/12 20:03:11
アクセス時にmove-to-frontする
ってどういう事？
854:デフォルトの名無しさん
08/12/12 20:08:11
あ、文字列のMTFじゃなくて自己組織化探索の方か。
855:デフォルトの名無しさん
08/12/13 01:06:00
論文の英文和訳なんてこんなところでやらんでくれ。
856:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/12/14 04:24:47
ハッシュはキー全体が定まらないと使えないから>>844の条件には合わないよ
858:デフォルトの名無しさん
08/12/14 06:01:04
>>856
そんなこと普通に勉強してれば思いつく程度だし、第一そのアプローチだと「神は存在するんだ！」みたいなドツボにはまるだろう。
＞しかし、たった5文字でint * 256^5=int * 1099511627776Byteのメモリを使います。
だってこの発想からだろｗ
続きはブログでやれ。ブログぐらい持ってるよな？ｗ
859:デフォルトの名無しさん
08/12/14 11:40:59
ふつーにBM法？
860:デフォルトの名無しさん
08/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:デフォルトの名無しさん
08/12/15 04:47:32
>>860
ここに長文を置かずにBlogに置いて、ここから誘導するようにすると喜ばれるでしょう。
862:デフォルトの名無しさん
08/12/15 04:56:42
多少自分の英語に自身があるからといって、日本人は英語が出来ないとか見下している奴だろ。そのオーラがビンビンしてるじゃんｗ
なんつーか、層化みたいな新興宗教の奴らと同じなんだよね。
863:デフォルトの名無しさん
08/12/16 12:04:51
>>862 から僻み野郎の気配がビンビン感じられる件
864:デフォルトの名無しさん
08/12/16 16:41:59
流れはよく判らんけど訳すなら全部訳してくれると嬉しい
中途半端はよくないよ
865:デフォルトの名無しさん
08/12/16 20:58:14
全部訳してテキストか pdf にしてどこかのアップローダにあげてくれ。
多くの人は途中経過に興味はないだろうし、俺は結果にも興味は無い。
866:デフォルトの名無しさん
08/12/17 18:29:56
木構造の葉ノードをIteratorパターンで順々に得る方法を実装したいのですが、どのようにすればいいでしょうか？
ただし、各ノードは子ノードだけ持っていて親ノードや兄弟ノードに関する情報は持ってないものとします
現在考えているのは、Iteratorの内部に現在たどっているノードをスタックで保持するってかんじなんですが、
もっと効率よい方法があるんじゃないのかなー？って思ったんです
867:デフォルトの名無しさん
08/12/17 18:44:55
自分でスタック作ってそのハンドルをイテレータのインスタンスとして持ちまわる。
木構造のイテレータは全部それで実装したよ。
効率が良いとされる方法はB+木みたく葉を全部末端に集めて
線形に辿らせるぐらいしかないんじゃないの。
構造に依存するし付け替えも面倒だけど。
868:デフォルトの名無しさん
08/12/17 18:46:22
あと昔のアルゴリズム事典に紐付き2分木というのがあったな。
末端の空きノードを利用するって事だったけど忘れた。
869:デフォルトの名無しさん
08/12/17 18:49:46
まあ何も考えずスタックで組んだほうが保守も楽だし、
追加や削除で余計なコストも掛からないから速度も大して変わらないと思うけどね。
870:デフォルトの名無しさん
08/12/20 01:36:40
昔GCのマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。
あれと同じようにすればいいんじゃないか。