C++とRubyで処理速度比較してみた　第一回

18635 ワード
C++ Mac アルゴリズム clang++ Ruby Ruby テキストリンク

はじめに

C++の処理速度が速い、Ruby生産性が高いと巷でよく聞くので、
実際に処理速度を比較してみたいと思いました。
それぞれで1000万までの素数生成プログラムを作り比べてみようと思います。

どちらもまだまだチューニングや測定方法などの改善の余地があると思うので、
こうやってみたら速くなるのでは
と気づいた方はコメントいただけるとすごく嬉しいです

そんな感じで改善していければ面白いかもと思い「第一回」としてます。

アルゴリズムは「エラトステネスのふるい」を使用してます。
自然数を何回かふるいにかけていって素数でない数を消していくと言うやり方です。
詳細で正確な解説は下記参照下さい。
https://ja.wikipedia.org/wiki/エラトステネスの篩

環境は下記になります。
macOS Catalina 10.15.6 [メモリ:8GB/CPU:Intel Core i5]
zsh
Apple clang version 12.0.0
ruby 2.6.3p62

Ruby編：コードと測定結果

prime_number.rb
def create_prime_number(max_number)
    terms = Array.new
    puts(Time.now.strftime("%H:%M:%S.%N hurui start"))
    max_number.times {|x| terms.push x + 1} # natural number
    terms.shift # reject 1
    last_number = Math.sqrt(max_number).floor # end of hurui

    puts(Time.now.strftime("%H:%M:%S.%N hurui start"))
    i = 0
    current_number = terms[i]
    while current_number <= last_number do
        ary = terms.reject {|x| x % current_number == 0 && x != current_number}
        terms = ary
        i += 1
        current_number = terms[i]
    end
    puts(Time.now.strftime("%H:%M:%S.%N hurui end"))

# result
#    p terms
end

create_prime_number(10000000)

実行結果は下記になります。

% ruby prime_number.rb
23:57:23.813912000 hurui start
23:57:24.487299000 hurui start
23:57:49.403797000 hurui end

Ruby編：気づいたこと

・破壊的メソッドでふるいにかけようとするとすごく遅くなりました。

prime_number.rb
terms.reject! {|x| x % current_number == 0 && x != current_number}

C++編：コードと測定結果

eratosthenes.cpp
#include<iostream>
#include <math.h>
#include <list>
#include <sys/time.h>

#define MAX_NUMBER 10000000

using namespace std;

int main()
{
    unsigned long last_num = (unsigned long)sqrt(MAX_NUMBER);
    unsigned long cur_num;
    struct timeval tv;
    struct tm *time_fmt;

    list<unsigned long> *num_ls = new list<unsigned long>;
    list<unsigned long>::iterator num_ls_itr;
    unsigned long itr_skip;
    unsigned long i;

    /* ======== measurement ======== */
    gettimeofday(&tv, NULL);
    time_fmt = localtime(&tv.tv_sec);
    cout << time_fmt->tm_hour << ":" << time_fmt->tm_min << ":" << time_fmt->tm_sec << "." << tv.tv_usec << endl;
    /* ======== measurement ======== */

    /* create natural number */
    for (unsigned long ntrl_num = 2; ntrl_num <= MAX_NUMBER; ntrl_num++) {
        num_ls->push_back(ntrl_num);
    }

    /* ======== measurement ======== */
    gettimeofday(&tv, NULL);
    time_fmt = localtime(&tv.tv_sec);
    cout << time_fmt->tm_hour << ":" << time_fmt->tm_min << ":" << time_fmt->tm_sec << "." << tv.tv_usec << endl;
    /* ======== measurement ======== */

    /* hurui */
    itr_skip = 0;
    num_ls_itr = num_ls->begin();
    cur_num = *num_ls_itr;
    while (cur_num <= last_num) {
        for (; num_ls_itr != num_ls->end();) {
            if (
                (*num_ls_itr % cur_num == 0) &&
                (*num_ls_itr != cur_num)
            ) {
                num_ls_itr = num_ls->erase(num_ls_itr);
            } else {
                num_ls_itr++;
            }
        }
        num_ls_itr = num_ls->begin();
        itr_skip++;
        for (i = 0; i < itr_skip; i++) {
            num_ls_itr++;
        }
        cur_num = *num_ls_itr;
    }

    /* ======== measurement ======== */
    gettimeofday(&tv, NULL);
    time_fmt = localtime(&tv.tv_sec);
    cout << time_fmt->tm_hour << ":" << time_fmt->tm_min << ":" << time_fmt->tm_sec << "." << tv.tv_usec << endl;
    /* ======== measurement ======== */

    /* result */
#if (0)
    cout << "[";
    for (num_ls_itr = num_ls->begin(); num_ls_itr != num_ls->end(); num_ls_itr++) {
        cout << *num_ls_itr << ",";
    }
    cout << "]" << endl;
#endif

    delete num_ls;

    return 0;
}

コンパイルと実行結果は下記になります。

% clang++ eratosthenes.cpp -o eratosthenes -O3
% ./eratosthenes
23:56:12.820103
23:56:13.458872
23:56:37.406918

C++編:気づいたこと

・最適化オプション(-O3)を付けずにコンパイルすると10秒ちょっと遅くなりました。

% clang++ eratosthenes.cpp -o eratosthenes

・listをヒープ領域からスタック領域に変更してもそんなに変わらなかった。

eratosthenes.cpp
list<unsigned long> num_ls;

終わりに

今回はC++の方がRubyよりもおよそ1秒ほど早かった形になります。
C++の方はiteratorループ内のeraseのやり方を誤ったせいで「segmentation fault」でしばらくハマりましたし、時間計測に使ったgettimeofday関数を後で調べてみると非推奨になっていたりしました(chronoを使うと良いらしい)。
やはり生産性はRubyの方が高かった印象です。