『Order』について
目次
『Order』について
みなさんは、『Order』という単語をどれほど知っていますでしょうか?
いろいろな分野で Order という言葉が使われますが、どの分野でもその重要さは群を抜いています。
ここでは、私が知っている Order について話したいと思います。
物理学において
物理学において、『そのオーダーはどれくらい?』 といった言葉が交わされます。 工学においても同様です。
これは、英語における『in the order of...』の省略語とされています。
意味としては、『細かい数字はおいておいて、何桁くらいの数字?』 という意味で使われます。
義務教育における算数では、計算は数字を全て計算する必要があります。 例えば、 『0.123m × 456m』 の答えは、 『56.088m 2 』 であり、それ以外はありません。
しかし、物理学における計算は違います。
計算式は理論から自分で導くものであり、式が間違えていることが多い分野です。 また、数値も実測値であることが多く、学校の勉強のように計算しやすい数字が当たっているわけでもありません。 (付記としてはこの場合の答えは 『56.1m 2 』 であり、小さい数字に意味がなくなります。 )
例えば、 『0.123m × 456m』 なのか、 『0.123m + 456m』 なのか、それとも 『0.123m × log 456m』 なのかが重要なのです。
そこで、数値を実際に計算する以前に、 10 x レベルで当ててみて、妥当な数値になるのか? という計算を行います。
その結果が、何桁の数字になるのか? オーダーはどれくらい? という質問になります。 答えとしては、『100m 2 くらい』 や 『10 2 m 2 くらい』 という解答になります。 (log 10 56.1 = 1.74 なので 10 2 に近い )
通常会話でも、だいたいの数字が知りたいときは『オーダーはどれくらい?』と聞いたりします。
情報工学において
情報工学において、『そのオーダーはどれくらい?』 といった言葉が交わされます。
これは、『ランダウの記号』の Order です。
意味としては、『処理をするときに、その計算量はどれくらい?』という意味で使われます。
コンピューターの計算において、複数のデータにおいて同一の処理をするということが良くあります。
例えば、[1, 10, 2, 9, 3, 8]
の中で一番大きい数字は? みたいな処理をするとき『一番大きい数字を検索する』という処理をすべての数字に対して行います。
一般的に記号 N
が数値の数を表しており、 どの程度の数か? という指標となります。
一般的な指標としては下記のとおりです。
-
O ( 1 )
- 最速です。
- 一般的にはありえません。
-
O ( log 2 N )
- 爆速です。
- 一般的には 事前処理済み (ソート済み)などの条件が付きます。
-
O ( N )
- 早いです。
- 1回の走査で計算できる処理の計算量となります。
-
O ( N log 2 N )
- 許容できる最大量です。
- 複雑な処理(ソートなど)における最速値が一般的にはこの値です。
-
O ( N x )
- 使用を躊躇します。
- この値が出てくると数が多くなったときの遅延が顕著になります。
データベースの計算や、コンピュータプログラムの計算でオーダーを考慮することは大切です。
プログラムの構築にミスをして 『O ( N x )』 が出てくる部分は遅延を生み出す要因となります。 計算量は指数関数的に増えるため、コンピュータリソースの増強では処理することは難しいです。
データベースなどを利用する際も、 Index などを使うことにより 『O ( N x )』 から 『O ( N log 2 N )』 に計算量が近づきます。 データベースチューニングを業務外とせず、 Index を使ってください。
日常の業務などでも、処理量は 『O ( N log 2 N )』 までに抑えましょう。
データベースにおいて
データベースを操作する SQL 言語や、 Spreadsheet などの表計算ソフトにおいて、 ORDER BY
は順序を表します。
SQL Like な言語においても同様です。
意味としては、『ある列で順序付けを行う』という意味になります。
この処理は一般的には sort
と呼ばれる処理となります。
ところで、 sort
は大きく分けて 『安定ソート(stable sort)』と『不安定ソート(unstable sort)』に分かれるのは知っていますでしょうか?
安定ソートは、2番目の要素、3番目の要素など、ソート処理を繰り返す場合、順序が保証されています。 不安定ソートはその逆で、2番目の要素、3番目の要素など、ソートを繰り返す場合に順序が保証されていません。
例示で示したいと思います。
氏名 | 国語の得点 | 現国の得点 | 古文の得点 |
---|---|---|---|
山田太郎 | 150 | 100 | 50 |
田中花子 | 150 | 50 | 100 |
鈴木一郎 | 100 | 100 | 0 |
ここで、 SELECT "氏名" ORDER BY "国語の得点" DESC, "現国の得点" DESC
とした場合を考えます。
安定ソートの場合、 ["山田太郎", "田中花子", "鈴木一郎"]
の順になります。
しかし、不安定ソートの場合、 ["山田太郎", "田中花子", "鈴木一郎"]
または ["田中花子", "山田太郎", "鈴木一郎"]
となります。
"現国の得点"
という 2番目の要素が保存されていない、不安定なソートとなります。
安定ソートか、不安定ソートか、2番目、3番目の要素で並び替えを行うときに重要な指標となります。 特に、全てのプログラミング言語やアルゴリズムにおいて 安定ソートで実装されていないということは知っておく必要があります。
不安定ソートの身近な例では、 javascript
は安定ソートではありませんでした。
『Internet Explorer』は最後のバージョンまで不安定ソート実装となっています。
SQL
は安定ソート実装であるため、2番目、3番目の要素を指定して問題ありません。
並び替えを行うときには、それが安定ソートか不安定ソートか確認するようにしてください。
まとめ
一般的には注文、発注という意味でのみ利用される『Order』に関するよもやま話でした。
もし気に入っていただけたら、友達などに『その Order どれくらい?』と聞いてみても面白いかもしれません。
以上
本サイトの記事について
本サイトの記事は、プログラミングだけでなく、雑多な雑学を多く配信しております。
もしよろしければ、ほか記事も閲覧いただけますと幸いです。