当前位置:网站首页>Time consuming test of construction and sorting of set, vector and list
Time consuming test of construction and sorting of set, vector and list
2022-07-19 12:05:00 【Apprentice Mo Xiaoge】
Test target
When the number of members is increasing ,set、vector And list Time consuming changes in the construction and sequencing of , find set The number of members that take more time than other containers
Test method
- set Use direct insertion
- vector Use assign Construct and use global sort Sort
- list Use assign Constructs and members sort Between sorts of
- The comparison is time-consuming , Don't care about the specific value of time consumption , Because different machines have different configurations
Test conclusion
Because the number of consecutive excesses set is different , The number of members obtained is also different , And it increases with the continuous increase of exceeding the upper limit , Therefore, the number of members obtained now is not accurate , Such as :
After continuously exceeding the upper limit is 10 when , The maximum number of members is 700 about
After continuously exceeding the upper limit is 20 when , The maximum number of members is 2000 about
But one thing is certain :set Efficiency of sorting while inserting , No, vector And list The assignment or sorting of is high , If there is massive data sorting , use vector or list The performance of sorting after assignment is relative to set better .
Test code
// Main logic 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 Whether the time consumption continuously exceeds that of other containers
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; // Use the same random data
Random random;
random.SetRandomNum<vector<uint64_t> >(member_count_num, input_random_num);
// Construct sorting function
vector<uint64_t> monitor_vector; // Externally defined containers , Prevent the time calculation caused by structural decomposition
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());
};
// Statistical sorting time
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
It is used to obtain the time consumption of program running , Support function objects (C++11 The new standard )
The time taken to obtain is microsecond
*/
#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()
{;}
// Set time-consuming function objects
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;
}
// Record the time when monitoring started
inline void Start() {
gettimeofday(&m_start, NULL);
}
// Record the time point when the monitoring ends
inline void End() {
gettimeofday(&m_end, NULL);
}
// According to the time point when the monitoring starts and ends , It takes time to get microseconds
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;
}
}
// It takes time to get the microsecond running time of the monitoring function object
inline uint64_t GetFnTime() {
Clear();
Start();
m_monitor_fn();
End();
return GetIntervalTime();
}
protected:
// Format internal related values
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
Can be directed to STL The container is filled with a specified number of random values , The value range is [0-RAND_MAX],RAND_MAX Is the integer constant expression of the maximum value . This value depends on the implementation . Ensure that this value is at least 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();
}
}
};If you have any questions or suggestions about the test , Welcome to discuss
边栏推荐
- TiKV 线程池性能调优
- Ten minutes from pytorch to mxnet
- 【嵌入式单元测试】C语言单元测试框架搭建
- Tidb memory control document
- The basic establishment of the sequence table and the related operations of adding, deleting, modifying and querying (the sequence table described in C language)
- 项目建设,谋事在人,成事亦在人!
- STM32F407 NVIC
- Leetcode 1252. Number of odd value cells
- 【二叉树】之力扣牛客必刷题
- 565. 数组嵌套 : 常规模拟题
猜你喜欢

【二叉树】之力扣牛客必刷题

Leetcode skimming -- find and minimum k-pair number 373 medium

How to build dashboard and knowledge base in double chain note taking software? Take the embedded widget library notionpet as an example

Valid bracket sequence of "Niuke | daily question"

mysql学习笔记-约束

HCIP(5)

From prediction to decision-making, Chapter 9 Yunji datacanvas launched the ylearn causal learning open source project
![[original] magisk+shamiko has been tested by app root](/img/85/29367cf544c0f221a5c296cdd8facd.png)
[original] magisk+shamiko has been tested by app root

赋能城市“规、建、运、管、服”——MapGIS CIM平台探索“CIM+”多场景应用
![[PostgreSQL] PostgreSQL 15 optimizes distinct](/img/7c/89d05171902dd88bd2b5c352c3614f.png)
[PostgreSQL] PostgreSQL 15 optimizes distinct
随机推荐
Leetcode 1304. N different integers with zero and
function/symbol ‘pango_ context_ set_ round_ glyph_ positions‘ not found in library ‘libpango-1.0. so. 0‘x
MGRE 环境下配置OSPF实验
TCP congestion control details | 7 Surpass TCP
Detailed explanation of MySQL show processlist
STL string input / output overload 2
Nature子刊 | 地下水固碳速率与寡营养海洋系统固碳速率相近
Swift 二进制数据与16进制字符串的相互转换
Lychee sound quality high fidelity AI noise reduction technology sharing
Enabling cities to "plan, build, operate, manage and serve" -- MAPGIS CIM platform explores "cim+" multi scenario applications
使用原生js实现按钮的全选功能,简单清晰
[original] magisk+shamiko has been tested by app root
Dream CMS Front Office Search SQL Injection
TCP拥塞控制详解 | 7. 超越TCP
Tikv memory parameter performance tuning
Will causal learning open the next generation of AI? Chapter 9 Yunji datacanvas officially released the open source project of ylarn causal learning
Research and implementation of 5g network Slicing Based on AI intelligent correlation technology
Two misunderstandings of digital transformation
The concept of binary tree and three traversal methods (C language)
LeetCode_17_电话号码的字母组合