Root One

数学中心のブログです。

C++のソート

C++のソートについてまとめてみました。

ソートと重複要素削除 (外部サイト)

ソートの難しいところ

1次元のソートは簡単ですが、難しいのは多次元のソートです。

例えば、

1 7
2 3
1 2
2 7
2 2
1 3

 というデータを月順にソートすると

1 7
1 2
1 3
2 3
2 7
2 2

というような結果が得られますが、これを日にち順にソートしなおすと

1 2
2 2
1 3
2 3
1 7
2 7

 というように、月の順序まで変わってしまう可能性があります。

日付順のソートをしたい場合は、このようなことが起きてしまうとまずい

わけですが、Excelであれば、ソートの優先度を「月、日」の順に設定することが

できて、上のようなことを回避することができます。

C++では、このような優先度別ソートは、sort関数の第3引数を調整すると可能です。

sortの第3引数はどのように順序をつけるかを定める関数を指定するところになるのですが、この関数の設定法はいくつか考えられます。

今回のケースであれば、重みを付けてソートするのがおすすめです。

重みを付けるとは

「日」は最大で31にしかならないことを考慮して、

M月D日であれば

M*31+D

という値を考えるということです。(Mの重みを31倍にした.)

こうして、M*31+Dを基準にしてソートしてみると、

自動的に月が日よりも優先されてソートされることになります。

実際のコード例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MyDate {
public:
	int Month;
	int Day;
	MyDate(int month, int day) {
		Month = month;
		Day = day;
	};
	int getValue() const {
		return Month * 31 + Day;
	}
};

ostream& operator <<(ostream& ost, const MyDate& p) {
	ost <<  p.Month << "月" << p.Day << "日";
	return ost;
}

int main() {
	vector<MyDate> dates = { MyDate(1,7),MyDate(2,3),MyDate(1,2),
		                     MyDate(2,7),MyDate(2,2),MyDate(1,3) };
	cout << "ソート前のデータ" << endl;
	for (auto d : dates) {
		cout << d << endl;
	}
	sort(dates.begin(), dates.end(), [](const MyDate& d1, const MyDate& d2)-> bool {return d1.getValue() < d2.getValue(); });
	cout << "ソート後のデータ" << endl;

	for (auto d : dates) {
		cout << d << endl;
	}

}

実行結果.

 ソート前のデータ
1月7日
2月3日
1月2日
2月7日
2月2日
1月3日
ソート後のデータ
1月2日
1月3日
1月7日
2月2日
2月3日
2月7日

プログラムのポイント

ostream& operator <<(ostream& ost, const MyDate& p) {
	ost <<  p.Month << "月" << p.Day << "日";
	return ost;
}

は自作クラスのMyDateの変数をcoutで表示できるようにするもので、ここはソートには直接関係しない部分です。

今重要なのは、MyDateクラスのgetValue関数で、ここが重みを付けたデータの和を考えるものとなっています。そしてこれをもとに

sort(dates.begin(), dates.end(), [](const MyDate& d1, const MyDate& d2)-> bool {return d1.getValue() < d2.getValue(); });

でソートを昇順に行っています。

上のケースは、M月D日というものでしたが、

Y年M月D日

といったケースにも応用できます。その場合はgetValue関数を

Y*12*31 + M*31+D

と設定してソートすればOKです。(12は月の最大値.)

ただし、値が大きくなってくると、オーバーフローに気をつける必要がありそうです。

ポテトが宇宙になった話

日本でも田舎のちょっとした山に行くと、

「星ってこんなにたくさんあったのか」というほどの

満天の星の夜空を見ることができます。

かなり前に実際に見に行ったことがあるのですが、

今でも、そのときに見えた流れ星は印象に残っています。

 

ところで、次の画像は何に見えるでしょうか。

f:id:likethenovel:20200126020120j:plain

きれいな星々が見えますか?右下はオリオン座でしょうか。

結論からいうと、実はこの画像のもとはポテトでした。

f:id:likethenovel:20200126020417j:plain

ポテトから宇宙が生まれた過程

以前の記事

ライフゲーム - Root One

で扱った内容ですが、これをここでも簡単に説明します。

ライフゲームのルール

まず、平面上の正方形(セル)がそれぞれ「0か1」という状態を持っていて、

0なら白、1なら黒に対応させます。

次のセルの状態は、周囲のセルの状態によって決定します。

決定法が問題ですが、おおざっぱに言うと、

周囲に黒が多い場合や逆に少なすぎる場合、白になります。

ちょうどよいときは、現状を維持するか、黒になります。

カラー画像への適用

本題ですが、ライフゲームをカラー画像に適用していくと

どんな感じに変化していくのかということを考えたいと思います。

オリジナルルールの状態は0と1しかありませんので、

当然ながらルールを変更する必要があります。

通常のRGBで考えると、状態は(256*256*256)通りあります。

一つのピクセルの状態をRGBの和として考えることにし、

ピクセルの値の和が一定値を超えるもの」が周囲に多すぎたり

あるいは少なすぎたりする場合は、RGBの値を減少させます。

また、ちょうどよい場合は増やします。

詳しいルールはあまり重要でないので述べませんが、

このようにライフゲームのルールを少し変化させて

30サイクルほど繰り返して得られたのが上の画像になります。


ポテトが星空に変わっていく動画

さらに少しルールを変えたもの.


ポテトが星になって消えていく動画です

f:id:likethenovel:20200126180215j:plain

Note. もとはポテトです.
 

C++で驚いた話

最近C++をさわりはじめたのですが、

すこし驚いたことがあったので、メモを残しておきたいと思います。

少し驚いたコード

vector<int> v = { 1,2,3 };
for (int i = 0; i < v.size() - 4; i++) {
 cout << v[i] << endl;
 if (i == 2) break;
}

実行結果.

1
2
3

何が意外だったのか

v.size()は3なので、v.size()-4 は -1 になるように見えます。

したがって、for文の中は実行されず、何も表示されないはずです。

しかし、実行結果を見ると、中身が実行されているので

何かおかしい

となったわけです。

理由は簡単で、

v.size() は size_t 型(unsigned long long ) になってしまい、

v.size()-4 もsize_t 型になって、 size_t 型の世界の -1 と解釈されたせいです。

size_t 型の世界で -1 は、負の数を扱うことができないので、

エラーになっても良さそうですが、そうはならず、

size_t 型が扱える一番大きな数として認識されてしまうようです。

(実験した環境では2^{64}-1になりました。)

つまり、結果的に上のコードは

vector<int> v = { 1,2,3 };
for (int i = 0; i < 18446744073709551615; i++) {
 cout << v[i] << endl;
 if (i == 2) break;
}

と解釈されて実行されたということになります。

偶然ですが、この話は、まさに10adicの世界で

\[-1 = \cdots 99999 \]

が成り立つというお話ですね。 

日常生活でp-adic的な現象に出会うことはあまりないかもしれませんが、

プログラムの世界だとこのようにp-adicの世界が見え隠れすることがあるようです。

追記

上記のようなことがあるので、size_t 型から引き算するときは充分注意しなければならないようです。

そして問題は「どのように回避すべきか」ということになりますが、次のように事前に int にキャストすれば良いようです。

vector v = { 1,2,3 };
for (int i = 0; i < static_cast<int>(v.size()) - 4; i++) {
	cout << v[i] << endl;
	if (i == 2) break;
}

実行結果. (何も表示されない.)

 

2割引のお米

あけましておめでとうございます。

たいした話ではないですが、最近少し驚いた話があります。

 

近所のスーパーで、普段1780円で売っているお米があるのですが、

2280円になって20%割引になって販売されてました。

どういうこと???

となりましたが、冷静になって計算してみると、

500 円値上がりで、456円引きなので、

\[ 500 - 456 = 500 + (\cdots 9999544) = \cdots 0044= 44  \]

が差額になります。

つまり普段より、44円割高という結果でした。

(2020年に入り始めて、意味もなく、p-adicの計算をしてみました。)

PowerPoint・Wordの数式入力

数式入力といえば、LaTeX ですが、PowerPoint・Word・Excel などのオフィス製品でも、ある程度高度な数式、例えば

\[ \int_0^1 \sin x \, dx \]

のようなものは入力可能です。

高度な数式や、美しさを求めるとLaTeXになるかもしれませんが、簡単な数式であれば、手軽かつ高速に入力できるというメリットがオフィス製品にはあります。(もちろん慣れればですが。)

各オフィス製品によって動作が微妙に異なることもあるので、以下ではPowerPointを想定して説明します。

PowerPointにおける数式入力は、

「挿入」から「πの数式マーク」を選びます。

そうすると、リボン(いろいろな視覚的なボタンが並んでいる上部のところ)から直感的な数式入力が可能なのですが、しかしこの方法はスピード面では劣る方法です。

おすすめの数式入力方法

高速で数式を入力したい場合は、リボンを利用しないキーボード操作による方法をとります。

例えば、分数 \frac{1}{2} であれば

数式モードにしてから、半角で、次の4つのキーを入力します。

「1」 「/」 「2」  「スペースキー」

最後の「スペースキー」が重要で、このキーを押すことで、

1/2

という形から

\[\frac{1}{2} \]

という形に変換されます。

また、 漸化式やシグマ記号、積分などの入力もキーボード操作で入力可能です。

これらについては、次の動画で簡単にまとめてあります。


数式の高速入力

 

10adic指数関数と対数関数の意外な関係

10 adicの指数関数はべき級数

\[ e^x = \sum_{n=0}^\infty \frac{x^n}{n!}\]

と定義します。

通常の指数関数と違い、収束半径は小さく、x20 で割れないと収束しません。

ところで

10adic対数関数 - Root One

の10adicの対数表によれば

\[ \log 3 = \cdots 439314850693280080844278655220\]

であり、20 で割り切れます。したがって、

\[\exp(\log 3) \]

は計算できることになりますが、果たして 3 になるでしょうか。

実際、定義に従って\exp(\log 3) を計算してみると、期待に反して、

\[\exp(\log 3) = \cdots 587235541010744998887421\]

となってしまい、 3 に戻りません。

では、一体この右辺の値はどんな量なのかというと、証明は略しますが実は

\[ \sqrt[4]{1}=\cdots 11847003581666295807 \]

となるものをとるとき、

\[3 \cdot \sqrt[4]{1} = \cdots 587235541010744998887421\]

が成立します。つまり、

\[\exp(\log 3) = 3 \cdot \sqrt[4]{1} \]

ということになります。

本当の逆関数であれば、左辺は 3 になるはずなのですが、10adicの世界では諸事情?により、

\[ \sqrt[4]{1}=\cdots 11847003581666295807 \]

だけずれてしまうことになります。

10adic指数関数と対数関数のMaximaを用いた計算法は

10adic指数関数と対数関数(外部サイト)

にあります。

10adic対数関数

久しぶりに10 adicのお話です。

10adicの世界でも指数関数を考えることができるという話は以前していて、例えば

\[3^{1+\sqrt{1}} = 4 + 5 \sqrt{1} \]

という少し不思議な等式を紹介したこともありました。

ちょっと難しいかもしれませんが、これについては

指数関数の値 (外部サイト)

で証明しています。

今回は10adicの対数関数について考えます。

対数関数は、おそらくべき級数

\[ \log (1+x) = \sum_{n=1}^ \infty (-1)^{n-1} \frac{x^n}{n} \]

として定義するのが普通なのかもしれませんが、ここでは

\[\log x: = \lim_{|h|_{10} \to 0} \frac{x^h-1}{h}  \]

として定義することにします。こうすると

\[\log 3 = \cdots  2848576493439314850693280080844278655220\]

のように計算することができます。

もう少し詳しい議論は

10adic対数関数 (外部サイト)

にあります。そこにもありますが、10adicの対数表をここにも置いておきます。

log(1) 0
log(3) 90019823112848576493439314850693280080844278655220
log(7) 5586979560633425174395291992894902155239551280600
log(9) 80039646225697152986878629701386560161688557310440
log(11) 71106824578391282763269738035428724288142750684460
log(13) 30014769227296998141600160323009540423034697535940
log(17) 77971142260363766723683519437401987213489115656080
log(19) 59097584378015115950621606255410805879195081983780
log(21) 95606802673482001667834606843588182236083829935820
log(23) 22382897935058888051413161421448084104977268418760
log(27) 70059469338545729480317944552079840242532835965660
log(29) 97798846647728300178201206031847975543514450928020
log(31) 74644513498439453658032250654972777814723280666080
log(33) 61126647691239859256709052886122004368987029339680
log(37) 80249814295132397773550198179919992890550163533340
log(39) 20034592340145574635039475173702820503878976191160
log(41) 64745144118554374765213360801115040394662590527240
log(43) 88379482971608740644332811581651070573744432674700
log(47) 91657571987339575386944577998212108763538980023120
log(49) 11173959121266850348790583985789804310479102561200
log(51) 67990965373212343217122834288095267294333394311300
log(53) 78742320626571937991693874580140279780945101939820
log(57) 49117407490863692444060921106104085960039360639000
log(59) 91953304298845138284562302282869710563648385166140
log(61) 77359133609393162142709102476025278605993656350260
log(63) 85626625786330578161273921694281462316928108591040
log(67) 3892849449173292185569943358805830308552657324980
log(69) 12402721047907464544852476272141364185821547073980
log(71) 74693570273115371646004562312267147569354532916120
log(73) 42599555499725156685761700061195767362484368824360
log(77) 76693804139024707937665030028323626443382301965060
log(79) 33868393602704118838119506335825578450790416892720
log(81) 60079292451394305973757259402773120323377114620880
log(83) 86477922554355612298593367759952822783542760375780
log(87) 87818669760576876671640520882541255624358729583240
log(89) 19381579402760258090505675317909549813078546370360
log(91) 35601748787930423315995452315904442578274248816540
log(93) 64664336611288030151471565505666057895567559321300
log(97) 17598579544088868577383616313568648143006821543520
log(99) 51146470804088435750148367736815284449831307994900

注意:これは「10adic」の対数表です。通常の対数表ではありません。

表をよく見ると、ちゃんと

\[\log 3 + \log 7 = \log 21\]

のように対数法則も成り立っていることが読み取れます。

1の平方根

対数関数の定義から、1の平方根\omegaに対して常に

\[\log \omega = 0 \]

となります。したがって特に

\[\log (-\sqrt{1}) = 0 \]

が成立します。ここでルート1は

\[\sqrt{1} = \cdots 8213239954784512519836425781249\]

 と選んでいます。

すると

\[1+\sqrt{1} \in 10 \mathbb{Z}_{10} \]

なので、

\begin{align} 0=\log (-\sqrt{1}) &= \log (1 - (\sqrt{1}+1)) \\ &= -\sum_{n=1}^ \infty \frac{ ( \sqrt{1}+1)^n}{n}\\ &= -\sum_{n=1}^ \infty \frac{2^n}{n} \left( \frac{\sqrt{1}+1}{2}\right)^n \\ &= -\sum_{n=1}^ \infty \frac{2^n}{n} \cdot \frac{\sqrt{1}+1}{2} \end{align}

と変形できます。

つまり、

\[0= \sum_{n=1}^ \infty \frac{2^n}{n} \cdot \frac{\sqrt{1}+1}{2} \]

が得られますが、

\[\frac{\sqrt{1}+1}{2} \]

が5で無限回割れて、2では割れないことから、

\[ \sum_{n=1}^ \infty \frac{2^n}{n} \]

が無限回2で割れるようにならなければならないことが分かります。(10adicの世界で0というのは、10で無限回割れることを意味します。)

有限的な主張に言い換えれば、任意に与えられた自然数Mに対して、充分大きいNを取れば

\[ g(N):=\sum_{n=1}^N \frac{2^n}{n}\]

の分子が 2^M で割り切れるということになります。

検証

上で定義したg(N) がどれくらい2で割れるのか実験します。

\[ g(1) = 2, \quad g(2) = 2 + \frac{2^2}{2} = 4 \]

は簡単に計算でき、g(1) は2で1回、g(2) は2で回割れることがわかります。次は

\[g(3) = 4 + \frac{2^3}{3} =\frac{20}{3}  \]

となりますが、これは2で2回しか割れません。次は

\[g(4)=\frac{32}{3} \]

となり、急に2で5回割れるようになります。さらに計算すると

\[g(5)=\frac{256}{15}\]

となり、2で8回割れるようになります。勢いがついてきたような気がしますが、

\[g(6) = \frac{416}{15}\]

の分子は2で5回しか割れません。次も

\[g(7) =\frac{4832}{105} \]

で分子はやはり、2で5回しか割れません。こうなると主張自体を疑ってしまいますが、次を計算すると

\[g(8) = \frac{8192}{105}\]

となり、分子が2で13回割れるようになります。(この場合、分子はちょうど 2^{13} となっています。)

さらに計算していくと、

\[ g(30) = \frac{10808563553590575104}{145568097675}\]

となり、分子は2で27回割れます。

これくらい計算すると、主張の妥当性も感じられるのではないかと思います。

まとめ

10adic対数関数を考えることで、ダイレクトに証明するのは難しそうな次の主張

\[\sum_{n=1}^N \frac{2^n}{n}\]

を既約分数でまとめた時、分子を望むだけ2で割れるようにNを取ることができる。

を得ることができました。

ちなみにこのような議論は10adicではなく、通常「2adic」の世界でなされるもので、p進界隈では結構有名な話のようです。

追記

いろいろ実験していたところ

予想

\[{\rm ord}_{2} \left( g(2^n) \right)  = 2^n-2+2n \quad (n \geq 4)  \]

を得ました。(左辺の記号{\rm ord}_{2}2 で何回われるかというものです.)

一般的な評価としては

\[{\rm ord}_{2} \left( g(n) \right) \geq n+1 - \log_2 (n+1 )  \]

くらいは言えて、これから

定理

\[{\rm ord}_{2} \left( g(2^n-1) \right)  = 2^n - n \quad (n \geq 1)  \]

は言える模様です。