08/11/16 06:29:55
>>808
ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』
を満たすもののことをいう．よって．一般の木上のヒープがありうる．
例えば多分木上のヒープとしてはd分ヒープはたまに使われるし，
より一般の木上のヒープとしてはフィボナッチヒープが有名．
ただ，最もよく使われるヒープは完全二分木上のヒープで，
何も断らずにヒープと言ったときこれを指す場合も多い．
場合によっては配列実装まで含めてヒープと言う場合もあるけど，
フォーマルには構造と実装は別に考えるので，
>>808 の二分ヒープの説明は本当はちょっとよろしくない．
810:デフォルトの名無しさん
08/11/16 06:53:51
>>807
どれくらいの精度で解析すればいいの？
あと，Lameの定理の結果を用いないというのは
Lameの定理を証明して用いるのは良いということ？
それとも，フィボナッチ数で抑えること自体が禁止されるの？
811:デフォルトの名無しさん
08/11/16 09:19:57
>>810
どの程度の制度かまでは問題に書いてないので、わかりません。
Lameの定理を証明してもダメだと思います。
フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。
812:デフォルトの名無しさん
08/11/16 11:41:06
>>811
互除法のアルゴリズムを
gcd(a,b) = if b == 0 then return a else return gcd(b, a mod b)
として解析する（mod は割り算の余り）．a, b ≧ 0 の場合のみ考える．
補題．
a > b ≧ 0 について，gcd(a,b) が k (≧ 1) ステップで終わるならば
a ≧ 1.1^{k+1}, b ≧ 1.1^k が成立する．
証明．
k = 1 のときは自明．k-1 まで正しいと仮定．
gcd(a,b) が k ステップで終わるとき，
gcd(b, a mod b) は k-1 ステップで終わるので帰納法の仮定から
b ≧ 1.1^{k-1}, a mod b ≧ 1.1^k，したがって
a ≧ 1.1^k + 1.1^{k-1} = 1.1^{k-1}×2.1 ≧ 1.1^{k-1}×1.21 = 1.1^{k+1}．
系．
gcd(a,b) のステップ数は O(log min{a,b})．
証明．
a > b としてよく，log b = m とおけば補題より O(m) 回以下のステップ数で終わるため．
813:811
08/11/16 17:41:20
ありがとうございます
a ≧ 1.1^{k+1}, b ≧ 1.1^k
この式をなぜ持ち出したのかがわかりません。
あと、系の証明が補題より証明できるあたりがいまいちわかりません。
よろしければ教えてください。
814:デフォルトの名無しさん
08/11/16 20:51:27
>>813
上：なんとなく．
1.1 に必然性はなくて，1.0001^k でも 1.0000000001^k でも何でもいい．
(1+ε)^k で示せれば系が示せるので，適当に不等式が成り立ちそうな値にした．
本当に解析しようとしたらギリギリの不等式評価を作るべきなんだけど，
この場合にギリギリに評価するとフィボナッチ数が出てしまうので，
わざとガバガバに評価しているという事情がある．
下：
> できるあたりがいまいちわかりません。
そういうときは具体的にここが分からないとか言うもんだよ．
ただ，補題が少し不十分な書き方だったね．補題は
「k (≧ 1) ステップ以上かかるならば」 に置き換えてよい（同じ証明が動く）ので，
そう置き替えておいて，対偶を取ると
「a < 1.1^{k+1} もしくは b < 1.1^k ならば k ステップ未満で終わる」 になるので
b < 1.1^m なる m を見つけられれば m ステップ未満で終わる．
そのような m としては log b (の切り上げ) にでも取れば十分(log は 1.1底)．
815:811
08/11/16 21:04:38
ありがとうございます。
もう一度問題と向き合って理解を深めたいと思います。
816:びぎなぁ
08/11/19 07:05:43
>>809
返事が遅くなりました。ありがとうございました。
ところで、最小全域木を求めるクラスカル法とプリム法の概要を理解出来たのですが、
計算量のところがウェブ（ウィキとか）で調べてもよく理解できません。
（１）クラスカル法
グラフの中で一番重みの小さい辺をMSTとして加えて行く。ただしその過程でcyclicに
なってしまうような辺は加えないようにする。計算量はO(E log E)またはO(E log V)
（２）プリム法
MSTに属する頂点とそうでないものの２グループに分け、まだMSTに属していない頂点から
最もコストの安く済む頂点をMSTに付け加えて行く。計算量は３種類あるみたい。
・隣接行列、探索→O(V^2)
・２分ヒープと隣接リスト→O(E log V)（←これはO((V+E)log(V))より）
・フィボナッチヒープと隣接リスト→O(E+V log (V))
ウェブの説明を読んでもわからないということはここで教えてもらってもわからないかも知れませんが
もしわかりやすい説明とかありましたら参考に教えて欲しいです
817:デフォルトの名無しさん
08/11/19 08:22:57
>>816
アルゴリズムの計算量を評価するためには
もっと正確にアルゴリズムを述べないといけないんだけど，
あなたの説明だと，良く分からない部分が多い．
（もちろん「普通の実装」というのがあるのだけれど，
それがあなたの理解しているものと違う可能性もある）
なので，あなたが理解している形で，For やら If やらを使って
手続きが明確に分かるようにアルゴリズムを書いてくれるかな？
その計算量だったら評価するよ．
818:びぎなぁ
08/11/19 16:22:32
>>817
イントロダクショントゥアルゴリズム二版から抜粋です
---------------------------------------
MST-クラスカル（G, w）
A←0
for each vertex v∈ V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge (u, v) ∈ E, taken in nondecreasing order by weight
do if FIND-SET(u)≠FIND-SET(v)
then A←A∪{(u, v)}
UNION(u, v)
return A
---------------------------------------
MST-プリム(G, w, r)
for each u∈V[G]
do key[u]←∞
π[u]←NIL
key[r]←0
Q←V[G]
while Q≠0
do u ← EXTRACT-MIN(Q)
for each v∈Adj[u]
do if v∈Q and w(u, v) < key[v]
then π[v]←u
key[v]←w(u, v)
---------------------------------------
819:デフォルトの名無しさん
08/11/19 21:49:58
>>818
その本に計算量の説明が懇切丁寧に書いてあるよ
820:デフォルトの名無しさん
08/11/19 21:54:24
ならし解析ですね分かりません。
821:デフォルトの名無しさん
08/11/20 00:37:39
LC-Treisってどんな木なのですかね？
822:びぎなぁ
08/11/20 02:42:41
>>819
了解です！
823:びぎなぁ
08/11/20 02:46:49
「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が
正の数だった場合、ダイクストラ法は失敗することがあるか？」
あれば例を教えて欲しいです
824:デフォルトの名無しさん
08/11/20 21:21:36
「開始点から離れて行く辺」の定義が必要なんじゃね？
825:びぎなぁ
08/11/20 23:44:17
sourceのことだと思います
826:デフォルトの名無しさん
08/11/24 19:02:46
バイナリ木関連のアルゴリズム
詳細に書いてる本ってありますか？
827:デフォルトの名無しさん
08/11/24 20:00:17
>>826
詳細ってどの程度？
必要なトピックを具体的にいくつか挙げてください。
828:デフォルトの名無しさん
08/12/02 09:34:20
トポロジカルソートはなぜグラフがDAGであることが前提なのですか？
サイクリックなグラフでもソート出来ると思うのですが。
829:デフォルトの名無しさん
08/12/02 10:13:52
>>828
トポロジカルソート（トポロジカルオーダリング）をどう定義してるの？
いくつか流儀があるから君の流儀が分からないと適切には答えられない．
830:デフォルトの名無しさん
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のマーク処理をリンクの付け替えだけで全部やってるコードを見た事がある。
あれと同じようにすればいいんじゃないか。