C++における除算と乗算の速度比較

除算は他の演算と比べて重い処理だそうです。
今回は素数を求めるプログラムを例に検証してみたいと思います。

C++を使いますが、他の言語でも概ね同じことが言えると思います。
また、プログラムに穴がありますが話を単純にするためということでご容赦ください。

検証方法

以下のランダムに生成した19桁の素数を使って実行速度の平均を比較します。
素数の生成はこちらのサイトで行いました。
素数ジェネレータおよび素数チェッカー

8764234445678654651
1000000007650000061
9865445665456543571
4324677654356765473
2579997656754323467

まずは除算から

#include <iostream>
#include <ctime>
using namespace std;

void Judge_primeNum(unsigned long int i);

int main() {

    unsigned long int num = 0;
    cin >> num;

    clock_t start = clock();    //計測開始

    Judge_primeNum(num);

    clock_t end = clock();     //計測終了

    cout << (double)(end - start) / CLOCKS_PER_SEC << " sec." << endl;

    return 0;
}

void Judge_primeNum(unsigned long int num){
    for(int i = 2; num >= (num/ i) >= i; i++) {    //除算
        if(num % i == 0 && num != i){
            cout << "not prime" << endl;
            return;
        }
    }
    cout << "prime" << endl;
    return;
}
実行結果

8764234445678654651 : 32.504 sec.
1000000007650000061 : 15.1937 sec.
9865445665456543571 : 32.5616 sec.
4324677654356765473 : 31.4624 sec.
2579997656754323467 : 24.1967 sec.
Average : 27.18368 sec.

続いて乗算

#include <iostream>
#include <ctime>
using namespace std;

void Judge_primeNum(unsigned long int i);

int main() {

    unsigned long long int num = 0;
    cin >> num;


    clock_t start = clock();

    Judge_primeNum(num);


    clock_t end = clock();

    cout << (double)(end - start) / CLOCKS_PER_SEC << " sec." << endl;

    return 0;
}

void Judge_primeNum(unsigned long int num){
    for(int i = 2; num >= i * i; i++) {          //乗算
        if(num % i == 0 && num != i){
            cout << "not prime" << endl;
            return;
        }
    }
    cout << "prime" << endl;
    return;
}
実行結果

8764234445678654651 : 0.001361 sec.
1000000007650000061 : 0.001269 sec.
9865445665456543571 : 0.001403 sec.
4324677654356765473 : 0.001302 sec.
2579997656754323467 : 0.000562 sec.
Average : 0.0011794 sec.


うーん、とてつもない速さですね。
除算が遅いってのは割と常識な話みたいですね、知りませんでした。
最近のハードは昔と違って高性能なので、普段コーディングする際は
あまり意識することはないかもしれませんが、もの凄い回数のループを
回す時なんかはかなりパフォーマンスに差が出そうですね。



ちなみに実行環境は以下の通りです。
f:id:noiu:20170620205322p:plain

macでブラウザ起動時にタブを復元する

昨日macbookを買ったんですが、掲題の件で困ったので書いておきます。


左上のリンゴマーク → システム環境設定 → 一般 を開く。

アプリケーションを終了するときにウィンドウを閉じる のチェックを外す。

f:id:noiu:20170619232630p:plain


以上です。


ところで、GoogleChromeでブックマークと検索結果が新規タブで開くようにすることってできませんかね?
それさえできればFireFoxから乗り換えるんだけどなあ。
ご存知の方いらっしゃっいましたら教えてください。

paizaでの標準入力(Java)

paizaやCodeIQなどでプログラミングの練習をしようと思ったとき
標準入力のサンプルコードを見てもチンプンカンプンでつまずいたのでまとめておきます。

基礎編

1.Scanner

一番簡単だと思います。
ただし遅いらしい。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();  //文字列の入力受付
        System.out.println(line);
    }
}

注意しなければならないのは、String型の場合の入力はnextLine()を使うのに対して
int型の場合はnextInt()を使うこと。

2.BufferedReader

paizaのサンプルコードで使われてたやつ。
いまいちよく解ってないです。

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferdReader br = new BufferedReader(new inputStreamReader(System.in));
        String line = br.readLine();     //文字列の入力受付
        System.out.println(line);
    }
}

InputStreamReaderのReadメソッドでは一文字毎にしか読み込めずに非効率なので
BufferedReaderをInputStreamReaderでラップすることで一列にまとめて読み込むと
効率が良くなるらしい。

初学者の僕はnewの中でnewをしているのが気持ち悪くて
受け付けなかったんですが、リファレンスやら見てるうちに
解ったような解らないような...
こっちの方がScannerを使うよりも速いらしいです。

(少し)応用編

- 入力されたString型をsplitで分割する

paizaでの入力は大体"1 1"やら"1,1"などの形で行われます。
そこで空白やカンマで区切って分割したり
int型に変換したりしなければいけません。

public class Main {
    public static void main(String[] args) {
        String str = ("1,2,3");
        String[] array = str.split(",");
        for(int i : array) {
            System.out.println(i);
        }
    }
}

splitを使うことで、空白やカンマで区切られた文字列を分割して配列に格納
することができます。

- 分割した文字列をint型に変換する

ところがこのままだとString型のままなので計算に使うことができず
ifやforで使いたいときに困ります。
そこでさらにint型に変換します。

public class Main {
    Public static void main(String[] args) {
        String str1 = "1";
        String str2 = "2";
        int a = Integer.parseInt(str1);
        int b = Integer.parseInt(str2);
        System.out.println(a+b);
    }
}

これでやっと入力された文字列を数字として扱うことができるようになりました。
Scannerを使うときはInteger.parseInt()をInteger.parseInt(Scanner.next())に
すると入力と置き換えが一発でできて効率的らしいです。

高次元配列の拡張for文

int arrays = {{1, 2, 3}, {10, 20, 30}, {100, 200, 300}};
for (int[] array : arrays) {  //array[0] = {1,2,3} array[1] = {10,20,30,} array[2] = {100,200,300}
  for (int element : array) {
    System.out.println(element);
  }
}

 

文字列の比較

String a = "晴れ";

if(a == "晴れ") {  //間違い

文字列の比較の際は == は使えない

if(s.equals("晴れ") {  //正しい表記

 

文字列の変数.equals(比較相手の文字列)

クラスの呼び出しに関する疑問点

 int i = new java.util.Random().nextint(int b);

 

又は

 

Random a = Random();

int i = a.nextInt(int b);

 

で0~bの間で乱数を生成し、iに代入する。

これは、java.utilパッケージのRandomクラスをインスタンス化して、

nextIntメソッドを呼び出して使っているということ。

 

一方、

 

 int i = java.lang.Math.min(int a, int b); 

(java.langは予めimportされているため、通常は記述しない)

 

でaとbを比較し、小さいほうをiに代入する。

これは、java.langパッケージのMathクラスのminメソッドを呼び出して使っている。

 

Randomクラスを利用する場合はインスタンス化しているのに対して

Mathクラスのminメソッドを利用する場合はインスタンス化しなくてもいいのは

何故だろう。

 

追記

自己解決しました。

RandomクラスのnextIntメソッドは、静的(static)メソッドではないからみたいです。

 

静的メソッドとは

メソッドにstaticをつけることで定義される。

静的メソッドとすることで以下の三つの効果が現れる。

 

1.メソッドの実体がクラスに属するようになる

2.インスタンスにメソッドの分身が準備される

3・インスタンスを1つも生み出すことなく呼び出せる

 

今回の場合、関係するのは3つ目の効果。

APIリファレンスを参照すると

RandomクラスのnextIntメソッドはインスタンスメソッドとなっている。

つまり、静的メソッドではないためnewでインスタンスを生成してからでないと呼び出すことができない。

一方、Mathクラスのminメソッドはstaticメソッドであるから、インスタンスの生成無しでいきなり呼び出すことができる。

 

訂正、補足がありましたらご指摘ください。

import構文に関するメモ

import構文とは

他のpackageに記述されたメソッドを参照する際に予めimportしておくことで

FQCN(完全限定クラス名)入力の手間を省くことができる。

 

import [pakcage] . [class] ;

 

このように記述することで、package内の全てのclassをimportすることができる。

 

import [pakcage].* ;

 

 

 実行する際は現在のクラスパスを基準として、対応したフォルダ階層を作り、その中にclassファイルを配置しておく必要がある。

 

base  //class path

|___test

           |___main

           |      PjMain.class  //package test.main;

           |

           |___print

                  Writeing.class  //package test.print;

 

 

import構文の例外

java.langパッケージに属するclassは予めimportされている