C++とJava（とSwift）の速度比較 〜ソートアルゴリズム編〜

$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=16.04
DISTRIB_CODENAME=xenial
DISTRIB_DESCRIPTION="Ubuntu 16.04.3 LTS"

Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/5/lto-wrapper
Target: x86_64-linux-gnu
（中略）
Thread model: posix
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4)

$ g++ -O2 -std=gnu++11

$ java -version
java version "1.8.0_144"
Java(TM) SE Runtime Environment (build 1.8.0_144-b01)
Java HotSpot(TM) 64-Bit Server VM (build 25.144-b01, mixed mode)

#include <vector>
#include <string>
#include <iostream>
#include <ctime>

class Person {
private:
    int id;
    std::string name;

public:
    Person( int id, const char* name ) {
        this->id = id;
        this->name = name;
    }

    Person() {
        this->id = 0;
        this->name = "";
    }

    int get_id() { return id; };
    std::string get_name() { return name; };

    bool operator< ( Person &p2 ) {
        return this->name < p2.name;
    };

    Person &operator=( const Person &p ) {
        this->id = p.id;
        this->name = p.name;
        return *this;
    }

};

template<class T> class Sort {
    T *buf;
    std::vector<T> *array;

public:
    Sort() {
    };

private:
    // ソート済みの2つの領域 (index_b〜index_c-1 と index_c〜index_e) をマージする関数
    void merge( int index_b, int index_c, int index_e ) {
        // 2つの領域が1つずつしかない場合は2つの大小関係だけ見る
        if ( index_b + 1 == index_e ) {
            if ( *(*array)[index_e] < *(*array)[index_b] ) {
                auto tmp = (*array)[index_e];
                (*array)[index_e] = (*array)[index_b];
                (*array)[index_b] = tmp;
            }
            return;
        }

        // index_1とindex_2を動かしながら，小さい方を順次index_bufへ書き込む
        int index_1 = index_b;
        int index_2 = index_c + 1;
        int index_buf = index_b;

        while ( true ) {
            if ( *(*array)[index_1] < *(*array)[index_2] ) {
                buf[index_buf++] = (*array)[index_1];
                // index_1が最後まで到達したらindex_2側を順番に見て終了
                if ( index_1++ == index_c ) {
                    while ( index_2 <= index_e ) {
                        buf[index_buf++] = (*array)[index_2++];
                    }
                    break;
                }
            } else {
                buf[index_buf++] = (*array)[index_2];
                // index_2が最後まで到達したらindex_1側を順番に見て終了
                if ( index_2++ == index_e ) {
                    while ( index_1 <= index_c ) {
                        buf[index_buf++] = (*array)[index_1++];
                }
                    break;
                }
            }
        }

        // バッファから元配列へコピー
        for ( int i = index_b; i <= index_e; i++ ) {
            (*array)[i] = buf[i];
        }

        return;
    };

    // 再帰的に呼び出す関数
    void merge_sort( int index_b, int index_e ) {
        int index_c = ( index_b + index_e ) / 2;

        // 左側をソート
        if ( index_b != index_c )
            merge_sort( index_b, index_c );

        // 右側をソート
        if ( (index_c + 1) != index_e )
            merge_sort( index_c + 1, index_e );

        // 左と右をマージ
        merge( index_b, index_c, index_e );

        return;
    };

public:
    // mainから呼ぶソート関数
    // ポインタの配列を渡すことを前提としている
    void merge_sort( std::vector<T> *vec ) {
        // ソート対象の配列
        this->array = vec;

        // マージ中のソート結果を一時的に記憶するバッファ
        this->buf = new T[ vec->size() ];

        // マージソート
        merge_sort( 0, vec->size() - 1 );

        delete [] buf;
    };

};

int main(int argc, char *argv[]) {
    // 時間測定のための変数
    struct timespec tp_start, tp_end;

    // 標準入力からデータを読み込み
    std::vector<Person*> vec_people;
    int id;
    std::string name;

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_start);

    while ( std::cin >> id && std::cin >> name ) {
        vec_people.push_back( new Person( id, name.c_str() ) );
    }

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_end);
    std::cout << "reading : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;

    // 読み込んだデータをソート
    Sort<Person*> sort;

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_start);

    sort.merge_sort( &vec_people );

    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tp_end);
    std::cout << "sorting : " << (double(tp_end.tv_sec - tp_start.tv_sec) + double(tp_end.tv_nsec - tp_start.tv_nsec) / 1000000000.0) << std::endl;

    // ソート済み確認
    for ( int i = 1; i < vec_people.size(); i++ ) {
        if ( *(vec_people[i]) < *(vec_people[i-1]) ) {
            std::cerr << "ERROR" << std::endl;
        }
    }

    for ( auto p : vec_people ) {
        delete p;
    }

    return 0;
}

public class Person implements Comparable {
    private int id;
    private String name;

    public Person( int id, String name ) {
        this.id = id;
        this.name = name;
    }

    public Person() {
        this.id = 0;
        this.name = "";
    }

    public int getId() { return id; };
    public String getName() { return name; };

    @Override
    public int compareTo( Object obj ) {
        return this.name.compareTo( ((Person)obj).name );
    };

    @Override
    public boolean equals( Object obj ) {
        if ( this.getId() == ((Person)obj).getId() &&
             this.getName() == ((Person)obj).getName() ) {
            return true;
        } else {
            return false;
        }
    }
};