set、vector與list的構造與排序的耗時測試

測試目標

測試在成員個數不斷遞增的情況下，set、vector與list的構造與排序的耗時變化，找出set耗時連續超過其他容器耗時的成員個數

測試方式

• set使用直接插入

• vector使用assign構造并使用全局sort排序

• list使用assign構造與成員sort的排序之間

• 比較的是耗時時間大小，對耗時的具體值不關心，因為不同的機器配置不一樣

測試結論

由于設定的連續超過次數不同，得到的成員個數值也不同，并且隨著連續超過上限的增加而增加，因此現在得到的成員個數值并不準確，如：

在連續超過上限為10時，成員個數最大在700左右

在連續超過上限為20時，成員個數最大在2000左右

但有一點可以肯定：set的邊插入邊排序效率，沒有vector與list的賦值或排序高，如果有海量數據排序的情況，用vector或list的賦值后排序的性能相對于set比較好。

測試代碼

// 主邏輯 main.cpp
#include "TimeConsume.h"
#include "Random.h"
#include <unistd.h>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdint>
#include <string>
using namespace std;

// set耗時是否連續超出其他容器
bool is_continue_beyond(uint64_t vector_time, uint64_t list_time, uint64_t set_time, uint64_t beyond_num) {
    static uint64_t s_beyond_num = beyond_num; 
    if (set_time > list_time && set_time > vector_time) {
	--s_beyond_num;
    } else {
	s_beyond_num = beyond_num;
    }

    return s_beyond_num == 0;
}

int main(int argc, char** argv) {

    uint64_t member_count_num = 0;
    uint64_t member_add_num = 0;
    uint64_t beyond_num = 0;
    if (argc != 4) {
	cout << "input: " << argv[0] << " member_start_num member_add_num beyond_num" << endl;
	return -1;
    } else {
	member_count_num = strtoull(argv[1], NULL, 10);
	member_add_num = strtoull(argv[2], NULL, 10);
	beyond_num = strtoull(argv[3], NULL, 10);
    }

    uint64_t vector_time = 0;
    uint64_t list_time   = 0;
    uint64_t set_time    = 0;

    while (!is_continue_beyond(vector_time, list_time, set_time, beyond_num)) {
	vector<uint64_t > input_random_num; // 使用一樣的隨機數據
	Random random;
	random.SetRandomNum<vector<uint64_t> >(member_count_num, input_random_num);

	// 構造排序函數
	vector<uint64_t> monitor_vector; // 外部定義容器，防止構造析構帶來的時間計算
	auto vector_sort = [&]() {
	    monitor_vector.assign(input_random_num.begin(), input_random_num.end());
	    sort(monitor_vector.begin(), monitor_vector.end());
	};

	list<uint64_t> monitor_list;
	auto list_sort = [&]() {
	    monitor_list.assign(input_random_num.begin(), input_random_num.end());
	    monitor_list.sort();
	};

	set<uint64_t> monitor_set;
	auto set_sort = [&](){
	    monitor_set.insert(input_random_num.begin(), input_random_num.end());
	};

	// 統計排序時間
        TimeConsume vector_time_consume(vector_sort);
        TimeConsume list_time_consume(list_sort);
        TimeConsume set_time_consume(set_sort);

	vector_time = vector_time_consume.GetFnTime();
	list_time = list_time_consume.GetFnTime();
	set_time = set_time_consume.GetFnTime();

	cout << "count:" << member_count_num<< "\t" << "vector_time:" << vector_time << "\t" << "list_time:" << list_time << "\t" << "set_time:" << set_time << endl;
	sleep(0.5);
	member_count_num += member_add_num;
    }
    return 0;
}

/*
TimeConsume.h
用于獲得程序運行的時間消耗，支持函數對象（C++11新標準）
獲得的耗時為微秒級
*/
#ifndef TIME_CONSUME_H
#define TIME_CONSUME_H

#include <sys/time.h>
#include <ctime>
#include <functional>
using std::function;

#define SEC_RATIO_MSEC 1000
#define SEC_RATIO_USEC (1000*SEC_RATIO_MSEC)

class TimeConsume {
public:
    TimeConsume(const function<void()> &monitor_fn = [](){;})
	: m_monitor_fn(monitor_fn) {
	    Clear();
    }

    ~TimeConsume()
    {;}

    // 設置耗時監控的函數對象
    inline function<void()> SetMonitorFn(const function<void()> &monitor_fn()) {
    	auto old_monitor_fn = m_monitor_fn;
    	m_monitor_fn = monitor_fn;
    	return old_monitor_fn;
    }

    // 記錄開始監控的時間點
    inline void Start() {
	    gettimeofday(&m_start, NULL);
    }
    
    // 記錄結束監控的時間點
    inline void End() {
	    gettimeofday(&m_end, NULL);
    }

    // 依據開始和結束監控的時間點，得到微秒級耗時
    inline uint64_t GetIntervalTime() {
    	if ((m_end.tv_sec > m_start.tv_sec)
    	    || (m_end.tv_sec == m_start.tv_sec && m_end.tv_usec >= m_start.tv_usec)) {
    	    return (m_end.tv_sec - m_start.tv_sec)*SEC_RATIO_USEC + (m_end.tv_usec - m_start.tv_usec); 
    	} else {
    	    return 0;
    	}
    }

    // 獲得監控函數對象的微秒級運行耗時
    inline uint64_t GetFnTime() {
        Clear();
    	Start();
    	m_monitor_fn();
    	End();
    	return GetIntervalTime();
    }

protected:
    // 格式化內部相關值
    inline void Clear() {
    	m_start.tv_sec = 0;
    	m_start.tv_usec = 0;
    	m_end.tv_sec = 0;
    	m_end.tv_usec = 0;
    }

private:
    struct timeval m_start;
    struct timeval m_end;
    function<void()> m_monitor_fn;
};
#endif

/*
Random.h
可以向STL 容器里填充指定個數的隨機值，取值范圍在[0-RAND_MAX]，RAND_MAX為最大值的整數常量表達式。此值依賴實現。保證此值至少為32767
*/
#ifndef RANDOM_H
#define RANDOM_H

#include <ctime>
#include <iterator>
using std::inserter;

class Random {
public:
    Random() {
	srand(time(NULL));
    }

    ~Random()
    {;}

    template <typename  ContainerT>
    inline void SetRandomNum(uint64_t count, ContainerT &container) {
	auto iter = inserter(container, container.end());
	for (uint64_t i = 0; i < count; ++i) {
	    iter = rand();
	}
    }
};

如果對測試有什么疑問或建議，歡迎大家來討論