プチコン 非公式コミュニティ
トピック
こういち
◆ou0jbJnEJ0Kb
2018/1/10 18:03
2018/1/10 18:03
質問
FFT、ダイクストラ法などの使い方を教えてください。
題の通りです。
FFTは何をする関数なのかはなんとなく分かってるのですが、引数の入出力が何を意味するのかあと一歩のところで分かりません。窓関数値に関しては何のことやらさっぱりです。
誰か教えていただけないでしょうか。
FFTは何をする関数なのかはなんとなく分かってるのですが、引数の入出力が何を意味するのかあと一歩のところで分かりません。窓関数値に関しては何のことやらさっぱりです。
誰か教えていただけないでしょうか。
コメント
こういち
2018/1/10 18:12
◆ou0jbJnEJ0Kb
とりあえず自分がどこまで分かってるかコメントに書いていきます。
・FFTとは波形を正弦波の成分に分解する関数である。
・入出力は複素数配列。
・入出力の配列はすべて同じで、1<<nで表せる要素数でなければならない。
間違いや、もっと分かりやすい言い回しなど気になった点があれば、指摘
してくださるとありがたいです。
・FFTとは波形を正弦波の成分に分解する関数である。
・入出力は複素数配列。
・入出力の配列はすべて同じで、1<<nで表せる要素数でなければならない。
間違いや、もっと分かりやすい言い回しなど気になった点があれば、指摘
してくださるとありがたいです。
こういち
2018/1/10 18:22
◆ou0jbJnEJ0Kb
分からない点
①出力の配列をr[],i[]としたときr[n],i[n]は第n調波成分の情報を表している…という認識で合ってますか？
②入力の配列は波形の瞬時値を表している…という認識で合ってますか？
①出力の配列をr[],i[]としたときr[n],i[n]は第n調波成分の情報を表している…という認識で合ってますか？
②入力の配列は波形の瞬時値を表している…という認識で合ってますか？
みなつ
2018/1/10 19:03
◆hJTkStjweib1
あってると思います(≧∇≦)b
①について、入力配列の大きさがnだったとすると、出力には
r[0],i[0] 直流成分
r[1],i[1] １波長がn要素の波（配列内に波が１つだけ収まる）の成分
r[2],i[2] １波長がn/2要素の波（配列内に波が２つ収まる）の成分
r[3],i[3] １波長がn/3要素の波（配列内に波が３つ収まる）の成分
・・・
r[n/2],i[n/2] １波長が2要素の波（配列内に波がn/2収まる）の成分。（１波長が２要素なので、これが最高周波数）
が入っております！
①について、入力配列の大きさがnだったとすると、出力には
r[0],i[0] 直流成分
r[1],i[1] １波長がn要素の波（配列内に波が１つだけ収まる）の成分
r[2],i[2] １波長がn/2要素の波（配列内に波が２つ収まる）の成分
r[3],i[3] １波長がn/3要素の波（配列内に波が３つ収まる）の成分
・・・
r[n/2],i[n/2] １波長が2要素の波（配列内に波がn/2収まる）の成分。（１波長が２要素なので、これが最高周波数）
が入っております！
こういち
2018/1/10 19:20
◆ou0jbJnEJ0Kb
回答ありがとうございまっす。合ってるんですね。安心しました。
続けて質問します。
③出力の成分は大きさがsqr(r[n]*r[n]+i[n]*i[n]),位相差がatan(i[n],r[n])のベクトルという認識で合ってますか？
④一番の疑問。入力の配列が瞬時値を表しているなら第四引数の入力配列の虚部って何なん？
続けて質問します。
③出力の成分は大きさがsqr(r[n]*r[n]+i[n]*i[n]),位相差がatan(i[n],r[n])のベクトルという認識で合ってますか？
④一番の疑問。入力の配列が瞬時値を表しているなら第四引数の入力配列の虚部って何なん？
みなつ
2018/1/10 22:12
◆hJTkStjweib1
ﾊｯ∑(ﾟДﾟ〃)
こっちにも書いておきます！
③あってます(≧∇≦)b
④は私も分からないのですが、逆変換を考ると
逆変換後の実部=r[n]*cos+i[n]*sin
逆変換後の虚部=r[n]*sin+i[n]*cos
となるので、逆変換後の実部と虚部は、常に「90度位相がズレただけの関係」になるみたいですにゃ！
ということは、例えば入力の実部と虚部に無関係な（90度位相がズレただけではない）信号を入れてFFTすると、逆変換で元の波形には戻らない（実部と虚部が、90度位相がズレただけの波形になっちゃう）ようですね～（´･ω･`）
なお、入力の「虚部だけ」に信号を入れてFFTすれば、逆変換したとき、９０度位相がズレた元の波形に戻りますにゃ～
こっちにも書いておきます！
③あってます(≧∇≦)b
④は私も分からないのですが、逆変換を考ると
逆変換後の実部=r[n]*cos+i[n]*sin
逆変換後の虚部=r[n]*sin+i[n]*cos
となるので、逆変換後の実部と虚部は、常に「90度位相がズレただけの関係」になるみたいですにゃ！
ということは、例えば入力の実部と虚部に無関係な（90度位相がズレただけではない）信号を入れてFFTすると、逆変換で元の波形には戻らない（実部と虚部が、90度位相がズレただけの波形になっちゃう）ようですね～（´･ω･`）
なお、入力の「虚部だけ」に信号を入れてFFTすれば、逆変換したとき、９０度位相がズレた元の波形に戻りますにゃ～
こういち
2018/1/10 22:16
◆ou0jbJnEJ0Kb
じゃあもう一個の質問もこっちに書いておきます。
③の式で出てきた大きさって実効値ですよね？
③の式で出てきた大きさって実効値ですよね？
みなつ
2018/1/10 22:22
◆hJTkStjweib1
たんじぇ
2018/1/11 10:49
◆WDmFkVwZ4yMl
ダイクストラ（経路探索）と A*(A-star)のほうもあわせて実装コード置いておきますね。
https://qiita.com/edo_m18/items/0588d290a19f2afc0a84
https://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7
https://github.com/mburst/dijkstras-algorithm
おなじような経路検索に「スパニングツリープロトコル(STP)」「高速スパニングツリープロトコル(RSTP)」があるのでこちらも参考程度に。
（ツリー構造を作るまでが経路探索で、全体が管理するのではなくてノード(L3 switch)ごとが隣のノードとの通信で接続や経路を管理してる動作）
経路探索は、基本的にはノード（頂点）から別のノードに行くまでにどのくらいのコスト（距離、時間）がかかるかを求めることだけど、
BASICだとなかなか実装コードが無いのと、扱うデータの構造体をどんなふうに配列で作るかで作り方が変わってきそうな感じです。
https://qiita.com/edo_m18/items/0588d290a19f2afc0a84
https://qiita.com/2dgames_jp/items/f29e915357c1decbc4b7
https://github.com/mburst/dijkstras-algorithm
おなじような経路検索に「スパニングツリープロトコル(STP)」「高速スパニングツリープロトコル(RSTP)」があるのでこちらも参考程度に。
（ツリー構造を作るまでが経路探索で、全体が管理するのではなくてノード(L3 switch)ごとが隣のノードとの通信で接続や経路を管理してる動作）
経路探索は、基本的にはノード（頂点）から別のノードに行くまでにどのくらいのコスト（距離、時間）がかかるかを求めることだけど、
BASICだとなかなか実装コードが無いのと、扱うデータの構造体をどんなふうに配列で作るかで作り方が変わってきそうな感じです。
こういち
2018/1/24 7:02 ネタバレ
◆ou0jbJnEJ0Kb
こういち
2019/4/20 15:18
◆ou0jbJnEJ0Kb
ダイクストラ…懐かしい。
データは隣接行列で管理するが楽そう。
フィボナッチヒープをプチコンで実装するのは厳しそうなのでバイナリヒープが無難か…
データは隣接行列で管理するが楽そう。
フィボナッチヒープをプチコンで実装するのは厳しそうなのでバイナリヒープが無難か…
こういち
2019/5/24 8:37
◆ou0jbJnEJ0Kb
フィボナッチヒープより速いと噂のペアリングヒープ実装できたけど、バイナリヒープの方が速かったという衝撃の事実。(pushは速いけど、popが遅い。)
こういち
2019/9/29 22:06
◆ou0jbJnEJ0Kb
最強のradix heap
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります