横から失礼します。 補足として、アルゴリズムの計算量(処理時間)を把握するのにオーダー記法というものが使われ、こちらを理解するとより分かりやすいと思います。 結論から言うと、文字列の検索の方が一般的に遅くなってしまいます。 checked、もとい「データを列状に並べた構造」での検索をjavaのString(StringBuilder.toString())クラスのcontainsで実装されているようでしたので、こちらのオーダーを調べてみました。 オラクルのjava公式ドキュメントには特に書いてなさそうでしたが、英語圏の記事を見ていると複数の記事で一般的な検索実装方法である線型探索であることが書かれています。 (記事の例：Blocks Codee "How to check if a string contains a substring in Java?", Medium "Efficient Substring Search in Java: How to Check if a String Contains a Substring") 線型探索は単純に前から調べていき、検索文字列と部分文字列が一致するかどうかを調べていく方法です。 torus711さんのおっしゃる通り、最善であれば1回の処理で、最悪の場合は文字列長程度分、この処理を繰り返す必要があります。 このような場合、オーダーをO(n)と表し、一般の場合において処理がデータ数(文字列長)に比例して増えることを表します。 一方、同じサイズの2次元配列を用意してbooleanで表す場合、検索する際に配列の該当要素[y][x]だけを見る形になります。 これは内部的に、配列のメモリ番地を直接指定して値を見る形となるため、すべての場合において処理は1回のみになります。 このような場合、オーダーをO(1)と表し、データ数(2次元配列の大きさ)に関係ない処理時間であることを表します。 オーダーは適切な関数f(n)を用いて一般にO(f(n))で表されます。このf(n)を比較することで処理時間の優劣がある程度わかります。 他のアルゴリズムでもオーダーが知られているものがあるため、知っていて損はないかもしれません。 色々書きましたが、動画作成・プログラミング活動を応援しています！
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
この人のギャグセンス最高やなあ。このエソテリックなコンテンツならではのテンポ感絶対やめないでほしい。好きな人が最後に残るから。
ちゃんと別々の考えを持った二人が話してるみたいで面白かったです。セリフを詰め詰めにして聞き逃したら巻き戻さなきゃ分からないような動画は疲れるのでこれくらいの動画が緩く見られて好きです。
皆さん、たくさんのコメント痛み入ります。こんなにいっぱい頂けるとは思っていませんでした。
全部にしっかり、失礼なく返信するのは体力的にも時間的にも難しいので、拝見したコメントにはハートを付けさせていただきます。
再生回数も３ケタが関の山と思っていました。ご視聴感謝いたします。本当にありがとうございます。
でも、アルゴリズムに関するコメントなどには、勉強もふまえてお返事するかもです。よろしくお願いします。
とても分かりやすい解説と、アルゴリズムを頭で理解するのに十分な間があってスムーズに視聴できました！
最近の動画は情報が詰まりすぎていて見ていると疲れてしまうので、長すぎるくらいの間が動画の内容と相まってちょうどよく感じました！
手きびしいコメントに負けず、タカバヤキンカさんが良いと思うスタイルで頑張ってください！
アルゴリズム全体については特段名前は付いていないかと思いますが，
ally リストが非空になってからの一連の処理（一つの連結成分を検出する部分）は通常「幅優先探索 (Breadth-First Search; BFS)」と呼ばれるものです．
他コメで A* との言及がありますが，（仮に特定のゴールが定まっていたとしても）ゴールまでの距離の下界を使っていないので A* ではないように思えます．
なお，checked をリスト（のようなもの）ではなく盤面と同じサイズの二次元 boolean 配列にすることで最悪計算量が改善されます．
リストへの存在性チェックに長さの線形時間がかかる一方で，配列の添字アクセスは定数時間なためです．
配列の確保に時間がかかるように思えますが，最悪ケースでは checked を走査するコストが支配的になります．
とても勉強になります。ありがとうございます。
動画内のプログラムではcheckedをリストではなく１行の文字列として定義し、その中から座標を検索する方法をとっています。これも配列のアクセスよりコストがかかるものなのでしょうか？
重ねて、詳細なコメントありがとうございます。
@@Takabayakinka 「リスト（のようなもの）」と謎の書き方をした部分は，「データを列状に並べた構造」というような意図でした．
こういうものから特定の値を探すのは普通にやると最悪計算量が線形時間ですが，これにはリストだけでなく，文字列や（座標自体を並べた一次元の）配列も該当します．
contains は魔法ではないので，内部的には「『この位置から始まる部分文字列は検索文字列に一致するか調べる』を開始位置毎にやる」必要が（少なくとも素朴に実装すれば）あるはずで，
検索文字列が先頭の方にあってくれないと遅いです．
毎回そんな幸運は起こらないので，ほとんどの場合で遅くなると思われます．
他方，checked を二次元配列にして，
checked[y][x] := （元のプログラムで言うところの）checked に入っていれば True，そうでないなら False
というような値を入れることにすれば（初期化時を除いて）常に定数時間で済みます．
横から失礼します。
補足として、アルゴリズムの計算量(処理時間)を把握するのにオーダー記法というものが使われ、こちらを理解するとより分かりやすいと思います。
結論から言うと、文字列の検索の方が一般的に遅くなってしまいます。
checked、もとい「データを列状に並べた構造」での検索をjavaのString(StringBuilder.toString())クラスのcontainsで実装されているようでしたので、こちらのオーダーを調べてみました。
オラクルのjava公式ドキュメントには特に書いてなさそうでしたが、英語圏の記事を見ていると複数の記事で一般的な検索実装方法である線型探索であることが書かれています。
(記事の例：Blocks Codee "How to check if a string contains a substring in Java?", Medium "Efficient Substring Search in Java: How to Check if a String Contains a Substring")
線型探索は単純に前から調べていき、検索文字列と部分文字列が一致するかどうかを調べていく方法です。
torus711さんのおっしゃる通り、最善であれば1回の処理で、最悪の場合は文字列長程度分、この処理を繰り返す必要があります。
このような場合、オーダーをO(n)と表し、一般の場合において処理がデータ数(文字列長)に比例して増えることを表します。
一方、同じサイズの2次元配列を用意してbooleanで表す場合、検索する際に配列の該当要素[y][x]だけを見る形になります。
これは内部的に、配列のメモリ番地を直接指定して値を見る形となるため、すべての場合において処理は1回のみになります。
このような場合、オーダーをO(1)と表し、データ数(2次元配列の大きさ)に関係ない処理時間であることを表します。
オーダーは適切な関数f(n)を用いて一般にO(f(n))で表されます。このf(n)を比較することで処理時間の優劣がある程度わかります。
他のアルゴリズムでもオーダーが知られているものがあるため、知っていて損はないかもしれません。
色々書きましたが、動画作成・プログラミング活動を応援しています！
@@torus711 うまく理解出来ました。丁寧なご説明に感謝いたします。
コメント欄殺伐としてるなあ。まんじゅうが座布団に座ってるのがツボ。
あふれ出る平成感…。良い〜〜〜〜〜〜
1:20
魔理沙のしょぼん顔かわいい
「っう」って言ってるのかな
いいねーこの感じ 動画投稿続けてほしいなあ
内側から見てく方法は思いつかなかった、青から周囲探索で青を繋げていって閉じたらクリアって考えてた
面白い
再生数が伸びてるわけでもない初投稿動画がおすすめに表示されるってたまにあるみたいですね
サムネでまんじゅうが座布団に座ってるの見えて再生してしまった。お茶らしきものもあるの良い。
未知と無機質さに興奮した 登録します
ほかの方のコメントを見て気付いた。 これMSペイントとかである「塗りつぶし」のアルゴリズムじゃないか！
個人的にはコードが短くなるのでDFS派。計算量は多分あんま変わりません。以下比較です。
(あってるかわからん)
BFS(幅優先探索)
・計算量はO(H+W)
・Queueを利用する。
・実装がちょっと長く、理解しにくい。
・平面グラフの最短経路長を求めるのが得意で、迷路などに使われる。
・対マンハッタン距離最強兵器。
＜使用例(多分)＞青鬼(座標平面から障害物付きで青鬼とプレイヤーの最短経路を求め、そこを移動)
DFS(深さ優先探索)
・計算量はO(H+W)
・Stackを利用する。
・実装が短いが、再帰関数嫌いな人は発狂する。
・グラフの連結や順列を求めるのが得意で、閉路の探索などに使われる。
・対Tree最強兵器。
＜使用例(多分)＞恶臭数字论证器 (なんでこれを例に出したのか･･･)
lab.magiconch.com/homo/
(「部分和問題」と呼ばれる問題の応用版。あらかじめ指定の数字（何とはいわないが）でできる数を記録しておき、そこから部分和を求める。1と10と-1が指定の数字から作れることから、すべての数が作れることを証明できる。)
うぽつです！
プログラミング頑張っててイイねd(>_･ )ｸﾞｯ!
これ4次元になると閉じた領域を検出するのむずく無いか。5次元は無理だよね(?)
多分出来ると思います もしやったら動画にしたいですね
ルール2にcheckedリスト内にある場合はリストに含めないが記載されてないのとCシャープ的には使用中のlist内データをdelした時にほぼバグるからなんとなくザワザワする
PythonやJavaだとリスト内データ弄り倒しても影響でないんだろうか
閉じていない領域を検出するには最外周のタイルが壁でないことが前提になっているか、または名前の付いているタイルの周囲に「名前がついていない、かつ壁でないタイル」を検出したとき閉じていないと判定することが必要です
最初の例だとDの左側のタイルにも名前がついていないので閉じていない領域と判定されてしまうかと思います
ご指摘ありがとうございます。
おっしゃる通りではありますが、動画内では簡略化、かつ便宜的に「最外周の赤いパネル」を「名前がついていないパネル」として呼称しました。
つまり、『allyリストに追加する際に名前が付いていないと、何を追加するのか分からないよね、そこで躓くよね』『青いパネルは結局無視するのだから、名前の有無も無視できるよね』ということを、まんじゅうも交えて表現したかったんですが、確かに説明不足でした。申し訳ありません。
コメントありがとうございます。精進します。
昨日 [コント版] の表記を追加しました。
9:22 実際のソース見ると最外周でも処理は終えずに右上の連続する赤をたどってcheckedに放り込んでるね
動画の説明だと、中心付近を起点にしたとき毎回最外周まで広げてから失敗させてるように感じたけど
コメントありがとうございます。
このアルゴリズムの肝は『２つのリストを軸に簡単な３つのルールで構成される』という"考え方"であり、拙くはありますが何とかお伝え出来たかなと思っています。
しかしながら、この動画を制作する過程で完成品が「説明用に描いた画像」と「確認用に書いたソースコード」の２つに分裂し、それらが辿る道筋に食い違いが生じました。
本アルゴリズムの本質を伝えようという目的は達成しましたが、細かい部分で視聴者を惑わせてしまう結果になったことは後悔しています。申し訳ありません。
UA-cam は どういうユーザーにこの動画を紹介したんだろうね。謎の閲覧数。
プログラミングおじさん集まりすぎでしょｗ
Seed Fillアルゴリズム、あるいはFlood Fillアルゴリズムと呼ばれるものの一種ではないでしょうか？
このアルゴリズムは「シード」を起点とする塗りつぶしのためのアルゴリズムですが、左上から順番にシードを置いて走査すると動画で紹介しているのと同じ動きになるかと思います。
なるほど、つまり私はggrniksではありますが、既存の機能を持つアルゴリズムを発想する程度の能力は持ち合わせている と… (｀・ω・´) + ｷﾘｯ
自分の良さを再発見させて頂きました。情報のご提供、並びに丁寧なコメントに、心から感謝致します。
手厳しいコメントしとるやつ動画作ったこと無い。
確かに大手と比べたら当然テンポが悪いとか粗がある。大手と比べたら当然だろ。初めての動画で、図の使い方も説明の順番もかなり練られている。テンポがどうとかは、きっと編集が慣れてきたら客観的に自分の動画を見れるようになって、そこから自分で改善点を見つけられるようになる。この人は頭が良いから絶対できる。
アルゴリズムや数学の解説系で、こういう適当な緩い感じたまらんほど好きなので絶対に続けて欲しい。応援してます。
まんじゅうが浮いてるよ、かわいいね。
なんか悲しいコメばっかで萎えるんだが、
面白いので頑張ってください！
やばいっすよ、僕の今見てる時点で250再生っすよ？
すごいです。
改善点が洗いざらい出てくるので助かりますヨ。
それに良かれ悪かれコメントして頂けるということは、人が集まっているということなので！
賑やかでうれしいです。昔活動していた頃は１ケタ再生が並でしたから。
そこまで高速化することを考えないならUnion Findを使った方が良いです
慣れない人がBFS・DFSを書くとバグらせることがあります。UFなら単純な2重ループで領域検出が可能ですし、よっぽど広い領域(マスの数が10^6以上とか)でなければUFでも遅さを感じずに実装可能です。
個人ゲーム作成のためであればUFをコピペしてから遅いと感じたら直すのをお勧めします。
変な事をしたいツクール民なので助かります 参考になります
UnionFindするのに比べて何か優位性があるんだろうか
まあでもこういう技巧的なのを考えるのって面白いよね
うまいこと実装すると、主さんのアルゴリズムのほうが最悪計算量がよいですよ～
よく分からんが領域は外からの攻撃に弱いぞ！
(◎□ ◎ ; ) < 外側からの攻撃に脆い
2:42 ここの古文好き
ルール2の一連のチェックが終わった際に、各マスが閉じた領域にいたかどうかはどうやって覚えていますか？
肝腎で草
AtCoder勢の傾向がよくわかるお手本のようなコメント欄
渦巻きみたいな🌀形だとどうなんだろう？
ただの「外周をゴールとしたA*アルゴリズム」で、
単に「外周に到達しない開始地点の集合(＝閉じた領域)を求めてるだけ」じゃないの？
A*アルゴリズム、美しくてかつ機能的な、アルゴリズムの王様ですよね。あれ好きです。
ですが、果たして「外周をゴールとしたA*アルゴリズム」に名前が付いているのか？主はggrniksなので分かりかねます()
コメントありがとうございます。
普通のBFSと同じじゃないの？
AtCoderで言うと何点の問題なんだろう
見た感じBFSが分かってて隣接する2点の条件が定義できれば解けるから、ムズめのC問題くらいだと思う
350点とか
囲碁とかに応用出来そう？
できそうですね… してみたくなりますね…
いずれ作ったらご紹介したく思います。
アルゴリズムに関してはからきしだけど、色を用いた分割統合法でも閉領域の検出はできそう
音のない時間は動画エラーなのか分からんくなる
bgmって大事なんだな
そもそも空白の時間多すぎて見づらいのが原因だけど、、、
ヒカキンの動画参考にしてみて、視聴者を離さない。
アルゴリズムの内容と説明はよかった
ありがとうございます。
まんじゅうの瞬きで繋げたつもりでしたが、間との兼ね合いが難しいですね。
@@Takabayakinka 瞬きの動きが小さくてほとんど見えないのが問題ですよね。
quotaあたりに記事出したら受けそう
2倍速がちょうどいいねー
名前のついていないタイルでも青の場合は閉じてるんじゃない?
似たご質問をされた方がいました。ですが、コピペするのも詰まらないのでお答えします。
おっしゃる通り、名前のついていないタイル "でも" 青の場合は閉じています。要するに「青ならば名前が付いていようが付いて無かろうが関係なく処理できる」ということです。
これを示唆するため、動画左上のルール項目には青のチェックが先に来るように書き、全てのルールにおいて「次へ」の命令としました。そして実際のプログラムでも上から順番に処理をするため（順次処理）、青は殆ど無視されて処理が経過します。
しかしながら、動画内にはゲームオーバーを決定するルール３をテキストとして載せていないため、かく余計な疑問を生む結果になりました。申し訳ありません。
@@Takabayakinka なるほ
動画のテンポが悪すぎ。
るーいのゆっくり科学さんとかその辺りのゆっくり解説で人気の動画を見て学んでください。
今の動画スタイルでは、貴方がなにか伝えたいことがあってもほとんどの人には刺さりません。
るーいさん大好きです。見てて飽きないですし分かりやすいですよね。
果たしてあなたが「ゲームを作りたい人など」に当てはまるかどうかわかりませんが、コメントありがとうございます。アルゴリズム主体の動画なので、そこの筋が通っていれば問題は無いと判断しました。
@@Takabayakinka視聴者が「ゲームを作りたい人など」に関わらず
一般の人にも知られないと「ゲームを作りたい人など」にも十分に届かないと思います。
でも説明が始まるととても聞きやすい説明になっているなとは思います。
ね！思ったw
そう思うのは自由だけど言い方をわかってない典型
そして他のチャンネルの名前出して批判するあたり消費豚の自覚がない豚なんだろうな