소개

C++의 처리 속도가 빠르고, Ruby 생산성이 높다고 면에서 잘 듣기 때문에,
실제로 처리 속도를 비교하고 싶었습니다.
각각 1000만까지의 소수 생성 프로그램을 만들어 비교해 보려고 합니다.

둘 다 아직 튜닝이나 측정 방법 등 개선의 여지가 있다고 생각하기 때문에,
이렇게 해보면 빨라지는 것은
라고 깨달은 분은 코멘트하실 수 있으면 매우 기쁩니다

그런 느낌으로 개선해 나가면 재미있을지도 생각해 「제1회」로 하고 있습니다.

알고리즘은 "엘라토스테네스 체"를 사용합니다.
자연수를 몇 번이나 체에 걸쳐서 소수가 아닌 수를 지워 간다고 하는 방법입니다.
상세하고 정확한 해설은 아래를 참조하십시오.
https://ko.wikipedia.org/wiki/엘라토스테네스의 체

환경은 다음과 같습니다.
macOS Catalina 10.15.6 [메모리:8GB/CPU:Intel Core i5]
zsh
Apple clang 버전 12.0.0
루비 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 쪽이 높았던 인상입니다.