読者です 読者をやめる 読者になる 読者になる

おふとんガレージ

技術的なことの忘備録とか

C++はじめました

忘備録

ある講義で諸々あって早急にC++を使えないといけない状態になったので

CとC++の違い
  • オブジェクト指向の導入
  • 変数がどこでも宣言可能
  • 関数の参照渡しが可能
  • bool型が使える
  • 返り値が無い関数の場合voidを明記する必要がある
ともかく何か書いてみた

同じタイミングで別の講義でソートにおける速さを比較せよって割と軽めの課題が出たので可能な限りC++を意識して書いてみた。
内容的にオブジェクト指向を使わなくてもなんとかなってしまったのでその辺は近々みっちりやりたいところ。

課題
  • 0~15までの範囲の中から重複しない10個の乱数を出力する。
  • クイックソートバイナリ列を用いたソートを行いその実行時間を計測する。
バイナリソートについて
  1. その数の存在を保存する配列Aを容易する
  2. 乱数の先頭から内容を確認し、それに対応する配列Aの箇所をfalse->trueに変更
  3. 乱数の最後まで確認が終了したら、配列Aのtrueとなってる箇所に対応する数値を出力

使用するメモリ領域も少なく処理も軽いが、重複する値の情報が消えてしまう。
リソースに制限がある中で、電話番号の並べ替えなど限られた状況でのみ威力を発揮する。

引っかかった点
  • bool配列は最初に全部falseで埋める必要がある
    • 初期状態だとtrueとfalseが混在しており正確なソート結果が出ない
  • 参照,ポインタ関連
    • 苦手を引きずりまくってるので一回基礎からやり直したいところ
実装
//
//  main.cpp
//  SysEngHW1
//
//  Created by zhuravlik on 2016/10/12.
//  Copyright © 2016年 zhuravlik. All rights reserved.
//

#include <iostream>
#include <time.h>
#include <string.h>
#include <stdlib.h>

#define NUM_OF_RANDS 10
#define MAX_RANDS 15

using namespace std;


inline void initRand(){
    srand((unsigned int)time(NULL));
}


void makeRandArray(int *init){
    
    initRand();
    int temp[MAX_RANDS + 1];
    int randKey, randNum = MAX_RANDS + 1;
    
    for(int i = 0; i <= MAX_RANDS; i++)
        temp[i] = i;
    
    cout << "-----Init Array-----" << endl;
    
    for(int i = 0; i < NUM_OF_RANDS; i++){
        randKey = rand() % randNum;
        *init = temp[randKey];
        temp[randKey] = temp[randNum - 1];
        --randNum;
        
        cout << *init << " ";
        ++init;
    }
    cout << "\n-----Init Array-----\n" << endl;
}


void binarySort(int *result){
    cout << "-----Binary Sort-----" << endl;
    
    clock_t start = clock();
    int sorted[NUM_OF_RANDS];
    int *temp = result;
    bool presence[MAX_RANDS + 1] = {0};
    
    //cout << "-----init-----" << endl;
    for(int i = 0; i < NUM_OF_RANDS; i++){
        //cout << *result << " ";
        presence[*result] = true;
        ++result;
    }
    
    cout << "----result----" << endl;
    
    
    //for(int i = 0; i <= MAX_RANDS; i++) cout << i << " : " << presence[i] << endl;
    
    int counter = 0;
    
    for(int i = 0; i <= MAX_RANDS; i++){
        if(presence[i] == true){
            sorted[counter] = i;
            cout << i << " ";
            counter++;
        }
    }
    cout << "\n";
    
    clock_t end = clock();
    cout << "duration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec." << endl;
    cout << "-----Binary Sort-----" << endl;
    
    for(int i = 0; i < NUM_OF_RANDS; i++){
        *temp = sorted[i];
        ++temp;
    }
}


int compareInt(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}


int main(int argc, const char * argv[]) {
    
    if(NUM_OF_RANDS > MAX_RANDS){
        cout << "Error! Plz check NUM_OF_RANDS and MAX_RANDS" << endl;
        return 1;
    }
    
    int init[NUM_OF_RANDS], res1[NUM_OF_RANDS], res2[NUM_OF_RANDS];
    
    makeRandArray(init);
    
    memcpy(res1, init, sizeof(init));
    memcpy(res2, init, sizeof(init));
    
    binarySort(init);
    
    cout << "\n-----Quick Sort-----" << endl;
    
    clock_t start = clock();
    qsort(res2, NUM_OF_RANDS, sizeof(int), compareInt);
    
    cout << "----result----" << endl;
    
    for(int i = 0; i < NUM_OF_RANDS; i++)
        cout << res2[i] << " ";
    
    cout << "\n";
    
    clock_t end = clock();
        cout << "duration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec." << endl;
    cout << "-----Quick Sort-----" << endl;
    
    return 0;
}
実行結果
-----Init Array-----
12 11 15 6 2 4 1 5 3 13 
-----Init Array-----

-----Binary Sort-----
----result----
1 2 3 4 5 6 11 12 13 15 
duration = 2.2e-05sec.
-----Binary Sort-----

-----Quick Sort-----
----result----
1 2 3 4 5 6 11 12 13 15 
duration = 2.1e-05sec.
-----Quick Sort-----
Program ended with exit code: 0
知見とか感想とか
cout << hogehoge << endl;

めっちゃ楽、printf()みたいに気を使わなくていいし楽。
見返してみるとC++の勉強だってのにCと対して変わらないコードになってる。
ソートは元から用意されてるもの使ったほうが賢い。
xcode初めて使ったけど、参照領域違反したときどこでそうなったか教えてくれるのすごい素敵。