Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

to palm:STL rbtree vs treap timing test result

Posted by frkstyc at 2005-06-06 15:17:09

数据规模：1至2097152的所有自然数，由STL random_shuffle乱序存放在文件中
测试方法：使用C++标准库的流式文件，从文件读入，排序输出到文件
计时方法：Windows API CreateProcess+GetProccesTimes，取User Time
测试环境：Intel Pentium M 1.5G, 256M, Windows XP SP1
测试结果：
STL set: 15.171s
treap: 16.283s
deque（参考，无排序）：8.672s

Followed by:

没有测试delete，因为你的源代码里面treap的delete好像没有调用 (271) frkstyc 2005-06-06 15:23:39
- palm的treap有问题的，内存瞬间涨到2XXM，机器都死掉了 (0) frkstyc 2005-06-06 16:20:38
  - XP也会死掉哦。。。 (0) js05 2005-06-06 16:34:38
    - 完全没办法了，不停地读虚拟内存，进程也杀不掉 (0) frkstyc 2005-06-06 16:36:41
  - 大概是dispose的问题吧.....郁闷中... (0) palmtenor 2005-06-06 17:03:04
    - 很明显你申请内存就没有释放的 (0) frkstyc 2005-06-06 17:04:02
这个结果，是说明STL rbtree就是比treap高效，还是我的treap代码太烂了？ (271) frkstyc 2005-06-06 16:43:21
- 什么东西进了STL，怎么也该慢个常数倍。。。 (0) js05 2005-06-06 16:57:24
  - 你这个理解肯定是不对的 (0) frkstyc 2005-06-06 17:00:28
    - 不是微软某员工的个人作品么..... (0) palmtenor 2005-06-06 17:06:25
      - 是说P.J. Plauger吗？他不是 (0) frkstyc 2005-06-06 17:07:40
        他不是MS的人 (0) frkstyc 2005-06-06 17:07:56
  - 那怎么理解呢？STL要调用很多的东西吧，感觉上同样的方法，STL必然要慢常数。。。 (0) js05 2005-06-06 17:22:33
    - 不要只想着竞赛的时候没有编译优化的情形，编译优化出来的代码虽然不是人能读的，但在大部分情况下比人能读的代码要高效，而且用STL开发还方便（看一下下面的代码就知道了） (0) frkstyc 2005-06-06 17:26:02
      - 编译优化就是在编译的时候优化吧，那关代码什么事呢？ (0) js05 2005-06-06 17:35:58
        当然论开发，STL之流当然是奇强的。。。 (0) js05 2005-06-06 17:36:35
        关键就是C++引入了inline的概念，STL的那些调用经过编译器之后绝大部分的十分简单的操作都被inline了，也就没有调用的问题了 (0) frkstyc 2005-06-06 17:39:27
        我觉得其实竞赛的时候也应该使用编译优化，同时也要调整缩短时限，常数级的优化实在无聊得很 (0) frkstyc 2005-06-06 17:42:39
        某些时候，优化常数是很必要的。。。 (0) js05 2005-06-06 17:46:54
        比如OI的时候，做提交答案题，优化一下常数，本来要10小时的，变成5小时，就AC了。。。 (0) js05 2005-06-06 17:47:43
        int[] AC，vector<int> TLE就无聊了吧？要做的优化应该是算法上的优化，而不是实现上的优化 (0) frkstyc 2005-06-06 17:48:31
        Re:int[] AC，vector<int> TLE就无聊了吧？要做的优化应该是算法上的优化，而不是实现上的优化 (0) js05 2005-06-06 20:26:29
        自己不能无聊，但是不得不防着无聊的人。。。 (0) js05 2005-06-06 20:27:02
我把源程序贴出来，你们自己比较吧 (271) frkstyc 2005-06-06 17:10:49
- set (368) frkstyc 2005-06-06 17:11:25
- treap (1188) frkstyc 2005-06-06 17:12:05

Post your reply here:

Home Page Go Back To top