2重ループと1重ループの計算量(オーダー)ってどれぐらい違うの?

f:id:ts0818:20200105143610j:plain

xn--tp5a.biz

雷の電流は、直流、それとも交流?
直流電流、いわゆる直流は、電圧の値と向きが一定なものをいいます。
理科の実験で使った乾電池などがこれにあたります。
これに対し、交流電流、いわゆる交流は電圧の値が周期的に変化するものを指していいます。
家庭に流れている電流がその好例と言えます。
では、雷によってもたらされる電流はいったいどちらでしょう?
答えは、あえて分けるとすれば直流です。
雲の下の部分にはプラスの氷の粒が蓄積しており、地面はマイナスの役割を果たします。
正確には直流と交流に分類できない、パルス(短時間の振動現象)と呼ばれるものになるそうです。

雷の電圧と電流。直流なのか交流なのか? | 雷の知恵袋

⇧  雷が「直流」であれば、「水プラズマ」の生成に役立つ日がいつか来ますかね~。

そういえば、

kawada-nouen.com

稲妻って稲の妻っていう漢字を書くけど、昔は稲夫でいなずまだったらしい。

雷の時期に稲の穂がついて膨らんで来る時期で、雷には稲を妊娠させる力があると言われていたそうです。

稲妻が稲を妊娠させるって昔の人は面白い考え方するねえ。

稲妻ってなぜ稲の妻なの?

⇧ 雷のことを稲妻っていう時もあるけど、稲妻って「稲夫」って漢字だったそうな。

 

はい、すみません、脱線しました。で、何で「水プラズマ」の話が?ってことですが、

headlines.yahoo.co.jp

 まずは九州大学の渡辺隆行教授とのタッグで進めるプラズマだ。1万度の高温でゴミや金属までも蒸発させる技術で、環境問題への実用化が期待されている。

アントニオ猪木氏、車いす姿でも元気を発信「あるがままで」という生き方(ENCOUNT) - Yahoo!ニュース

⇧  アントニオ猪木氏のインタビュー記事で、「プラズマでごみ問題解決?」って何だろう?って思ったんですが、

 

www.chem-eng.kyushu-u.ac.jp

水プラズマには O,H,OH ラジカルが豊富に含まれているので,新しい廃棄物処理プロセスへの展開が可能である。ゴミを単に分解・無害化するだけではなく,プラズマでゴミを分解することによって水素を取り出すことも可能となる。

水プラズマを用いて廃棄物から水素を製造する方法は,プラズマの放電領域で有機物を高速で分解できることから分解効率が高い方法である。水プラズマ自体からも水素が発生するので,廃棄物から副生水素を製造するプロセスは実現できる可能性がある。

本章ではアーク放電の可視化と温度計測をもとに水プラズマの発生原理と特徴を解説し,最後に車載型水プラズマの応用展開を紹介する。

http://www.jspf.or.jp/Journal/PDF_JSPF/jspf2019_01/jspf2019_01-27.pdf

⇧  ってな感じで「水プラズマ」の研究が紹介されていまして、

 

まずは「水プラズマ」という定義を明確にする。「水プラズマ」と「水蒸気プラズマ」はどちらも水をプラズマ状態にしたものなので,混同されている場合がある。「水プラズマ」と「水蒸気プラズマ」は,原理的にも特性も異なるものである。

http://www.jspf.or.jp/Journal/PDF_JSPF/jspf2019_01/jspf2019_01-27.pdf

⇧  で、何が違うかと言うと、

「水蒸気プラズマ」は,アルゴンなどで発生した熱プラズマの高温領域に水蒸気を吹き込み,水蒸気をプラズマ化する方法である。この方法はフロンや PCBの分解などに応用されており,オーストラリアのCSIROが開発したPLASCON プロセスが有名である。
一方,「水プラズマ」とは,液体の水をプラズマの高温領域に供給し,瞬時に水素と酸素に分解する方法である。この方法は水だけではなく,各種の水溶液やコロイドでもプラズマを発生できる。

http://www.jspf.or.jp/Journal/PDF_JSPF/jspf2019_01/jspf2019_01-27.pdf

⇧  てな違いがありますと。

そもそも、プラズマって何?ってな情弱な私なので、調べてみたところ、

seoulinmedicare.com

Plasma is the fourth state of matter following the state of solid, liquid and gas whereby the gaseous state has been ionized by the high temperature and high electricity in everyday environment. The universe is consisted of 99.999% plasma.

f:id:ts0818:20200105140442p:plain

What’s Plasma – SeoulinMedicare

⇧  上記サイト様によりますと、「気体」に何らかのエネルギーが加わることにより「プラズマ」 ができるんであると。宇宙の99.999%は「プラズマ」で構成されてるってのが衝撃だけど...

んで、この加えるエネルギーとして、直流電流を利用することが多いってことなんですかね?

 

まぁ、「水蒸気プラズマ」「水プラズマ」の違いはよく分からんけど、おそらく「水蒸気プラズマ」は「気体」から、「水プラズマ」は「液体」 から生成できるってことを言いたいんですかね?

「水蒸気」は、

水蒸気(すいじょうき、スチームともいう)は、気化した蒸気。空気中の水蒸気量、特に飽和水蒸気量に対する水蒸気量の割合のことを湿度という。

水蒸気 - Wikipedia

⇧ って説明で、「蒸気」は、

蒸気(じょうき、vapor, vapour)は、物質液体から蒸発して、あるいは固体から昇華して、気体になった状態のもの。特に臨界温度以下の物質気相を指すこともある。日本語においてしばしば水蒸気 (steam)の略語として用いられる。蒸気機関の蒸気も水蒸気の意味である。液相固相平衡を保って共存している状態の圧力を蒸気圧という。

蒸気 - Wikipedia

⇧ って説明になっとるしね。

 

水プラズマ技術は,有機系廃棄物から水素を製造する高温熱分解技術のひとつとして考えられる。水プラズマを用いる方法は,他の燃焼法よりも水素の製造量が多く,装置が小さいという利点がある。

特に廃棄物処理を現地で分散型のシステムとして処理することも可能となるので,今後のプラズマ処理システムの新たな展開が期待できる。

http://www.jspf.or.jp/Journal/PDF_JSPF/jspf2019_01/jspf2019_01-27.pdf

⇧ 「水プラズマ」が導入できると、有機物(ここではゴミを想定しているかと)の分解効率は高い、且つ、従来の燃焼法よりも水素の製造量が多く装置が小さいという利点が享受できるらしい。

ゴミ処理場の問題とかでも選択肢が広がるってことですかね?(装置が小さくできるということは、必要な土地面積も小さくなるってことではないかと。)

あっ、でも、収集したゴミを置く敷地の必要量は変わらんから、ゴミ処理場問題には関係ないか。

 

アントニオ猪木(アントニオいのき、Antonio Inoki1943年2月20日 - )は、日本の元プロレスラー実業家政治家本名猪木 寛至(いのき かんじ)。神奈川県横浜市鶴見区出身。血液型AB型新日本プロレス設立後のキャッチフレーズは「燃える闘魂」。日本プロレス所属時代のキャッチフレーズは「若獅子」。愛称は「アントン」。

アントニオ猪木 - Wikipedia

⇧  「燃える闘魂」のキャッチフレーズを持つ、アントニオ猪木氏に、「プラズマによるゴミ焼却での環境問題への実用化へのPR」はマッチしてますね~。

 

あと、「学術論文」の読める技術が欲しいな~って思ってたらば、 

gigazine.net

一部の学術誌には、掲載予定の論文を別の科学者がチェックする査読というシステムが存在します。世に出る論文がある程度の質や正確性を保っているのは、査読者の審査に負うところが多いとされていますが、「査読者の中には非常に悪質な査読コメントを書く者もいる」と科学誌サイエンスに記事を寄稿したサイエンスライターのクリスティ・ウィルコックス氏が指摘しています。

論文の「ひどいチェック」が科学の発展を妨げているという指摘 - GIGAZINE

⇧  アカデミックな世界でも、正当なレビューができない人がおりますと、人間だもの。というわけで、狂った街、東京に戻ってきました、どうも、ボクです。

まぁ、何ていうか、こういう問題が出てきてしまうと、今までの論文に対しての価値も揺らいでしまうのでは?って思ってしまいますかね、論文読んだこと無いけど、というか読み方も知らないから読めんしね...。

アカデミックな素養が欲しいな~。

 

まぁ、そんなこんなで、脱線しまくりましたが、「計算量(オーダー)」ってなものについて調査してみました~。そんでは、レッツトライ~。

 

計算量(オーダー)って?

そもそも、計算量(オーダー)って何ぞや? 

ランダウの記号ランダウのきごう、Landau symbol)は、関数極限における値の変化度合いに、おおよその評価を与えるための記法である。

ランダウの記号 - Wikipedia

ランダウの漸近記法 (asymptotic notation)ランダウ記法 (Landau notation) あるいは主要な記号として O (オーもしくはオミクロン Ο。数字の0ではない)を用いることから(バッハマン-ランダウの)O-記法 (Bachmann-Landau O-notation)ランダウのオミクロンなどともいう。

ランダウの記号 - Wikipedia

記号 O は「程度」の意味のオーダー(Order)から。

ランダウの記号 - Wikipedia

なおここでいうランダウエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。

ランダウの記号 - Wikipedia

ランダウの記号は数学計算機科学をはじめとした様々な分野で用いられる。

ランダウの記号 - Wikipedia

⇧  ってな感じで、値の変化に対する評価のために考案されたもので、「O-記法」っていうらしいっす。 

 

qiita.com

あるアルゴリズムを使った演算の性能を表す指標。
計算量は大きく二つに分けられる。
- 時間計算量(処理時間の計算量)
- 空間計算量(メモリ使用量の計算量)

単に計算量(オーダー)と言った場合、時間計算量のことを指す。

計算量オーダーについて - Qiita

⇧  上記サイト様が詳しいですが、 


{O(1)},{O(logn)},{O(n)},{O(nlogn)},{O(n^2)},{O(n^3)},{O(n^100)}

の順で計算量が増えていくようですかね。

Wikipediaさんによりますと、

記法 名称 アルゴリズムの例
指数時間 (exponential, geometricとも) (現在最も速い)巡回セールスマン問題の(厳密解の)解法
階乗関数 (factorial, combinatorialとも) 2つの論理式の同型判定[1]、巡回セールス問題などのNP完全問題の全探索による解法

ランダウの記号 - Wikipedia

⇧  このあたりが、今のところ、最も速いってことですが、

一方で制約のない巡回セールスマン問題の直接の応用事例は無いと言ってもよい。逆に実際の応用事例では、より複雑な定義で配送計画や表面実装ロボットの動作計画などに適用される。

巡回セールスマン問題 - Wikipedia

⇧  「巡回セールスマン問題」については、制約付きの解しか無さそうなので、事実上、


{O(2^n)},{O(n!)}

については、実用的ではないってことになるんですかね?

 

 

二重ループと一重ループの計算量はどのぐらい? 

例のごとく、Aizu Online Judge の問題を解いていた時に、 

onlinejudge.u-aizu.ac.jp

n に関する2重ループで実装された


{O(n^2)}

の素朴なアルゴリズムを、ひとつのループで完結した


{O(n)}

アルゴリズムに改良することができました。また、改良したアルゴリズムでは、入力を配列に保持する必要もなくなり、メモリ使用量も改善することができます。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D

⇧  の問題で、「二重ループ」と「一重ループ」で計算量がだいぶ変わってきそうなんですと。

 

nowokay.hatenablog.com

アルゴリズムの話では、計算量の解析がかかせません。
計算量はオーダー記法で表されますが、これは、データの入力量に対してどのくらい時間がかかるかをあらわしたものです。

https://nowokay.hatenablog.com/entries/2009/01/06

⇧ 上記サイト様で、視覚化してくれていました。

なので、「一重ループ」は「一次関数」、「二重ループ」は「二次関数」 的に計算量が増加していく感じになるのではないかと。

 

というわけで、Aizu Online Judge に提出したコーディングは、こんな感じ。(提出時、package main; は削ってますが) 

package main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws NumberFormatException, IOException {
    // TODO 自動生成されたメソッド・スタブ
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int priceRange = Integer.valueOf(in.readLine()); // n
    int minv = Integer.valueOf(in.readLine()); // 最小値
      int tmp = 0; // 退避用
      int maxv = 0; // 最大利益(価格の差)
    for (int i = 1; i <= priceRange -1 ; i++) {

      tmp = Integer.valueOf(in.readLine());
      if (i == 1) { // 初回を、最大利益の初期値とする
      maxv = tmp -minv;
      }
      if (maxv < (tmp -minv)) { // 最大利益の更新
        maxv = tmp -minv;
      }
      if (minv > tmp) { // 最小値の更新
        minv = tmp;
      }
    }
        System.out.println(maxv);
  }
}

ってな感じで、

f:id:ts0818:20200105144655p:plain

1番時間がかかったものでも、「00.17s」でいけましたと。(要素は199999個)

ただし、要素が一番多いもの(200000個)は、処理時間としては「00.15s」であると。

「00.17s」かかったケースで考えると、「一重ループ」は「一次関数」、「二重ループ」は「二次関数」 的に計算量が増加していくと思われるので、「二重ループ」は、199999 × 199999 の個数を処理するということになるかと。

で、「一重ループ」と「二重ループ」の計算量を比較してみようということで、

www.momoyama-usagi.com

1秒間に1億ステップ (100,000,000) 実行できるものとして考え、1秒(1億ステップ)を超えてしまうものは計算にかかる時間を載せています。

プログラムの計算量、オーダー表記 O( ) の求め方のまとめ - 工業大学生ももやまのうさぎ塾

⇧  上記サイト様の表を参考にさせていただきました。

「二重ループ」で1.0秒(100,000,000ステップ)かかる時、「一重ループ」では0.0001秒(10,000ステップ)となるので、「一重ループ」では0.1秒(10,000,000ステップ)との時は、「二重ループ」で12日(100,000,000×3600×12ステップ)かかるらしい...

「一重ループ」で00.17s(17,000,000ステップ)の時は、...

(17,000,000 × 17,000,000) ÷ 10,000,000 = 2,890,000秒

ってことになりますと。

2890000 ÷ 3600 = 802.777777778
802.777777778 ÷ 365 = 2.19939117199

およそ、2.2年っすか...

無邪気に「二重ループ」を使ってきましたけど、極力「一重ループ」でいける時は「一重ループ」で頑張らねばって気がしましたかね...。

アルゴリズム難しいな~

いつものごとく、モヤモヤ感が募りましたかね...

今回はこのへんで。