BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ yangsq (yangsq) 于 (Fri Dec 26 14:27:43 2008) 提到: 现在做项目需要处理大数据量，简单说就是想把大约10000000个整数放到一个set里面。我首先用得是C++，就是set insert，结果跑了半天，而用Java的 Hashset add，跑了10几秒就跑完了。都说C++在效率上有优势，可是为什么会产生这样的结果？求大牛说明 ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Fri Dec 26 15:23:37 2008) 提到: 不知道你的代码是怎么写的。有一个问题，如果你知道数据量很大的话，可以在一开始就选取一个大一点的set。默认的set空间很小，你不停地insert很容易就需要频繁地析构和构造新的set对象。 ☆─────────────────────────────────────☆ yangsq (yangsq) 于 (Fri Dec 26 15:51:02 2008) 提到: 不好意思，我是个菜鸟，想问一下怎样选取一个大点的set ☆─────────────────────────────────────☆ Monono (浮云啊~) 于 (Fri Dec 26 17:37:36 2008) 提到: 【在 yangsq 的大作中提到: 】 : 现在做项目需要处理大数据量，简单说就是想把大约10000000个整数放到一个set里面。 : 我首先用得是C++，就是set insert，结果跑了半天，而用Java的 Hashset add，跑了10几秒就 : 跑完了。 : ................... 首先不知道你代码怎么写的其次C++的set常见的版本是用红黑树（平衡树？）实现的，每次插入时间复杂度大约是O(logn)。而Hashset正如它的名字所示，是用Hash实现的，所以每次插入时间复杂度大概是O(1) 我觉得是这个原因 lx接着补充 ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Fri Dec 26 17:56:00 2008) 提到: 哦，这样子啊，学习一下。以前从来没有从数据结构上考虑过。 @@ 【在 Monono 的大作中提到: 】 : 首先不知道你代码怎么写的 : 其次C++的set常见的版本是用红黑树（平衡树？）实现的，每次插入时间复杂度大约是O(logn)。 : 而Hashset正如它的名字所示，是用Hash实现的，所以每次插入时间复杂度大概是O(1) : ................... ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Fri Dec 26 18:06:00 2008) 提到: 发现C++里面也有hash_set这样的数据结构。 LZ可以试着用一下。估计速度也就上去了。 ☆─────────────────────────────────────☆ coolfantasy (Cool) 于 (Fri Dec 26 18:12:57 2008) 提到: 应该没这么明显吧。。估计lz代码有问题【在 ericyosho (ericyosho) 的大作中提到: 】 : 发现C++里面也有hash_set这样的数据结构。 : LZ可以试着用一下。 : 估计速度也就上去了。 : ................... ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Fri Dec 26 18:36:55 2008) 提到: 嗯，想了想，还真是。 LZ说的是插入的效率不高，没提到搜索的效率不高。还真可能是代码的问题。【在 coolfantasy 的大作中提到: 】 : 应该没这么明显吧。。估计lz代码有问题 ☆─────────────────────────────────────☆ yangsq (yangsq) 于 (Fri Dec 26 18:53:37 2008) 提到: #include <iostream> #include <set> using namespace std; #include <windows.h> int main(int argc, char* argv[]) { set <int> test_set; int t = GetTickCount(); for(int i = 0; i < 10000000; i++) { test_set.insert(i); } t = GetTickCount()-t; cout <<t <<endl; return 0; } 不好意思，这个是我测试的代码，对比了一个同样的java代码，可是C++用时要多得多 ☆─────────────────────────────────────☆ Monono (浮云啊~) 于 (Fri Dec 26 19:10:49 2008) 提到: 【在 yangsq 的大作中提到: 】 : #include <iostream> : #include <set> : using namespace std; : ................... 把java的测试代码，以及最终时间测试结果都贴一下吧。机子上没有java环境 ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Fri Dec 26 19:21:28 2008) 提到: 我用你的代码跑了一下，直接就挂掉，core dump了，应该是溢出，core文件有100M那么大。环境是 SunOS gcc 4.0.3 =.= ☆─────────────────────────────────────☆ zhoujin010 (忆邮未尽) 于 (Fri Dec 26 21:44:08 2008) 提到: vc下编译成release版本的再执行，3秒 ☆─────────────────────────────────────☆ famousz (Fam) 于 (Fri Dec 26 21:49:09 2008) 提到: 大致测试效率应该是差不多的。我这里c++不开优化的话比java慢一些 ☆─────────────────────────────────────☆ zhoujin010 (忆邮未尽) 于 (Fri Dec 26 21:54:27 2008) 提到: 如楼上所说，set与hashset的数据结构是不一样的，插入操作的时间复杂度本来就不一样。通常情况下hash比平衡树的效率要高，但通过以上测试发现C++的set性能高于java的hashset，是由于C++本身效率比java高，但如果插入的数目继续增大，会发现java的hashset会超过C++中的set。对比语言的效率应该使用相同的数据结构，你应该拿java中的treeset或treemap跟C++中的set比才有意义。 ☆─────────────────────────────────────☆ yangsq (yangsq) 于 (Fri Dec 26 23:06:29 2008) 提到: 谢谢各位的回答，我问这个问题的目的并不是想比较C++的set和Java的hashset，而是我现在的项目需要处理很大的数据量。但是我上面贴出来就是个例子。我也在CSDN上发了同样的帖，他们的回答是使用： set insert(iterator, 100); 如： temp_set.insert(temp_set.end(), 10000) 试过了，感觉效果还是比较明显的。同时我测试过了Dev C++ 和VC++，两个运行的时间也差别很大。 ☆─────────────────────────────────────☆ mmgroup (からす) 于 (Fri Dec 26 23:26:32 2008) 提到: iterator干吗用的能改变数据结构么还是改变了算法 ☆─────────────────────────────────────☆ yangsq (yangsq) 于 (Fri Dec 26 23:29:44 2008) 提到: 我也不太清楚，查了http://www.cplusplus.com/reference/stl/set/insert.html，有下面的代码和注释： myset.insert (it,25); // max efficiency inserting ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Sat Dec 27 00:13:28 2008) 提到: iterator，你可以简单认为它就是指针，其实就是一个对指针做了封装的对象。 ☆─────────────────────────────────────☆ zhoujin010 (忆邮未尽) 于 (Sat Dec 27 10:14:22 2008) 提到: set insert(iterator, 100); 如果被如果被插入到set里的数据本身是有序的，可以根据上一次插入的结果直接得到本次插入的指定位置，而不需要从树的根开始比较，因此是O（1）的时间复杂度 ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Sun Dec 28 11:44:09 2008) 提到: set是红黑树，如果不需要删除就用hash ☆─────────────────────────────────────☆ ocaenheart (起个什么好呢？) 于 (Sun Dec 28 12:27:32 2008) 提到: 用stl的hash_map吧 ☆─────────────────────────────────────☆ hg (gyh) 于 (Mon Dec 29 16:51:12 2008) 提到: 为什么那个程序用不同的编译环境编译出来的运行时间差别那么大? 16.609秒 DEV-C 5.219秒 VC6 28.828秒 VS2005 看了VC6效率确实比较高... ☆─────────────────────────────────────☆ jokerlee (Jackal The Dire) 于 (Mon Dec 29 17:51:07 2008) 提到: windows上跑的gcc不能说明问题 ☆─────────────────────────────────────☆ yegle (一阁@SL小分队) 于 (Mon Dec 29 18:29:06 2008) 提到: -O3 【在 hg (gyh) 的大作中提到: 】 : 为什么那个程序用不同的编译环境编译出来的运行时间差别那么大? : 16.609秒 DEV-C : 5.219秒 VC6 : ................... ☆─────────────────────────────────────☆ zhbconan (冲田总受|路过团散骑|SL|猪头帮|天山南北) 于 (Mon Dec 29 18:45:40 2008) 提到: 这话说的... 那wine上跑的vc还不能说明问题呢... 博尔特在中国打败了美国人也说明不了问题。 lz的测试说明，至少在windows环境下gcc是比vc慢的。至于在linux上，想也知道结果如何。【在 jokerlee (Jackal The Dire) 的大作中提到: 】 : windows上跑的gcc不能说明问题 ☆─────────────────────────────────────☆ zhoujin010 (忆邮未尽) 于 (Tue Dec 30 00:06:45 2008) 提到: windows上gcc本来就不如vc的编译器 ☆─────────────────────────────────────☆ Wavestone (阳光空气水) 于 (Tue Dec 30 08:22:21 2008) 提到: -03是什么选项？【在 yegle 的大作中提到: 】 : -O3 ☆─────────────────────────────────────☆ guo (计忆邮心|郭) 于 (Tue Dec 30 09:07:32 2008) 提到: 优化【在 Wavestone 的大作中提到: 】 : -03是什么选项？ ☆─────────────────────────────────────☆ huyuanmeix (crocodile) 于 (Tue Dec 30 09:58:26 2008) 提到: 来学习一下 ☆─────────────────────────────────────☆ Wavestone (阳光空气水) 于 (Tue Dec 30 14:18:03 2008) 提到: /0x？【在 guo 的大作中提到: 】 : 优化 ☆─────────────────────────────────────☆ kevinew (132|合鸟) 于 (Tue Dec 30 14:49:09 2008) 提到: 主要是linux上没有VC ，所以也就没法用lin上的gcc和vc比了【在 zhoujin010 的大作中提到: 】 : windows上gcc本来就不如vc的编译器 ☆─────────────────────────────────────☆ guo (计忆邮心|郭) 于 (Tue Dec 30 16:36:58 2008) 提到: gcc的优化选项是-On VC的好像是/On吧类似吧【在 Wavestone 的大作中提到: 】 : /0x？ ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Tue Dec 30 16:51:12 2008) 提到: VC的 /On 选项，是在默认的release里面配置的。 gcc的 -On选项，在命令行中是需要手动指定的，或者在makefile中明确写明。由于没有安装devCPP，因此devCPP中的release版本有没有默认设置优化选项，不可知。 ☆─────────────────────────────────────☆ maniac (maniac) 于 (Tue Dec 30 20:36:12 2008) 提到: c++容器就是很低效，没啥好说的自己重新写一个，用hash方法来实现set，会快很多标准库里面的set要跟原有的一个个比过再放进去，如果我没记错的话。这不是语言问题，是算法问题 ☆─────────────────────────────────────☆ taps (水龙头) 于 (Tue Dec 30 21:57:40 2008) 提到: 容器的实现不是C++语言的事情吧，跟编译器有关，是每个C++编译器的实现都很低效么？【在 maniac 的大作中提到: 】 : c++容器就是很低效，没啥好说的 : 自己重新写一个，用hash方法来实现set，会快很多 : 标准库里面的set要跟原有的一个个比过再放进去，如果我没记错的话。 : ................... ☆─────────────────────────────────────☆ bada (BADA) 于 (Tue Dec 30 21:57:41 2008) 提到: c++容器效率低？搞笑呢吧。 LZ的问题是c++用的是set ,而java用得是hashmap，才导致的结果。而且CSDN上面给的建议是个偷巧的方法，因为LZ的例子是从1加到10k，数字是依次递增的。所以每次都Insert到最后，然后看情况旋转；这个比单独Insert要快一个找lgn的时间。如果Insert的东东不是递增的，CSDN的方法就不能了。而hashmap时间约等于o1，自然快非常多了。不过这个靠人品，因为如果冲撞了，自然更废时间，可以精心构造一组Int数据（恰好每次除以种子数余数都一样，种子数就是那几个质数，ＳＴＬ里面都是写死的）正好都碰撞，这样时间复杂度就是o（n），反而慢了。 ☆─────────────────────────────────────☆ bada (BADA) 于 (Tue Dec 30 22:00:45 2008) 提到: 而其，自己动手写ｈａｓｈ的ｓｅｔ，那不就是hashset嘛，【在 maniac 的大作中提到: 】 : c++容器就是很低效，没啥好说的 : 自己重新写一个，用hash方法来实现set，会快很多 : 标准库里面的set要跟原有的一个个比过再放进去，如果我没记错的话。 : ................... ☆─────────────────────────────────────☆ taps (水龙头) 于 (Tue Dec 30 22:46:12 2008) 提到: 一个好的hash函数会用随机化来让大量冲撞的问题发生的概率非常小，STL真的就那么几个么...天... 【在 bada 的大作中提到: 】 : c++容器效率低？搞笑呢吧。 : LZ的问题是c++用的是set ,而java用得是hashmap，才导致的结果。 : 而且CSDN上面给的建议是个偷巧的方法，因为LZ的例子是从1加到10k，数字是依次递增的。所以每次都Insert到最后，然后看情况旋转；这个比单独Insert要快一个找lgn的时间。如果Insert的东东不是递增的，CSDN的方法就不能了。 : ................... ☆─────────────────────────────────────☆ bada (BADA) 于 (Tue Dec 30 22:47:46 2008) 提到: 你说的hash函数，和我说的hashmap的东西不是一个东西啊。hashmap就是除求余啊。未来的冲撞无法预知，怎么能随机化呢？我看到的GCC的STL的hashmap源码，是这样的....... 【在 taps 的大作中提到: 】 : 一个好的hash函数会用随机化来让大量冲撞的问题发生的概率非常小，STL真的就那么几个么...天... ☆─────────────────────────────────────☆ taps (水龙头) 于 (Tue Dec 30 23:01:33 2008) 提到: hashmap不也是对key进行hash函数求值么，如果每次在建立hashmap时随机生成hashfunction()，就相当于我们每次有无数多的hash函数中随机选择一个，这样hash函数就不会固定对某些已知的输入组合非常敏感，我是这样理解的，当然前提要保证不能随机出非常烂的hash函数.... 【在 bada 的大作中提到: 】 : 你说的hash函数，和我说的hashmap的东西不是一个东西啊。hashmap就是除求余啊。未来的冲撞无法预知，怎么能随机化呢？ : 我看到的GCC的STL的hashmap源码，是这样的....... ☆─────────────────────────────────────☆ bada (BADA) 于 (Tue Dec 30 23:10:03 2008) 提到: 你说的是类似MD5的散列，那个要很长的时间，而且本身散列的结果是一个范围很大的值，怎么存到一个array里面呢？ STL的hashmap就是用除留余数的方法，当发现当前存放的元素超过的array的大小，会自动enlarge，并更换另一个除数。一般除数的选择是当前元素的个数的2倍的的质数组里面最小的那个。而这个质数组是固定的，只有28个，从53开始。你看看STL源码hashtable的东东，就知道我的意思了。【在 taps 的大作中提到: 】 : hashmap不也是对key进行hash函数求值么，如果每次在建立hashmap时随机生成hashfunction()，就相当于我们每次有无数多的hash函数中随机选择一个，这样hash函数就不会固定对某些已知的输入组合非常敏感，我是这样理解的，当然前提要保证不能随机出非常烂的hash函数.... ☆─────────────────────────────────────☆ taps (水龙头) 于 (Tue Dec 30 23:16:15 2008) 提到: 我是视图想看来着，我也不是学计算机的，面对晦涩的代码每次我都劝自己还是学点别的吧，哎... 【在 bada 的大作中提到: 】 : 你说的是类似MD5的散列，那个要很长的时间，而且本身散列的结果是一个范围很大的值，怎么存到一个array里面呢？ : STL的hashmap就是用除留余数的方法，当发现当前存放的元素超过的array的大小，会自动enlarge，并更换另一个除数。一般除数的选择是当前元素的个数的2倍的的质数组里面最小的那个。而这个质数组是固定的，只有28个，从53开始。 : 你看看STL源码hashtable的东东，就知道我的意思了。 ☆─────────────────────────────────────☆ bada (BADA) 于 (Tue Dec 30 23:34:16 2008) 提到: 推荐你看看STL代码剖析，结合STL代码看看，不错。千万别看vc的STL源码，那个应该是用了混淆器，根本不让你看懂。还是看GCC的爽.... ☆─────────────────────────────────────☆ lifesider (走在人生边上) 于 (Wed Dec 31 22:48:11 2008) 提到: STL中的set是按节点存储的,因此每次都会调用new,而且set的insert成员函数采用不同的形式其效率也是不一样的.而楼主采用的基本的插入形式当数据量很大的时首先会有一个搜寻合适位置时间然后才是new节点然后才是插入操作,时间消耗当然多了,不过java我不了解,因而我也不好作比较其次我认为最重要的关键还是在搜寻元素时的可能出现的分页查找时间消耗吧.当数据量很大时,用关联容器可能出现的分页错误也会增多,这样的++和--操作时的时间消耗也会增多,这也是影响关联容器效率低下的原因楼主可以参考Effective STL

[合集] 请教C++ 容器效率问题(set 存放大数据量)