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

今天发现treap的性价比比AVL高的不是一点啊.....再加上优质的MC随机数发生器....（测试结果见内）

Posted by palmtenor at 2005-06-06 11:35:02

n=2000000,insert->output->delete
Pentium4 2.8G HT
Compiled with O3
随机：
19.16s
顺序：
11.33s

Followed by:

给我发一个吧，有删除吗？ (110) TN 2005-06-06 11:36:47
坚决使用SPLAY，删除实在太爽了。。。 (110) js05 2005-06-06 11:40:55
- 这两个那个性价比更高？ (0) TN 2005-06-06 11:41:56
  - MS是treap比较快吧，不过也是有限的快。。。 (0) js05 2005-06-06 11:43:13
    - 那编程复杂度呢？ (0) TN 2005-06-06 11:43:53
      - 不考虑删除的话，MS差不多，都要左旋右旋的，但是SPLAY的删除很方便，比不同的BST还方便。。。 (0) js05 2005-06-06 11:45:05
        可以这样理解，SPLAY的删除实际上就是插入。。。 (0) js05 2005-06-06 11:46:19
        这个怎么理解..... (0) palmtenor 2005-06-06 11:50:16
        看下面。。。 (0) js05 2005-06-06 11:51:26
        可是我怎么听说Splay删除特麻烦...... (0) TN 2005-06-06 11:46:21
        怎么麻烦了，把删除的元素调整到跟，然后合并左右子树，怀疑你听的不是这个方法。。。 (0) js05 2005-06-06 11:47:34
        不是删除的时候也要展开一下么？ (0) palmtenor 2005-06-06 13:04:54
        删除的原理不同，那种删除是当成普通BST删除，然后再调整的。。。 (0) js05 2005-06-06 13:24:44
        我看的那版splay还有什么zig...zag....太XX了..... (0) palmtenor 2005-06-06 11:46:49
        这个就是左旋右旋吧，不知道为什么叫这个名字。。。 (0) js05 2005-06-06 11:48:03
      - 用RK删点法,treap的删除比插入还简单。。。 (0) zhougelin 2005-06-06 13:27:12
        用RK删点法？ (0) palmtenor 2005-06-06 13:43:03
        同不理解，是不是什么把优先级搞小，然后调到顶的方法？ (0) js05 2005-06-06 14:01:57
        当然不是，删除不需要旋转 (0) zhougelin 2005-06-06 14:25:46
        确实诡异，我还是用我的SPLAY吧。。。 (0) js05 2005-06-06 14:32:31
有人帮着跟STL的red black比一下？ (110) palmtenor 2005-06-06 11:48:34
- STL不显然慢吗/ (0) js05 2005-06-06 11:49:48
  - 加上编译优化呢？ (0) TN 2005-06-06 11:50:10
    - 不知道，RB树从没调对过。。。 (0) js05 2005-06-06 11:50:48
- 特别不解STL为什么要用RB....比效果显然AVL最好 (0) palmtenor 2005-06-06 11:51:38
  - 这个结论实测过么？ (0) frkstyc 2005-06-06 13:08:19
    - 至少从平衡度来讲应该是AVL最平衡~ (0) palmtenor 2005-06-06 13:11:31
      - 我写了一个和POJ计时原理差不多的东西，把你的程序给我我可以测一下时间 (0) frkstyc 2005-06-06 13:12:19
        哦？说说？用什么写得？ (0) TN 2005-06-06 13:13:43
        首先编译成exe，用CreateProcess创建进程，用GetProcessTimes获取时间 (0) frkstyc 2005-06-06 13:14:29
        GetProcessTime？ (0) TN 2005-06-06 13:14:23
        JobProcess里面的东西，不太会用。。。 (0) js05 2005-06-06 13:25:34
        不够这样测的是什么时间？是系统时间还是CPU时间，还是实际的时间？ (0) js05 2005-06-06 13:30:20
        进程占用的user time (0) frkstyc 2005-06-06 13:34:35
      - 不是越平衡越好的，还要考虑维护平衡的代价。。。 (0) js05 2005-06-06 13:23:52
    - styc教我怎么用STL的RB，我比比 (0) palmtenor 2005-06-06 13:11:50
    - 忽然发现做2201的时候还真写过一个treap，现用我自己的测一下吧，看14:00有没有结果出来 (0) frkstyc 2005-06-06 13:26:06
      - 在收拾东西，再等一下吧 (0) frkstyc 2005-06-06 13:52:51
  - 为什么这么说？不都是平衡的吗? (0) TN 2005-06-06 13:10:00
    - 不是严格平衡的啊...自认为平衡性:AVL>RB>Treap>Splay (0) palmtenor 2005-06-06 13:44:25
      - AVL没有RB平衡吧 (0) zhougelin 2005-06-06 14:26:20
        怎么都爱比最BT的情况。。。 (0) js05 2005-06-06 15:50:12

Post your reply here:

Home Page Go Back To top