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

1 名前：デフォルトの名無しさん mailto:sage [2005/10/15(土) 20:42:23 ] 前スレ創設者 FeaturesOfTheGod ◆UdoWOLrsDM の言葉 >プログラム板の皆さん、こんにちは。 >無謀にもこんなスレを立ててみました。 >四則演算、初等関数、その他の関数の関数値を求めるアルゴリズムについての話をしましょう。 >人間にとって計算しやすい方法についても別途語ることにしましょう。 前スレ↓ pc8.2ch.net/test/read.cgi/tech/1090227743/ 804 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 08:36:21 ] >>802 その例では破綻しないぞ 805 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 11:31:33 ] >>804 kwsk 806 名前：デフォルトの名無しさん mailto:sage [2008/11/13(木) 21:00:49 ] >>802の例だとd(a, b) = 0で探索終わらね？ 正答が得られないって意味で破綻なんじゃね？ 807 名前：デフォルトの名無しさん [2008/11/14(金) 22:07:03 ] ユークリッド互除法の最悪時間計算量をLameの定理の結果を用いずに解析せよという問題がさっぱりわかりません。 ぜひ解答お願いしたいです。 スレチでしたらすみません。。 808 名前：びぎなぁ mailto:sage [2008/11/16(日) 05:22:26 ] アルゴリズムの勉強を始めたのですが、用語が色々あって混乱しています。 （どの用語がどの用語の中に含まれているのかとか） ヒープと二分ヒープという言葉があるのですが、同じ意味でしょうか？ 木構造--------二分木---------------二分探索木・・・左の子<=親<=右の子 木構造--------二分木---------------二分ヒープ・・・（１）根に最大値がくる、 　　　　　　　　　　　　　　　　　　　　　　　　　 （２）N[a],N[2a],N[2a+1]のデータでは必ずN[a]のデータが一番大きい 木構造--------二分木---------------ヒープ・・・二分ヒープと同義？ 木構造--------多分木 809 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:29:55 ] >>808 ヒープとは，木であって各頂点でヒープ条件『自分の値が子の値以上』 を満たすもののことをいう．よって．一般の木上のヒープがありうる． 例えば多分木上のヒープとしてはd分ヒープはたまに使われるし， より一般の木上のヒープとしてはフィボナッチヒープが有名． ただ，最もよく使われるヒープは完全二分木上のヒープで， 何も断らずにヒープと言ったときこれを指す場合も多い． 場合によっては配列実装まで含めてヒープと言う場合もあるけど， フォーマルには構造と実装は別に考えるので， >>808 の二分ヒープの説明は本当はちょっとよろしくない． 810 名前：デフォルトの名無しさん mailto:sage [2008/11/16(日) 06:53:51 ] >>807 どれくらいの精度で解析すればいいの？ あと，Lameの定理の結果を用いないというのは Lameの定理を証明して用いるのは良いということ？ それとも，フィボナッチ数で抑えること自体が禁止されるの？ 811 名前：デフォルトの名無しさん [2008/11/16(日) 09:19:57 ] >>810 どの程度の制度かまでは問題に書いてないので、わかりません。 Lameの定理を証明してもダメだと思います。 フィボナッチ数を用いても良いかまでもわかりませんが、使わないでできるのなら使わないで解いてもらいたいです。 812 名前：デフォルトの名無しさん mailto:sage [2008/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 mailto:sage [2008/11/16(日) 17:41:20 ] ありがとうございます a ≧ 1.1^{k+1}, b ≧ 1.1^k この式をなぜ持ち出したのかがわかりません。 あと、系の証明が補題より証明できるあたりがいまいちわかりません。 よろしければ教えてください。 814 名前：デフォルトの名無しさん mailto:sage [2008/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 mailto:sage [2008/11/16(日) 21:04:38 ] ありがとうございます。 もう一度問題と向き合って理解を深めたいと思います。 816 名前：びぎなぁ mailto:sage [2008/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 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 08:22:57 ] >>816 アルゴリズムの計算量を評価するためには もっと正確にアルゴリズムを述べないといけないんだけど， あなたの説明だと，良く分からない部分が多い． （もちろん「普通の実装」というのがあるのだけれど， 　それがあなたの理解しているものと違う可能性もある） なので，あなたが理解している形で，For やら If やらを使って 手続きが明確に分かるようにアルゴリズムを書いてくれるかな？ その計算量だったら評価するよ． 818 名前：びぎなぁ mailto:sage [2008/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 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:49:58 ] >>818 その本に計算量の説明が懇切丁寧に書いてあるよ 820 名前：デフォルトの名無しさん mailto:sage [2008/11/19(水) 21:54:24 ] ならし解析ですね分かりません。 821 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 00:37:39 ] LC-Treisってどんな木なのですかね？ 822 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:42:41 ] >>819 了解です！ 823 名前：びぎなぁ mailto:sage [2008/11/20(木) 02:46:49 ] 「有向グラフで、開始点から離れて行く辺のweightが全て負の数で、その他の全ての辺が 正の数だった場合、ダイクストラ法は失敗することがあるか？」 あれば例を教えて欲しいです 824 名前：デフォルトの名無しさん mailto:sage [2008/11/20(木) 21:21:36 ] 「開始点から離れて行く辺」の定義が必要なんじゃね？ 825 名前：びぎなぁ mailto:sage [2008/11/20(木) 23:44:17 ] sourceのことだと思います 826 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 19:02:46 ] バイナリ木関連のアルゴリズム 詳細に書いてる本ってありますか？ 827 名前：デフォルトの名無しさん mailto:sage [2008/11/24(月) 20:00:17 ] >>826 詳細ってどの程度？ 必要なトピックを具体的にいくつか挙げてください。 828 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 09:34:20 ] トポロジカルソートはなぜグラフがDAGであることが前提なのですか？ サイクリックなグラフでもソート出来ると思うのですが。 829 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 10:13:52 ] >>828 トポロジカルソート（トポロジカルオーダリング）をどう定義してるの？ いくつか流儀があるから君の流儀が分からないと適切には答えられない． 830 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 13:40:19 ] トポロジカルソート： （１）DAGに対して、DFSを実行する。 （２）Finishing timeの大きい順に頂点を並べる。 というものですが、いかがでしょうか。 831 名前：デフォルトの名無しさん mailto:sage [2008/12/02(火) 17:21:09 ] >>830 それを定義に採用するなら，DAGでなくてもいいよ． ただ，普通はそれを定義にはしない． （それは，トポロジカルソートのひとつを求めるアルゴリズム） 普通のトポロジカルソートの定義は頂点への番号付け（並び順）σで， u から v に枝があるとき σ(u) < σ(v) なるものを言うんだけど， これだと u → v → w → u なるサイクルがあると σ(u) < σ(v) < σ(w) < σ(u) で番号付けに矛盾する． 832 名前：デフォルトの名無しさん mailto:sage [2008/12/03(水) 04:53:21 ] >>831 なるほど。わかったような気がします。 ありがとうございます。 833 名前：初心者プログラマ mailto:sage [2008/12/03(水) 16:31:24 ] 突然すみません。これからプログラミングで一辺に対して指定した数分の円を正六角形の中に敷き詰めるプログラムを 書こうとしています。例えば１と指定した場合は六角形内に１個の円が描かれます。例として９を指定した場合の図を 添付します。 kansai2channeler.hp.infoseek.co.jp/cgi-bin/joyful/img/8194.zip 聞きたいのは、nの辺の数に対してどのような法則性があるかということです。 １辺の長さを仮に１とした場合、n=1なら中心から半径√3/2の円が描かれると思いますが、 n>=2のときはどのように半径は決まって行くのでしょうか。nが何個であっても普遍的な 法則などあるのでしょうか。アホな質問だったらすみません。 834 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 00:19:45 ] >>833 数学板へどうぞ。 835 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 00:48:43 ] >>833 (√3/2)/n 836 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 01:02:08 ] >>833 >>835は間違い。 (√3/2)/(1+n√3) 837 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 01:02:56 ] >>836 さらに間違えてた。orz (√3/2)/(1+ (n-1)√3) 838 名前：デフォルトの名無しさん mailto:sage [2008/12/04(木) 14:49:49 ] 有り難うございました。 839 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 04:37:19 ] ビッグ・オー記法の問題ですが、 a(n)=n^(1/2) b(n)=10*log[2]n どちらが大きいですか？導き方を教えて下さい。 840 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 07:34:40 ] >>839 十分大きな n に対しては n^{1/2} > 10 log n． lim_{x→∞} x^{1/2} / (10 log x) をロピタルなり何なりで示して εδで書いてε = 1 にでも取れば良い． 841 名前：839 mailto:sage [2008/12/07(日) 13:57:54 ] >>840 limがわかっていないのですが、limを使わずに導くことは可能でしょうか？ 842 名前：デフォルトの名無しさん mailto:sage [2008/12/07(日) 14:14:55 ] δε論法 843 名前：デフォルトの名無しさん mailto:sage [2008/12/11(木) 01:52:02 ] わからないなら a^n >> n^b >> log(n) とでも暗記しておけ。 大概はこれだけ覚えてりゃ問題ない 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