横から失礼します。 補足として、アルゴリズムの計算量(処理時間)を把握するのにオーダー記法というものが使われ、こちらを理解するとより分かりやすいと思います。 結論から言うと、文字列の検索の方が一般的に遅くなってしまいます。 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)を比較することで処理時間の優劣がある程度わかります。 他のアルゴリズムでもオーダーが知られているものがあるため、知っていて損はないかもしれません。 色々書きましたが、動画作成・プログラミング活動を応援しています！
この人のギャグセンス最高やなあ。このエソテリックなコンテンツならではのテンポ感絶対やめないでほしい。好きな人が最後に残るから。
ちゃんと別々の考えを持った二人が話してるみたいで面白かったです。セリフを詰め詰めにして聞き逃したら巻き戻さなきゃ分からないような動画は疲れるのでこれくらいの動画が緩く見られて好きです。
コメント欄殺伐としてるなあ。まんじゅうが座布団に座ってるのがツボ。
アルゴリズム全体については特段名前は付いていないかと思いますが，
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
魔理沙のしょぼん顔かわいい
「っう」って言ってるのかな
閉じていない領域を検出するには最外周のタイルが壁でないことが前提になっているか、または名前の付いているタイルの周囲に「名前がついていない、かつ壁でないタイル」を検出したとき閉じていないと判定することが必要です
最初の例だとDの左側のタイルにも名前がついていないので閉じていない領域と判定されてしまうかと思います
ご指摘ありがとうございます。
おっしゃる通りではありますが、動画内では簡略化、かつ便宜的に「最外周の赤いパネル」を「名前がついていないパネル」として呼称しました。
つまり、『allyリストに追加する際に名前が付いていないと、何を追加するのか分からないよね、そこで躓くよね』『青いパネルは結局無視するのだから、名前の有無も無視できるよね』ということを、まんじゅうも交えて表現したかったんですが、確かに説明不足でした。申し訳ありません。
コメントありがとうございます。精進します。
昨日 [コント版] の表記を追加しました。
変な事をしたいツクール民なので助かります 参考になります
ほかの方のコメントを見て気付いた。 これMSペイントとかである「塗りつぶし」のアルゴリズムじゃないか！
うぽつです！
プログラミング頑張っててイイねd(>_･ )ｸﾞｯ!
これ4次元になると閉じた領域を検出するのむずく無いか。5次元は無理だよね(?)
多分出来ると思います もしやったら動画にしたいですね
アルゴリズムに関してはからきしだけど、色を用いた分割統合法でも閉領域の検出はできそう
よく分からんが領域は外からの攻撃に弱いぞ！
なんか悲しいコメばっかで萎えるんだが、
面白いので頑張ってください！
やばいっすよ、僕の今見てる時点で250再生っすよ？
すごいです。
改善点が洗いざらい出てくるので助かりますヨ。
それに良かれ悪かれコメントして頂けるということは、人が集まっているということなので！
賑やかでうれしいです。昔活動していた頃は１ケタ再生が並でしたから。
Seed Fillアルゴリズム、あるいはFlood Fillアルゴリズムと呼ばれるものの一種ではないでしょうか？
このアルゴリズムは「シード」を起点とする塗りつぶしのためのアルゴリズムですが、左上から順番にシードを置いて走査すると動画で紹介しているのと同じ動きになるかと思います。
なるほど、つまり私はggrniksではありますが、既存の機能を持つアルゴリズムを発想する程度の能力は持ち合わせている と… (｀・ω・´) + ｷﾘｯ
自分の良さを再発見させて頂きました。情報のご提供、並びに丁寧なコメントに、心から感謝致します。
9:22 実際のソース見ると最外周でも処理は終えずに右上の連続する赤をたどってcheckedに放り込んでるね
動画の説明だと、中心付近を起点にしたとき毎回最外周まで広げてから失敗させてるように感じたけど
コメントありがとうございます。
このアルゴリズムの肝は『２つのリストを軸に簡単な３つのルールで構成される』という"考え方"であり、拙くはありますが何とかお伝え出来たかなと思っています。
しかしながら、この動画を制作する過程で完成品が「説明用に描いた画像」と「確認用に書いたソースコード」の２つに分裂し、それらが辿る道筋に食い違いが生じました。
本アルゴリズムの本質を伝えようという目的は達成しましたが、細かい部分で視聴者を惑わせてしまう結果になったことは後悔しています。申し訳ありません。
2:42 ここの古文好き
肝腎で草
UnionFindするのに比べて何か優位性があるんだろうか
まあでもこういう技巧的なのを考えるのって面白いよね
うまいこと実装すると、主さんのアルゴリズムのほうが最悪計算量がよいですよ～
まんじゅうが浮いてるよ、かわいいね。
渦巻きみたいな🌀形だとどうなんだろう？
音のない時間は動画エラーなのか分からんくなる
bgmって大事なんだな
そもそも空白の時間多すぎて見づらいのが原因だけど、、、
ヒカキンの動画参考にしてみて、視聴者を離さない。
アルゴリズムの内容と説明はよかった
ありがとうございます。
まんじゅうの瞬きで繋げたつもりでしたが、間との兼ね合いが難しいですね。
@@Takabayakinka 瞬きの動きが小さくてほとんど見えないのが問題ですよね。
quotaあたりに記事出したら受けそう
AtCoderで言うと何点の問題なんだろう
見た感じBFSが分かってて隣接する2点の条件が定義できれば解けるから、ムズめのC問題くらいだと思う
350点とか
ただの「外周をゴールとしたA*アルゴリズム」で、
単に「外周に到達しない開始地点の集合(＝閉じた領域)を求めてるだけ」じゃないの？
A*アルゴリズム、美しくてかつ機能的な、アルゴリズムの王様ですよね。あれ好きです。
ですが、果たして「外周をゴールとしたA*アルゴリズム」に名前が付いているのか？主はggrniksなので分かりかねます()
コメントありがとうございます。
囲碁とかに応用出来そう？
できそうですね… してみたくなりますね…
いずれ作ったらご紹介したく思います。
普通のBFSと同じじゃないの？
2倍速がちょうどいいねー
動画のテンポが悪すぎ。
るーいのゆっくり科学さんとかその辺りのゆっくり解説で人気の動画を見て学んでください。
今の動画スタイルでは、貴方がなにか伝えたいことがあってもほとんどの人には刺さりません。
るーいさん大好きです。見てて飽きないですし分かりやすいですよね。
果たしてあなたが「ゲームを作りたい人など」に当てはまるかどうかわかりませんが、コメントありがとうございます。アルゴリズム主体の動画なので、そこの筋が通っていれば問題は無いと判断しました。
@@Takabayakinka視聴者が「ゲームを作りたい人など」に関わらず
一般の人にも知られないと「ゲームを作りたい人など」にも十分に届かないと思います。
でも説明が始まるととても聞きやすい説明になっているなとは思います。
ね！思ったw