VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)

VBSで便利なプログラムを作れスレ 2 http://mevius.5ch.net/test/read.cgi/tech/1539439008/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

333: デフォルトの名無しさん [sage] 2019/02/20(水) 02:40:36.02 ID:B2QSVSiS >>321 すべてのノードについて、左の子以下の数は、自分の数よりも小さく、 右の子以下の数は、自分の数よりも大きくなる これは普通の2分探索木で、 C++ のSTL にある、map・set というコンテナだろ でも皆、再帰を使って実装しているのでは？ 再帰を使わない方法は、思いつかない http://mevius.5ch.net/test/read.cgi/tech/1539439008/333

336: デフォルトの名無しさん [] 2019/02/20(水) 04:50:23.34 ID:DVhbz9AC >>333-334 前回は片山のおかげで台無しだったもんな いつもの自演乙 http://mevius.5ch.net/test/read.cgi/tech/1539439008/336

342: ピッコロ ◆YAZTByPXwc6o [] 2019/02/20(水) 21:39:37.53 ID:zpD+5nAC >>333 　　　∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧∧ 　＜STL！STL！STL！STL！STL！STL！STL！STL！STL！　＞ 　　∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨∨ 　　　 、　　　　　　 　、　　　　　　　　、　　　　　　 、　　　　　　　 、 　 /っﾉ　　　　　　/っﾉ　　　　　　/っﾉ　　　　　/っﾉ　　　　　　/っﾉ 　/ /　 ∧＿∧ / /　 ∧＿∧　/ /　 ∧＿∧ / /　 ∧＿∧ / /　 ∧＿∧ 　＼＼（　　　　）＼＼（　　　　）＼＼（　　　　）＼＼（　　　　）＼＼（　　　　） http://mevius.5ch.net/test/read.cgi/tech/1539439008/342

345: ピッコロ ◆YAZTByPXwc6o [] 2019/02/20(水) 22:20:00.76 ID:zpD+5nAC >>333 STLでググりましたけどわけわからなすぎてむりぽ 二分探索木を実装したいんじゃないんです 二分木を数字の順番でたどって値を出力したいんです どうかよろしくお願いいたします http://mevius.5ch.net/test/read.cgi/tech/1539439008/345

346: 333 [sage] 2019/02/20(水) 23:54:30.57 ID:B2QSVSiS 二分木 https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8 行きがけ順、通りがけ順、帰りがけ順探索[編集] 二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。 従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。 根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、 部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、 片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。 二分探索木では通りがけ順探索は、ノードを大きさ順（あるいは大きさの逆順）に調べることになる。 >>321 は、通りがけ順でしょ ところで、ピラフ大王は、ピッコロ大魔王になったのですか？ http://mevius.5ch.net/test/read.cgi/tech/1539439008/346

348: 333 [sage] 2019/02/21(木) 00:07:47.86 ID:JBRYA9bz 通りがけ順は、左の子がある限り、ドンドン降りていく 左の子から上に上がったら、そのノードを記録して、右の子へ降りる 右の子へ降りたら、また左の子がある限り、ドンドン降りていく http://mevius.5ch.net/test/read.cgi/tech/1539439008/348

350: 333 [sage] 2019/02/21(木) 00:10:49.00 ID:JBRYA9bz それを再帰を使わずに実装していることなんて、あるかな？ 漏れは、思いつかない アルゴリズムのスレで聞いたら、どうかな？ http://mevius.5ch.net/test/read.cgi/tech/1539439008/350

354: 333 [sage] 2019/02/21(木) 08:40:37.72 ID:JBRYA9bz 順位キュー(優先度付きキュー、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やシミュレーションゲームの参考になる http://mevius.5ch.net/test/read.cgi/tech/1539439008/354

355: 333 [sage] 2019/02/21(木) 08:56:17.37 ID:JBRYA9bz 2分ヒープ(BinaryHeap)は、 優先度つきキュー (順位キュー、priority queue)や、 ダイクストラ法 (Dijkstra's Algorithm)で使っているけど、 ここで、JavaScript の配列を使って、2分ヒープを作っている。 http://jsdo.it/michihito/bGH5 PushObj, PopObj を見たけど、再帰は使っていない！ 追加・削除の計算量はともに、O(log n) です 確か以前も、このスレで、このアルゴリズムに改良点があるとか、ピラフに指摘されたはず http://mevius.5ch.net/test/read.cgi/tech/1539439008/355

359: 333 [sage] 2019/02/22(金) 06:28:37.54 ID:43iXBVf1 順位キューではなく、スタックで考えてみた >>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すると、スタックが空 http://mevius.5ch.net/test/read.cgi/tech/1539439008/359

362: 333 [sage] 2019/02/22(金) 11:33:24.78 ID:43iXBVf1 >>360 順位キュー・スタックの、どちらで実装できたの？ 漏れも、Ruby, JavaScript, Haxe あたりで書いてみようかな？ http://mevius.5ch.net/test/read.cgi/tech/1539439008/362

365: 333 [sage] 2019/02/23(土) 08:10:07.72 ID:DQY5g4De 良ければ、どこかで発表してください 漏れも、参考にしたいので http://mevius.5ch.net/test/read.cgi/tech/1539439008/365

369: 333 [] 2019/03/15(金) 15:40:19.86 ID:L+hp7qbL >>366 これを解析して、Ruby に変換しようとしているけど、キツイw http://mevius.5ch.net/test/read.cgi/tech/1539439008/369

389: 333 [sage] 2019/03/16(土) 22:17:00.89 ID:1E15fsAJ >>370-371 ピッコロ様、ありがとう。参考にします 今、rubytree gem を使えるのか、説明書を読んでいるところです http://mevius.5ch.net/test/read.cgi/tech/1539439008/389

390: 333 [sage] 2019/03/17(日) 05:15:05.97 ID:QeX4wN+m 他にも、ruby_structures というgem もあるようです Stack, Queue, Linked List, Binary Tree, LRU Cache, Heap, Priority Queue, Graph and Weighted Graph など、 1人でアルゴリズムの部品を作っているようです 色々と、研究してみます しかし、ピッコロの成長力は、すごいですね！ もう漏れは、軽く抜かれていますわw http://mevius.5ch.net/test/read.cgi/tech/1539439008/390

391: 333 [sage] 2019/03/17(日) 08:07:24.60 ID:QeX4wN+m >>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 http://mevius.5ch.net/test/read.cgi/tech/1539439008/391

392: 333 [sage] 2019/03/17(日) 08:16:52.39 ID:QeX4wN+m それと、parent もあっても良いかも def initialize(val=nil, parent=nil, left_child=nil, right_child=nil) end http://mevius.5ch.net/test/read.cgi/tech/1539439008/392

396: 333 [sage] 2019/03/17(日) 22:12:01.47 ID:QeX4wN+m この2分木は、同じ値が複数存在しないことが前提条件ですか？ 複数あると、バグるのでしょうか？ http://mevius.5ch.net/test/read.cgi/tech/1539439008/396

401: 333 [sage] 2019/03/18(月) 22:38:04.62 ID:e1XJ4IHa 平衡2分木は基本だね インデックスに対して、MongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しているらしいし、 Linux のプロセス・スケジューラーは、赤黒木を使っている B TreeとB+ Treeの違い https://christina04.hatenablog.com/entry/2017/05/17/190000 http://mevius.5ch.net/test/read.cgi/tech/1539439008/401

402: 333 [sage] 2019/03/18(月) 22:47:32.29 ID:e1XJ4IHa >>401 では、全データを走査するには、B Tree よりも、B+ Tree の方が良さそう。 ただし、メモリを2倍ぐらい使いそう それと、逆順の走査には、next pointer を双方向ポインターにする方が良さそう http://mevius.5ch.net/test/read.cgi/tech/1539439008/402

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.027s