好好学习,天天向上
在这个神马都是浮云的年代,我背着理想,带上坚持上路了...
posts - 2, comments - 0, trackbacks - 0, articles - 2
导航
C++博客
首页
新随笔
联系
聚合
管理
<
2024年11月
>
日
一
二
三
四
五
六
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
7
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
给我留言
查看公开留言
查看私人留言
随笔分类
(2)
AS3
C++
编程技巧(1)
个人随笔(1)
脚本语言
游戏服务端
游戏客户端
随笔档案
(2)
2012年10月 (1)
2009年12月 (1)
文章分类
(3)
C++(3)
文章档案
(2)
2013年5月 (1)
2012年10月 (1)
最新随笔
1. 系统功能实现的两种编码方式
2. C# 读写Config文件
搜索
最新评论
阅读排行榜
1. C# 读写Config文件(2832)
2. 系统功能实现的两种编码方式(303)
评论排行榜
1. C# 读写Config文件(0)
2. 系统功能实现的两种编码方式(0)
二分法与Map速度测试
Posted on 2012-10-22 19:58
尘末
阅读(279)
评论(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
=
r
a
nd()
%
TEST_COUNT;
112
map
<
int
,
int
>
::iterator it
=
m_mapInt.find( nFindID );
113
}
114
CCounter::Instance().PrintCounterMS();
115
/Files/lzyuan1006/二分法与Map速度测试.rar
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
DLL中使用CImage关闭调用程序后会卡死的问题另类解决办法
二分法与Map速度测试
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © 尘末