VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
333(21): デフォルトの名無しさん [sage] 2019/02/20(水)02:40 ID:B2QSVSiS(1/5)
>>321
すべてのノードについて、左の子以下の数は、自分の数よりも小さく、
右の子以下の数は、自分の数よりも大きくなる
これは普通の2分探索木で、
C++ のSTL にある、map・set というコンテナだろ
でも皆、再帰を使って実装しているのでは？
再帰を使わない方法は、思いつかない
336: デフォルトの名無しさん [] 2019/02/20(水)04:50 ID:DVhbz9AC(2/4)
>>333-334
前回は片山のおかげで台無しだったもんな
いつもの自演乙
342(2): ピッコロ ◆YAZTByPXwc6o [] 2019/02/20(水)21:39 ID:zpD+5nAC(1/3)
>>333
∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧
＜STL！STL！STL！STL！STL！STL！STL！STL！STL！ ＞
∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨
、 、 、 、 、
/っﾉ /っﾉ /っﾉ /っﾉ /っﾉ
/ / ∧＿∧ / / ∧＿∧ / / ∧＿∧ / / ∧＿∧ / / ∧＿∧
＼＼（ ）＼＼（ ）＼＼（ ）＼＼（ ）＼＼（ ）
345: ピッコロ ◆YAZTByPXwc6o [] 2019/02/20(水)22:20 ID:zpD+5nAC(3/3)
>>333
STLでググりましたけどわけわからなすぎてむりぽ
二分探索木を実装したいんじゃないんです
二分木を数字の順番でたどって値を出力したいんです
どうかよろしくお願いいたします
346(1): 333 [sage] 2019/02/20(水)23:54 ID:B2QSVSiS(5/5)
二分木
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8
行きがけ順、通りがけ順、帰りがけ順探索[編集]
二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。
従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。
根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、
部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、
片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。
二分探索木では通りがけ順探索は、ノードを大きさ順（あるいは大きさの逆順）に調べることになる。
>>321
は、通りがけ順でしょ
ところで、ピラフ大王は、ピッコロ大魔王になったのですか？
348(1): 333 [sage] 2019/02/21(木)00:07 ID:JBRYA9bz(1/4)
通りがけ順は、左の子がある限り、ドンドン降りていく
左の子から上に上がったら、そのノードを記録して、右の子へ降りる
右の子へ降りたら、また左の子がある限り、ドンドン降りていく
350(3): 333 [sage] 2019/02/21(木)00:10 ID:JBRYA9bz(2/4)
それを再帰を使わずに実装していることなんて、あるかな？
漏れは、思いつかない
アルゴリズムのスレで聞いたら、どうかな？
354: 333 [sage] 2019/02/21(木)08:40 ID:JBRYA9bz(3/4)
順位キュー(優先度付きキュー、priority queue)は、ダイクストラ・A* で使っている。
確か、2分ヒープと同じで、最小値だけがtop に来る。
他のノードの関係は、保証されないのだったかな？
>>321
の図で説明すると、
まず、4に来るとキューに、[4, 2, 6] を追加すると、[2, 4, 6]となる
削除しないで、peek だけすると、最小は2なので、2へ行き、[1, 3] を追加すると、[1, 2, 4, 6, 3]となる
そこでpeekすると、最小は1なので、1へ行き、追加するものはないので、
1をpop して、peekすると、最小は2なので、2へ戻り、
2をpopして、peekすると、最小は3なので、3へ行き、追加するものはないので、
3をpopして、peekすると、最小は4なので、4へ戻り、追加するものはないので、
4をpopして、peekすると、最小は6なので、6へ行き、[5, 7] を追加すると、[5, 6, 7]となる
そこでpeekすると、最小は5なので、5へ行き、追加するものはないので、
5をpopして、peekすると、最小は6なので、6へ戻り、
6をpopして、peekすると、最小は7なので、7へ行き、追加するものはないので、
7をpopすると、キューが空
プログラミング・コンテスト・チャレンジブック、第2版、2012
言語は、C++で、ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる
355(1): 333 [sage] 2019/02/21(木)08:56 ID:JBRYA9bz(4/4)
2分ヒープ(BinaryHeap)は、
優先度つきキュー (順位キュー、priority queue)や、
ダイクストラ法 (Dijkstra's Algorithm)で使っているけど、
ここで、JavaScript の配列を使って、2分ヒープを作っている。
http://jsdo.it/michihito/bGH5
PushObj, PopObj を見たけど、再帰は使っていない！
追加・削除の計算量はともに、O(log n) です
確か以前も、このスレで、このアルゴリズムに改良点があるとか、ピラフに指摘されたはず
359(1): 333 [sage] 2019/02/22(金)06:28 ID:43iXBVf1(1/2)
順位キューではなく、スタックで考えてみた
>>321
の図で説明すると、
まず、4に来ると、スタックに大きい方から、[6, 4, 2] をpush する
削除しないで、末尾をpeek だけすると、最小は2なので、2へ行き、
一旦、2をpop してから、[3, 2, 1] をpushすると、[6, 4, 3, 2, 1]となる。
(一旦、2をpopして、順番を変えるのがミソ)
そこでpeekすると、最小は1なので、1へ行き、追加するものはないので、
1をpop して、peekすると、最小は2なので、2へ戻り、
2をpopして、peekすると、最小は3なので、3へ行き、追加するものはないので、
3をpopして、peekすると、最小は4なので、4へ戻り、追加するものはないので、
4をpopして、peekすると、最小は6なので、6へ行き、
一旦、6をpop してから、[7, 6, 5] をpushすると、[7, 6, 5]となる
そこでpeekすると、最小は5なので、5へ行き、追加するものはないので、
5をpopして、peekすると、最小は6なので、6へ戻り、
6をpopして、peekすると、最小は7なので、7へ行き、追加するものはないので、
7をpopすると、スタックが空
362(1): 333 [sage] 2019/02/22(金)11:33 ID:43iXBVf1(2/2)
>>360
順位キュー・スタックの、どちらで実装できたの？
漏れも、Ruby, JavaScript, Haxe あたりで書いてみようかな？
365(1): 333 [sage] 2019/02/23(土)08:10 ID:DQY5g4De(1)
良ければ、どこかで発表してください
漏れも、参考にしたいので
369(1): 333 [] 2019/03/15(金)15:40 ID:L+hp7qbL(1)
>>366
これを解析して、Ruby に変換しようとしているけど、キツイw
389: 333 [sage] 2019/03/16(土)22:17 ID:1E15fsAJ(1)
>>370-371
ピッコロ様、ありがとう。参考にします
今、rubytree gem を使えるのか、説明書を読んでいるところです
390(1): 333 [sage] 2019/03/17(日)05:15 ID:QeX4wN+m(1/4)
他にも、ruby_structures というgem もあるようです
Stack, Queue, Linked List, Binary Tree, LRU Cache, Heap, Priority Queue, Graph and Weighted Graph など、
1人でアルゴリズムの部品を作っているようです
色々と、研究してみます
しかし、ピッコロの成長力は、すごいですね！
もう漏れは、軽く抜かれていますわw
391(1): 333 [sage] 2019/03/17(日)08:07 ID:QeX4wN+m(2/4)
>>370
accessor で、インスタンス変数の読み書きを公開できます。
それと、多重代入も使えます。
inspect も再定義しておけば、p の表示をカスタマイズできます
class Tree
attr_accessor :value, :left, :right
def initialize(value, left, right)
@value, @left, @right = value, left, right
end
def inspect( ) "#{ @value } : #{ @left ? @left.value : nil } : #{ @right ? @right.value : nil }" end
end
また、class を、module で囲むのもおすすめ
module BinaryTree
class BinaryTreeNode
end
end
392(1): 333 [sage] 2019/03/17(日)08:16 ID:QeX4wN+m(3/4)
それと、parent もあっても良いかも
def initialize(val=nil, parent=nil, left_child=nil, right_child=nil)
end
396(1): 333 [sage] 2019/03/17(日)22:12 ID:QeX4wN+m(4/4)
この2分木は、同じ値が複数存在しないことが前提条件ですか？
複数あると、バグるのでしょうか？
401(3): 333 [sage] 2019/03/18(月)22:38 ID:e1XJ4IHa(1/3)
平衡2分木は基本だね
インデックスに対して、MongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しているらしいし、
Linux のプロセス・スケジューラーは、赤黒木を使っている
B TreeとB+ Treeの違い
https://christina04.hatenablog.com/entry/2017/05/17/190000
402: 333 [sage] 2019/03/18(月)22:47 ID:e1XJ4IHa(2/3)
>>401
では、全データを走査するには、B Tree よりも、B+ Tree の方が良さそう。
ただし、メモリを2倍ぐらい使いそう
それと、逆順の走査には、next pointer を双方向ポインターにする方が良さそう
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.028s