面对查找需求如何选择容器

在写代码的时候，即使编程老手经常会遇到一个不知道如何抉择的事情，面对查询的需求如何选择容器，容器的大小等因素也会困扰我们的选择。为什么呢？新手面对查询往往会直接选择map，因为map是内部是支持查询函数的,但老手知道map是通过复杂性换取查询的性能的（map的实现往往是红黑树），那如果要保存的数据个数不多呢，是否值得使用map这样的容器呢？

最近两天写了几行短小的代码，针对这个问题进行了一测试，测试对vector,map,hash_map三种有代表性的容器进行了测试，测试容器的长度为10，50，100，200，500，1000.测试的方法是使用int作为测试对象，vector的查询使用顺序查找，map和hash_map的查询使用容器的find函数。为了能表现出测试结果，查询测试了1000000次，开始时，查询的数据我用rand函数产生随机数作为查询对象，后来发现好像对查询干扰过大，最后还是使用了顺序数据作为查询对象。

由于测试结果数据枯燥，我在后面再附录上测试的程序。每个测试都作了3次，取平均值给大家看看结果。测试使用的是STLPort，Visual Studio 2003的DEBUG版本。测试结果如下：

                                                                                                                                                             表1 各种容器的耗时

容器容纳的尺寸

vector(ms)

map(ms)

hash_map(ms)

10

578

1333

1333

20

1078

1562

1328

50

2520

1921

1328

100

4953

2176

1328

200

9806

2422

1322

500

24437

2739

1323

1000

48827

2942

1317

 

在容器的数量小于20个的时候，vector的还表现良好，即使有查询的需求，也可以考虑直接选择vector，但当容器的数据超过50个以后、，map的优势就显示出来了。而且当容器的容量继续增大后，map的查询速度增加也很平稳，当然这和map的实现是采取红黑树，查询的时间复杂度是log2(N)有关。而且hash_map（unorder_map）表现只能用稳定高效形容。所以在大部分时候hash_map是我们的首选。

由于测试中有其他的干扰信息，所以测试数据不等于实际效率。这个数据只是一个参考数据。但是我们大致可以得到一些感觉，容器的尺寸小于20时，我们大可以选择vector作为容器。不用选择更加复杂的容器。如果要容纳的对象个数大于50而且需要查询的时候，vector就不要选择了。用更快的容器。对于map和hash_map，优先选择hash_map。当然我说的是STLport的hash_map，不是微软默认的。我在前面《慎用Visual Studio C++默认的hash_map》的文章说明过这个问题了。在此不复述了。

同时测试的是很我还测试一个其他问题，就是swtich case的性能，发现swtich case 的性能基本不会随case的条件增加而增加耗时（懂汇编的要笑话我了，哈哈），而且非常非常非常非常快，所以，如果有时候你追求的极限性能的目标，而且可以用swtich case的时候，可以考虑用这个比较“丑陋”一点的写法。

BTW:《c++编程规范》一书的第76条是，默认使用vector,否则使用其他容器。其中提到了选择容器的3个原则：

1.    正确性事，简单，清晰是第一位的

2.    在必要时考虑效率

3.    尽可能编写事务安全的代码。（注意插入和删除的迭代器失效问题的影响）

 

 

附录测试代码如下，我懒得写注释了。偷懒。

#include <stdio.h>

#include <string.h>

#include <time.h>

#include <math.h>

#include <stdlib.h>

#include <conio.h>

#include <iostream>

#include <fstream>

#include <memory.h>

#include <map>

#include <hash_map>

#include <ace/OS.h>

#include <ace/Time_Value.h>

#include <ace/SString.h>

#include <ace/Shared_Memory_MM.h>

#include <ace/Shared_Memory_SV.h>

#include <ace/Mem_Map.h>

#include <ace/SV_Shared_Memory.h>

 

using namespace std;

 

const size_t TEST_NUMBER = 100000*10;

void test_findwith_container(size_t container_len)

{

    vector<int>          int_vector;

    map<int,int>         int_map;

    hash_map<int,int>    int_hash;

 

    int_vector.resize(container_len);

    int_hash.resize(container_len);

    //

    for(size_t i = 0;i<container_len;i++)

    {

        int_vector[i]=i;

        int_map[i] = i;

        int_hash[i]=i;

    }

    ACE_Time_Value tvStart(0);

    ACE_Time_Value tvEnd(0);

    ACE_Time_Value tvPassTime(0);

 

    tvStart = ACE_OS::gettimeofday();

 

    for (size_t i= 0;i<TEST_NUMBER;++i)

    {

        int find_number =  i%container_len;

        //

        for(size_t j = 0;j<container_len;j++)

        {

            if (int_vector[j]==find_number)

            {

                break;

            }

        }

    }

    tvEnd = ACE_OS::gettimeofday();

    tvPassTime = tvEnd - tvStart;

    cout<<"test vector gettimeofday :"<<tvPassTime.msec()<<" "<<endl;

    tvStart = ACE_OS::gettimeofday();

    for (size_t i= 0;i<TEST_NUMBER;++i)

    {

        int find_number =  i%container_len;

        int_map.find(find_number);

    }

    tvEnd = ACE_OS::gettimeofday();

    tvPassTime = tvEnd - tvStart;

    cout<<"test map gettimeofday :"<<tvPassTime.msec()<<" "<<endl;

    tvStart = ACE_OS::gettimeofday();

    for (size_t i= 0;i<TEST_NUMBER;++i)

    {

        int find_number =  i%container_len;

        int_hash.find(find_number);

    }

    tvEnd = ACE_OS::gettimeofday();

    tvPassTime = tvEnd - tvStart;

    cout<<"test hash gettimeofday :"<<tvPassTime.msec()<<" "<<endl;

}

 

//

int main(int argc, ACE_TCHAR* argv[])

{

  

    for (int j=0;j<3;++j)

    {

        cout<<"container length = 10 "<<endl;

        test_findwith_container(10);

        cout<<"container length = 20 "<<endl;

        test_findwith_container(20);

        cout<<"container length = 50 "<<endl;

        test_findwith_container(50);

        cout<<"container length = 100 "<<endl;

        test_findwith_container(100);

        cout<<"container length = 200 "<<endl;

        test_findwith_container(200);

        cout<<"container length = 500 "<<endl;

        test_findwith_container(500);

        cout<<"container length = 1000 "<<endl;

        test_findwith_container(1000);

    }

 

    _getch();

    return 0;

}

 

# 测试
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生