体K上の多項式環K[x]を既約でない多項式f(x)で生成されるイデアル(f(x))で割って得られる剰余環はなぜ体にならないのか
Kを体とする。K上の多項式環K[x]に対して、]がK上既約であれば、剰余環は体となる。これは代数学における極めて有名な事実だ。このようになる教科書的な説明を述べると、K上既約な多項式から生成されるイデアルは極大イデアルであり、極大イデアルによる剰余環は体になる*1から、ということになる。
しかし、ちょっと待って欲しい。多くの人はこれだけ見て「ああなるほどね」と納得するのだろうか?例えば、だとすると、これはK上既約ではないわけだが、このときが体にならないことは当然だと、直感的に理解できるだろうか?少なくとも、私はできない。
というわけで、本稿ではなぜが体にならないのかということを直感的に説明してみたいと思う。
このことを理解するために、1つ簡単だが重要な事実がある。それは「体は整域である」ということである。簡単に証明してみる。Kが体であり、かつとなるa, bが存在すると仮定する。すると、Kは体なのでaの逆元が存在する。このとき、となり、であることに矛盾する。よってKは整域である。
さて、だとすると、の元はと書ける。すると、である。この剰余環の積の演算を用いてこの元を2乗すると、となる。よって剰余環は整域ではないため、体ではない。
どうしてこんなことになってしまうのだろうか?K上の多項式をで割った余りは高々1次式であるが、は既約ではないため、1次式の積として書き表すことが出来てしまう。すると、その1次式同士を掛け合わせると、の倍数に出来てしまうのである。で割り切れる多項式はこの剰余環の零元であるため、整域ではなくなってしまうのである。
逆にf(x)が既約多項式であれば、f(x)より次元の小さいどんな多項式同士を掛けあわせてもf(x)の倍数にはならず、結果として剰余環は整域となる。これが、既約多項式で生成されるイデアルによる剰余環が体になる直感的理由である。(厳密な証明ではない。)
以上、定理が満たされないケースを深く考えてみることで、逆に定理をより深く理解することを試みた。特に代数学のように抽象的な分野では、具体例をたくさん考えて、自ら手を動かすことが理解への近道である。その手間を惜しむことなく、今後も数字と戯れていきたい。
*1:この証明は難しくはないが、ちょっとだけ複雑なので調べてみて欲しい。
ネットワークトポロジーに潜む位相空間
情報を学んだ事のある人間であれば、ネットワークトポロジーという言葉を聞いた事があるだろう。これは、ネットワーク上でサーバやスイッチ等がどのように接続されているかを示す用語である。
また、トポロジーというのは数学の位相を意味するということは、数学を深く学んでいない人でも何となく聞いた事があるだろう。
そこで思ったのだが、ネットワークトポロジーと言うからには、そこに何らかの位相空間があるはずである。しかし、いろいろ調べてみても、どうにも情報界隈でキチッと決められた位相構造の定義は無いように思われる。そもそも情報、特にネットワークを専門とする人で、位相空間をしっかり学んだことがある人は少ないような気がするし、この状況はある意味当然なのかもしれない。ただ単に、ネットワーク上でのノードの繋がり方が何となく位相空間っぽいと思った人が名付けたのかもしれない。
以上を鑑みて、ここ最近ネットワークの中にはどのような位相構造があるのかを数学的視点から真面目に考えていたのだが、考えがまとまってきたので記事にしてみたいと思う。*1
まず、ここで扱うネットワークとはどのようなものか定義する。ネットワークとは、有限なn個( )のノードを持ち、ノードの間がエッジで接続されているものであるとする。任意の2つのノードを直接つなぐエッジはあっても良いしなくても良い。また、任意の2つのエッジは、ノード以外の点で共有点を持たないこととする。1つのエッジが大きくよじれて、自分自身とクロスすることもないとする。さらに、ここでは純粋にノード間の繋がり方のみに注目したいので、全てのエッジの長さは1とする。これにより、ネットワークは距離空間となる。これはよくある議論で、ノード間のホップ数を距離とするのである。(この距離の考え方は後で拡張する。)
次に、数学における位相空間の定義に触れたいと思う。位相空間とは、ざっくり言うと「集合に対して開集合となる部分集合を定義することで作られる空間」である。開集合を定義するというのは、慣れないとちょっと不思議に思うかもしれない。ユークリッド空間では距離の概念があったから、開集合は自然に定義された。しかし、位相空間の考え方は、距離の定義されていない一般の集合に対して、逆にどのような部分集合が開集合であるかを決めてやることで、距離空間と似たような議論ができるようにするというものである。つまり、開集合さえ決まれば位相構造が決まると言っても過言ではない。
そこで、以下の2点を解決すれば、ネットワークの位相構造を決めることができる。
- ネットワークはどのような集合で表現できるか?
- ネットワークを表す集合において、どのような部分集合が開集合になるか?
まずパッと思いつくのは、i番目のノードをaiとした時、とするものである。このようにネットワークを離散的に捉えるのはよくある手法であるが、この場合、エッジはどのように表現されるのだろうか?
最初に考えたのは、開集合の決め方によってノード間の接続を表現する方法である。位相空間における開集合は、点の近傍を表していると捉えることができるので、ある点に接続されている全ての点とその点自体から成る集合を開集合とするのである。
一見するとこれは良さそうに見えるのだが、開集合の公理から、開集合同士の共通部分、および和集合も開集合になるため、ほとんどのケースでXは離散位相空間になってしまう。これでは全ての点がバラバラになってしまい、ネットワーク内の連結が表現できない。
調べてみると、エッジをノードと同じように集合の要素として扱うことを考えた人もいるようである。しかし、自分には長さを持つエッジをノードと同一視しているのがどうにも気持ち悪く、納得できなかった(追記2を参照)。興味のある方は以下を参照して頂きたい。
グラフ構造で位相空間のイメージをつかむ - Qiita
次に考えたのが、ネットワークをエッジも含めて3次元ユークリッド空間内に埋め込む方法である。ネットワークとは実際の空間にあるモノ同士の接続なのだから、3次元ユークリッド空間内にノードを表す点、及びエッジを表現する、点の間をつなぐ曲線を配置することができる。エッジの長さが全て1という制約はあるが、エッジは好きにたわませれば良いので、ノード数が有限であればこのような集合を構成することは可能である。
では、ここにどのような開集合系を定義することができるだろうか?ここで定義した集合はユークリッド空間の部分集合なので、私は最初次の定理を利用することができると考えた。
位相空間Aが集合Bを部分集合として含むとする。Aの任意の開集合Uに対して、はBの開集合となる。
一度はこれで決着かと思われたが、実はこの開集合系にはまだネットワークを表現するには不自然な点がある。例えば、以下のようにエッジがたわんだネットワークを考えよう。
ここで、点のε近傍を考えると、これは開集合である。そのため、UかつXは開集合である。しかし、そうなると以下の図の赤色で示す部分がXのε近傍となる。
ノード間の距離はエッジに沿って考えるのが自然なので、上のような集合がε近傍となるのは不自然である。
次に考えたのが、ノードを表すある点からエッジを表す曲線に沿って長さε未満の部分をε近傍とする方法である。以下に例を示す。
ここで再び開集合の公理より、開集合同士の交わりは再び開集合になるので、ノードの真ん中にポツンと開集合ができてしまう。
ここではこのような開集合も受け入れることとする。
また、(あまり意味はないが)位相空間足り得るためには、エッジの途中の点の近傍というものも考える必要がある。例えば、点とを繋ぐエッジにおいて、から距離d(d<ε)だけ離れた点を取ると、ここでのε近傍は以下のようになる。
また、もともとはノード間でしか距離は考えていなかったが、近傍を考えるためにはエッジの途中の点の間にも距離が生まれるが、これも認めることにする。
ここで考えたようなε近傍が本当に開集合かどうかを調べるのは簡単である。ネットワークの集合をXとすると、ε近傍として決めた曲線Vを薄く包み込むような3次元ユークリッド空間上の開集合Uを考えれば、は先ほど述べた定理により開集合である(追記1を参照)。
さて、先ほどからやたらとε近傍にこだわっていたわけだが、ε近傍だけが開集合ではない。しかし、距離空間において、ε近傍を全て集めたものは開基と呼ばれ、これらの和集合を全て集めたものを加えてやれば、それが開集合系を成すことが知られている。その意味で、ε近傍だけを定義すればほとんど開集合系を定めたことになる。
以上により、ひとまずネットワークを表現する集合、及びその開集合系を定めることができた。
さて、ここからは私の自己満足である。上で定義したネットワークの位相構造は、エッジがグニャグニャと(ある程度自由に)曲がることができて、どうにも汚い印象がある。例えるなら、整理されていないサーバラックの裏側を覗いたような残念な気持ちになるのである。これをもう少し"綺麗に"配線することは出来ないだろうか?
最も綺麗な配線は、全てのエッジを真っ直ぐな線分にすることである。しかし、全てのエッジの長さが1であるという制約を考えると、ノードの数が増えた場合にこれは実現不可能である。もしノード数が3つなら正三角形の、4つなら正四面体の各頂点にノードを配置することで実現できるのだが・・・
そこで考えた。次元を上げたらどうなるか?今、2次元空間では3つの点、3次元空間では4つの点を、互いに長さ1の線分で繋ぐことができるのだから、n次元空間ではn+1個の点を長さ1の線分で繋げられるのではないか?
調べてみたら、この予想はなんと正しいことがわかった。詳細な説明は以下のリンクを参照して欲しいが、ようはn次元空間での超正多面体を考えるのである。そして、その中でも全ての頂点が互いに辺で結ばれるような超正多面体はnがいくつであっても存在する。
http://eprints3.math.sci.hokudai.ac.jp/364/4/jin0804.pdf
具体的な形についても述べておく。n+1次元空間において、というn+1個の点を互いに結ぶことで、n次元の部分集合が得られる。これこそが上で述べたn次元の超正多面体となる。
この超多面体の頂点にノードを配置することで、全てのエッジを長さ1の線分として表し、かつノードも対称な形で配置できる。
さて、これで理想的なネットワークの位相構造を手に入れたのであるが、ここでやりたいことは、3次元ユークリッド空間上の汚いネットワークを、この綺麗なネットワークに対応付けることである。そうすれば、3次元ユークリッド空間上の全てのネットワークに対して標準形のようなものを与えることができる。
この対応を探すことは、まさに両者の間の位相同型写像を探すことに他ならない。位相同型写像とは、連続な全単射であり、かつ逆写像も連続であるような写像のことである。証明は省くが、何次元の空間であろうと点は点(0次元)であり、線は線(1次元)なのだから、両者が位相同型であることはほとんど明らかであろう。
以上、ネットワークトポロジーを3次元ユークリッド空間上に埋め込む形で定義し、かつその標準形を高次元のユークリッド空間上に与えた。数学を学んだことで、情報の世界で長年謎だった問題が解決され、数学を学ぶモチベーションがさらに高まった。これからも数学に強いエンジニアを目指し、日々数学を学んでいきたい。
追記1
ネットワーク集合自体はユークリッド空間に埋め込まれているとは言え、この集合上で考える距離はもはや通常の意味での距離とは異なるため、近傍もユークリッド空間とは違うものになる。そのため、ユークリッド空間の開集合との共通部分だということを利用して開集合であることを主張するのは誤りだと気づいた。素直にノード上をたどった長さを距離として、それを用いて開集合を決めるのが自然であろう。
追記2
本稿を書いてからずっと悩んでいたが、やはり離散的な構造であるグラフを連続的な空間に埋め込むというのは、なんとも美しくないような気がしてきた。悔しいが、リンクを貼った先の記事で紹介されているような位相の入れ方がよいのかもしれない。ただし、やるならとことん抽象的にやるべきである。すなわち、ノードとエッジはどちらも本質的には区別のない点であると捉え、ノードに対応する点の近傍にはそれとつながるエッジを含め、エッジに対応する点の近傍はそのエッジのみから成る集合であるとする。そうして、ノードだのエッジだのの区別がなくなった点に対して、今度は逆に開集合として自分自身だけが含まれるようなものが存在する点はエッジであり、そうでない点はノードであると考えるのである。紹介した記事とほとんど同じことを言っているようだが、ノードとエッジを本質的に区別するのは位相構造のみであるという立場を強く強調しておきたい。
*1:本記事に記載している内容は私が自力で考えて導き出したものであり、これが必ずしも正解とは限らない。そういう考え方もあるのだと思って頂ければ幸いである。
ガロアの基本定理の定性的なイメージと具体例
少し前にやっとガロア理論を学ぶことができた。ガロア理論の核となるのはガロアの基本定理である。ざっくり説明すると、L/Kが体のガロア拡大であるとき、その中間体Mに対してガロア群Gal(L/K)の部分群の中に1対1に対応するものがあるという定理である。しかも、中間体同士の包含関係と、Gal(L/K)の部分群の包含関係は互いに逆向きに対応するのである。これがこの定理の不思議なところであり、キーポイントであると思われる。
本記事ではガロアの基本定理で述べている中間体とガロア群の部分群の間の逆向きの包含関係について述べると共に、1つ具体例を出してみたいと思う。
まず、ガロア群とは何かについて簡単に述べてみる。L/Kが体のガロア拡大であるとき、K自己同型群のことをガロア群と呼び、Gal(L/K)と書く。K自己同型群は、Lに含まれる元のうちKの元を不変にするような同型の集合であり、これは自己同型群の部分群になる。
今、という体の包含関係があり、またこれに対応してガロア群の部分群の間にという包含関係が合ったとする。ここで、L, M, Kの元を変えないようなLの自己同型の集合は、それぞれどんな集合であるかを考えてみる。まずLについてであるが、Lの自己同型がLを変えないのだとすれば、それは恒等写像のみである。これはガロア群の自明な部分群である1に対応する。また、Kについて考えてみると、Kを変えないLの自己同型というのは、まさにK自己同型の定義そのものであり、それらの集合はガロア群Gal(L/K)そのものである。また、Mについては具体的にどういう体かを示していないためざっくりとしたことしか言えないが、かつであれば、Mを変えないという条件は、Lを変えないよりは緩く、Kを変えないよりは厳しいため、その数は1よりは大きく、|Gal(L/K)|よりは小さいと考えられる。そのような集合をHとすると、これはガロア群の部分群になる。
以上の考察のように、ガロア拡大の中間体の列に対して、その中間体を変えないようなLの自己同型を考えていくと、それが全てガロア群の部分群になっている。そして、サイズの大きい中間体ほど、それを変えないという条件が厳しいものとなるため、該当する自己同型の数は少なくなっていく。このようにして、中間体とそれを変えないガロア群の部分群の対応を考えると、逆向きの包含関係が見えてくるのである。これがガロアの基本定理に対する私の定性的な理解である。
ガロア拡大の中間体とガロア群の部分群の対応例
例として、ガロア拡大を考える。ここで、は1の原始5乗根である。詳細はとても書ききれないので省くが、である。演算表を以下に示す。
× | 1 | 2 | 3 | 4 |
---|---|---|---|---|
1 | 1 | 2 | 3 | 4 |
2 | 2 | 4 | 1 | 3 |
3 | 3 | 1 | 4 | 2 |
4 | 4 | 3 | 2 | 1 |
次に、このガロア群の部分群を具体的に求めてみる。ガロア群の位数が4なので、自明でない部分群の位数としてあり得るのは2のみである。そう思って上の演算表を見てみると、が部分群になっていることが分かる。
以上により、という部分群の列が得られた。これに対する中間体の列を考えるために、自明でない部分群が自己同型群としてどのように振る舞うかを考えてみる。の元はと表すことができる。の元はに作用することでを置換することになる。具体的な置換の仕方をHの元である1, 4について考えてみると、1は単位元なので恒等写像となる。一方、4はをそれぞれ4乗する操作を表すので、へと移される。指数部分が演算表の値と一致しているところがポイントである。
ここで、Hによって不変となるの中間体Mを具体的に求めてみる。上記の考察から、4による置換ではと、及びとが入れ替わることが分かる。そのため、Hの元による置換ではが変化しないことになる。今、であるため、これらについては特に考える必要がない。と置くと、と書けるため、結局が不変になることだけを考えればよい。すなわち、である。
Mをもう少し詳しく調べてみる。複素平面上での対称性を考えると、となるので、が言える。また、である。よって解と係数の関係よりを根に持つ2次多項式は以下のようになる。
よりとなる。よってだということが分かる。
これにより、ガロア拡大の中間体とガロア群の部分群の間の対応は以下のようになる。
5次方程式の可解性との関連
上の例をもう少し推し進めて、方程式の可解性との関連について考察してみる。ガロア理論の一番有名な帰結として、一般の5次方程式の解を代数的に求めることはできないというものがあるが、これはあくまで「一般の」5次方程式の話である。つまり、一部の「特殊な」5次方程式には解の公式が存在するのである。そしてガロア理論の真髄は、ある特殊な5次方程式に解の公式があるかどうかが、その方程式の最小分解体への拡大に対するガロア群が可解群かどうかを確かめることで分かるということである。
実は上の例で取り上げたという体は、という形の5次方程式の最小分解体になっている。先ほどだということに言及したが、実はさらにであることが知られている。これはアーベル群であるため、自動的に可解群となる。そのため、は代数的に解くことができる。
上記方程式の解は当然であるが、ポイントはこのように解を四則演算とべき根で示すことができる*1のは、最小分解体への拡大に対するガロア群が可解群になっているからだという理論的な説明ができることである。
もっとも、これは最初から解が分かりきっている簡単な例であり、一般にはある方程式が与えられたとき、その最小分解体を求めることは簡単ではないと思われる。
総括
以上、ガロア理論を学んで得た知見を消化するために、いろいろと遊んでみた結果を書き記した。ガロア理論を理解するのは高校生以来の夢だったので、完璧でないにせよある程度イメージをつかむことができたのは非常に嬉しい。
世の中にはガロア理論以外にもわくわくするような理論が山ほどあると思うので、そういったものをこれからも地道に学んでいきたい。
参考
- 作者: 雪江 明彦
- 出版社/メーカー: 日本評論社
- 発売日: 2010/12/07
- メディア: 単行本(ソフトカバー)
- 購入: 2人 クリック: 14回
- この商品を含むブログを見る
*1:は四則演算とべき根で表現できるため。
代数拡大、分離拡大、正規拡大そしてガロア拡大へ
今日は久々にソフトウェアエンジニアとしてではなく、日曜数学者としての記事を書いてみる。
実はここ数カ月、ずっと代数学の勉強をしている。代数学は以前雪江先生の本にチャンレンジして、見事に撃沈したので、今は2度目の挑戦中である。(懲りずにまた雪江先生の本を読んでいる。)
最近ついにガロア拡大体のあたりまで読み進めることができたため、本格的にガロア理論の中身に入る前に、一度これまでの知識をおさらいしてみようと思う。
代数学を学ぶ上での1つのマイルストーンとして、ガロア理論があることは言うまでもない。このガロア理論の主要な定理として、ガロアの基本定理が挙げられる。これは、ガロア拡大と呼ばれる体の拡大L/K*1があったときに、その中間体とガロア群の間に一対一の対応があるというものである。(私もつまみ食いした程度なので、まだこれくらいの理解度しかないのはあしからず。)
ガロアの基本定理を1つの目標と考えた時、群に対してはその部分群を、体に対してはその拡大体を考えることが重要である。今日のテーマはこの体の拡大のうち、いくつか重要なものを取り上げ、その具体例を考えることである。体とはざっくり言うと元の間に四則演算が成り立つような集合のことである。有理数全体の集合(有理数体)、実数全体の集合(実数体)、そして複素数全体の集合(複素数体)などが有名である。
代数拡大
LがKの拡大体であるとする。任意のについて、Kの元が係数となるような多項式f(x)*2があり、となるとき、LはKの代数拡大という。例えばK=、の場合を考えてみる。であるが、これを根に持つような上の多項式は存在する。例えばなんかがそうである。そのため、にを付け加えてできる体をLとすれば、これはKの代数拡大となる。こういう体のことを記号でと書いたりする。
ちなみに、を根に持つような多項式で、最高次係数が1であるもののうち、より次数が小さいものは存在しない。そのため、f(x)のことをK上の最小多項式と呼ぶ。
もう少し具体的にLについて考えてみよう。単に集合の元としてにのみを付け加えてもこれは体にならないため(例えば乗法の逆元が存在しない)、付随していろいろな元が加わる。結果として、Lは以下のように表すことができる。
代数拡大でない例も考えてみる。例えばとすると、これは代数拡大ではない。なぜなら、を根に持つ多項式は、上には作れないからである。このように、代数拡大ではない体の拡大を超越拡大と呼ぶ。
分離拡大
L/Kが代数拡大であるとする。任意のについてK上の最小多項式がKの代数閉包*3で重根を持たないとき、L/Kを分離拡大と呼ぶ。例としては、例えば上で考えたなんかは分離拡大になっている。実際、最小多項式の根はであり、重根を持たない。
この分離拡大というやつはなかなかクレイジーである。なぜなら、代数拡大のうち、分離拡大でない例を見つけることが結構難しいのだ。
体には標数という概念があり、例えば標数pの体において、任意の元をp倍すると0になる*4。それに対して、例えばのように、元を何倍しても0にはならないような体の標数は0である。そして、標数0の体の代数拡大は必ず分離拡大になる。数学にあまり馴染みのない人間にとって、標数0の体というのは難しい議論の例を考える上で重宝するのだが、これが全て分離拡大になるのだとすると、分離拡大でない体とはどういうものか想像しづらくなるのだ。
しょうがないので標数が正の体について考えてみる。標数が正の体のうち、もっともイメージしやすいのが有限体である。これはその名の通り位数が有限の体のことである。「よし、有限体の代数拡大で分離拡大でない例を探してみよう」と思ったのも束の間、実は有限体の代数拡大も必ず分離拡大となるのだ。
では一体どんな体の拡大を考えれば、分離拡大でない例を見つけることができるのか?残された道は、標数が正であり、かつ位数が無限となる体だけである。実は、このような体の拡大の中には、確かに分離拡大でないケースが存在する。一番有名な例としては、*5上の有理関数体における拡大が挙げられる。ここで、であるため、は上既約な多項式である*6。しかし、上では*7と因数分解できるため、これは分離拡大ではない。
他にも何か良い例がないかと考えたのだが、結局上記のどこの教科書にも載っていそうな例しか分からなかった。どなたか他の例をご存知であれば教えて欲しい。
正規拡大
L/Kをやはり代数拡大であるとする。正規拡大を説明するために、K上の共役について述べておく。のK上の最小多項式において、同じくもこの方程式の根だったとする。このとき、αとβはK上で共役であるという。一般に、βはα同様にLに含まれるとは限らないのだが、Lの元のK上の共役が全てLに含まれるとき、L/Kを正規拡大と呼ぶ。例としては、やはり代数拡大のところで取り上げたが挙げられる。証明はしないが、このケースではに加えたについてのみ、上の最小多項式の共役がに含まれるかを考えればよい。共役はであり、これらはともにに含まれるため、は正規拡大となる。
正規拡大でない例も、分離拡大ほどではないが私のような素人には見つけるのが難しい。教科書に載っている例としては、が挙げられる。
等間隔でない時系列データからトレンドを抽出する方法の考案
私は去年からモルモットを飼っている。毎週土曜日にケージ掃除し、その時に体重測定も行っている。体重というのはノイズが多い値である。体重測定の直前に餌をたくさん食べていれば大きめの値がでるし、逆に直前にフンをたくさんしていたりすると少なく出てしまう。そういったノイズの影響を排除するには、データを平滑化するというのが一般的である。よくやるのは、各データを前後の点と足して平均を取ったものをその点での値とする方法である。
平均値を用いた方法は簡単な割にそこそこいい感じのグラフを描くことができるのであるが、1つ問題がある。通常、時系列データといった場合には暗黙のうちにデータが等間隔で並んでいることが前提となっている。しかし、例えばモルモットの体重データの場合、土曜日が忙しいと日曜日に体重を測ったり、もしくはその週は体重を計るのをやめてしまったりするため、そうはいかない。つまり、ある点の1つ先のデータは一週間後のものだが、1つ前のものは二週間前のデータだったりすると、それらの平均を取るというのは正しくない。なぜなら、今着目している点により近いデータの方が、その点のデータとより大きな相関があるためである。このように、等間隔に並んでいない時系列データを平滑化する際には、ちょっとした工夫が必要となる。
そこで、今回はそんな工夫を1つ形として書き表してみようと思う。基本的なアイディアとしては、着目している点により近い点に対して大きな重みを与えるような形で加重平均を取るというものである。重みの与え方であるが、着目している点を中心とした正規分布を考え、その正規分布の値を利用する。こうすることで、近い点についてはある程度着目している点に影響を与えることができるし、またずっと遠い点については影響がほとんどなくなる。
また、計算のちょっとした工夫として、ある程度離れた点については、加重平均の計算に加えずとも、ほとんど影響がない。そこで、最初から計算から除外してしまっても差し支えない。これにより、計算を高速化することが可能となる。
まあこんな感じで大したアルゴリズムではないが、話を明確にするためにちょっと数理的に記述してみる。ある時刻の数列t0, t1, ... , tn-1に対して、その時の時系列データの値がy0, y1, ... , yn-1であるとする。また、平均値μ, 標準偏差σの正規分布の点xでの値をN(μ, σ, x)と表す。さらに、ある時刻tiに着目したとき、その点の前後の時間T以内にある点の添字集合をMti, Tとする。このとき、ある時点ti (0 <= i < n) について、平滑化後の値y'iは以下のようになる。
このアルゴリズムではTとσがパラメータとなり、これらの値によってグラフの様子が変化する。適用される際には、これらの値をいろいろ変えてみて、よさ気な値を選んで貰えればと思う。
template引数にコンテナを指定し、関数内でiterateする方法
自分が修士の学生でC++を書いていたとき、どうにも分からなかったことがある。それは、template関数のtemplate引数にstd::vectorなどのコンテナを指定し、関数内でそのコンテナに対してiteratorを回す方法である。当時の自分は以下のようなコードを書いており、コンパイルエラーから抜けだせなくなった。
template <class X> void iterateTest(const X& var) { // Xはstd::vectorなどのコンテナであり、以下でそのconst_iteratorにアクセスしたい for(X::const_iterator itr = std::begin(var); itr != std::end(var); itr++) { std::cout << *itr << std::endl; } }
これがコンパイルエラーになる理由が当時全く分からず、最終的に諦めてしまったのであった。
しかし、最近これに対する解答を見つけた。それが以下のコードである。
template <class X> void iterateTest(const X& var) { // X::const_iteratorの前にtypenameを付け、これが型名であることを明示 for(typename X::const_iterator itr = std::begin(var); itr != std::end(var); itr++) { std::cout << *itr << std::endl; } }
つまり、型名の前にtypenameをつければよかったのである。こうしなければならない理由は、X::const_iteratorとだけ書くと、これがXクラスのconst_iteratorという名前のstatic変数とも解釈できるなど、Xの正体がこの時点で不明であるがために、解釈が一意に定まらないためである。
さて、これでようやく長年の疑問が解決したわけだが、実はもっと簡単に書ける方法があることを発見した。それはrange based forを使う方法である。コードを以下に示す。
template <class X> void iterateTestNew(const X& var) { // range based forを使えばよりスッキリ書ける for(const auto& el : var) { std::cout << el << std::endl; } }
以前の記事でも取り上げたrange based forにまさかこんな使い道があったとは・・・C++はまだまだ知らないことが多く、いろんな場面で損をしていると思う。今後も着実に勉強を進め、効率のよいコードを書けるようになりたい。