好好学习，天天向上

在这个神马都是浮云的年代，我背着理想，带上坚持上路了...
posts - 2, comments - 0, trackbacks - 0, articles - 2

二分法与Map速度测试

Posted on 2012-10-22 19:58 尘末 阅读(280) 评论(0)  编辑 收藏 引用 所属分类: C++
最开始我不太了解map的实现机制，就做了一个这样的比较，结果发现自己写的二分法实际上还要快一些，下面贴代码：
  1//**********************************************************************
  2    //制造基础数据
  3    vector<int> m_vtBaseData;
  4    for ( int i = 0; i < TEST_COUNT; i++ )
  5    {
  6        m_vtBaseData.push_back( i);
  7    }
  8
  9    //打乱顺序
 10    for ( int i = 0; i < TEST_COUNT; i++ )
 11    {
 12        int nStart = rand() % TEST_COUNT;
 13        int nEnd = rand() % TEST_COUNT;
 14        if ( nEnd != nStart )
 15        {
 16            swap( m_vtBaseData[nStart], m_vtBaseData[nEnd] );
 17        }
 18    }
 19
 20    //*********************************************************************
 21    //开始测试
 22    vector<int> m_vtInt;
 23    map<int, int> m_mapInt;
 24 
 25    int nLen = m_vtBaseData.size();
 26    int    arrInt[TEST_COUNT];
 27    memset( &arrInt, 0, TEST_COUNT );
 28
 29    //测试vecter插入
 30    cout<<"vector插入耗时:";
 31    CCounter::Instance().StartCounter();
 32    for ( int i = 0; i < nLen; i++ )
 33    {  
 34        int nID = m_vtBaseData[i];
 35        if ( m_vtInt.size() <= 0 )
 36        {
 37            m_vtInt.push_back( nID );
 38        }
 39        else
 40        {
 41            //二分法查找位置，插入
 42            int left=0;
 43            int right=m_vtInt.size()-1;
 44            while(left<=right)
 45            {
 46                int middle=(left+right)/2;
 47                if (nID>m_vtInt[middle] && ( middle+1 > right || nID < m_vtInt[middle+1] )) 
 48                {
 49                    m_vtInt.insert( m_vtInt.begin() + middle + 1, nID );
 50                    break;
 51                }
 52                if (nID>m_vtInt[middle]) 
 53                {
 54                    left=middle+1;
 55                }
 56                else 
 57                {
 58                    if ( middle == 0 )
 59                    {
 60                        m_vtInt.insert( m_vtInt.begin(), nID );
 61                        break;
 62                    }
 63                    right=middle-1;
 64                }
 65            } 
 66        }
 67    }
 68    CCounter::Instance().PrintCounterMS();
 69
 70
 71    //测试map插入
 72    CCounter::Instance().StartCounter();
 73    for ( int i = 0; i < nLen; i++ )
 74    {
 75        int nID = m_vtBaseData[i];
 76        m_mapInt.insert( make_pair( nID, nID ) );
 77    }
 78    CCounter::Instance().PrintCounterMS();
 79
 80
 81    //测试vector查找 
 82    CCounter::Instance().StartCounter();
 83    for ( int i = 0; i < TEST_COUNT; i++ )
 84    {
 85        int nFinded = 0;
 86        int nFindID = rand() % TEST_COUNT;
 87
 88        // 极速二分查找
 89        int left=0;
 90        int right=m_vtInt.size()-1;
 91        while(left<=right)
 92        {
 93            int middle=(left+right)/2;
 94            if (nFindID==m_vtInt[middle]) 
 95            {
 96                nFinded = middle;
 97                break;
 98            }
 99            if (nFindID>m_vtInt[middle]) 
100                left=middle+1;
101            else 
102                right=middle-1;
103        }  
104    }
105    CCounter::Instance().PrintCounterMS();
106
107    //测试map查找 
108    CCounter::Instance().StartCounter();
109    for ( int i = 0; i < TEST_COUNT; i++ )
110    { 
111        int nFindID = rand() % TEST_COUNT;
112        map<int, int>::iterator it = m_mapInt.find( nFindID );
113    }
114    CCounter::Instance().PrintCounterMS();
115


/Files/lzyuan1006/二分法与Map速度测试.rar

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理