BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ camelBUPT (迷茫的人) 于 (Tue Oct 27 09:49:56 2009) 提到: ☆─────────────────────────────────────☆ windfail (目采冥夕绛) 于 (Tue Oct 27 09:50:53 2009) 提到: 排序树？ ☆─────────────────────────────────────☆ ericyosho (ericyosho) 于 (Tue Oct 27 10:21:27 2009) 提到: 平衡二叉树？红黑树？不懂也来凑热闹＠＠ ☆─────────────────────────────────────☆ camelBUPT (迷茫的人) 于 (Tue Oct 27 10:27:30 2009) 提到: http://blog.csdn.net/romandion/archive/2008/05/09/2421370.aspx 可以参考一下，不过我没看懂。 ☆─────────────────────────────────────☆ camelBUPT (迷茫的人) 于 (Tue Oct 27 10:30:06 2009) 提到: 感觉像B-树。【在 camelBUPT 的大作中提到: 】 : http://blog.csdn.net/romandion/archive/2008/05/09/2421370.aspx : 可以参考一下，不过我没看懂。 ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 10:35:01 2009) 提到: 若为非负整数，bitmap应该最好,O(1) 其他情况下RBT也不错，O(lgn) ☆─────────────────────────────────────☆ camelBUPT (迷茫的人) 于 (Tue Oct 27 10:38:32 2009) 提到: 需要的是支持高效插入，删除，查询的数据结构。【在 allen0308 的大作中提到: 】 : 若为非负整数，bitmap应该最好,O(1) : 其他情况下RBT也不错，O(lgn) ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 10:44:33 2009) 提到: 这还不够高效么？ bitmap---对于某数i，插入置bitmap[i]为1，删除置bitmap[i]为0，查询直接bitmap[i]==1即可，当然前提数非负非重复整数集 RBT--除线性的hashtable外，应该也算高效的了吧【在 camelBUPT 的大作中提到: 】 : 需要的是支持高效插入，删除，查询的数据结构。 ☆─────────────────────────────────────☆ jmpesp (垃圾|人渣|缅甸果敢第一司令) 于 (Tue Oct 27 10:50:27 2009) 提到: 【在 allen0308 的大作中提到: 】 : 这还不够高效么？ : bitmap---对于某数i，插入置bitmap[i]为1，删除置bitmap[i]为0，查询直接bitmap[i]==1即可，当然前提数非负非重复整数集 : RBT--除线性的hashtable外，应该也算高效的了吧数据大了，这个bitmap的空间也不容小视吧？还有检索这个所谓的i因为数组是有序的，所以用二分查找复杂度也有O（lgn）吧，所以综合各个方面来讲，用Bitmap的复杂度应该不是O（1）。还有，频繁的增删，用bitmap会导致碎片是不是很大呢？ ☆─────────────────────────────────────☆ camelBUPT (迷茫的人) 于 (Tue Oct 27 10:52:01 2009) 提到: 恩，也行哈。不过貌似可以结合数组和链表来设计一种满足这种需求的数据结构。【在 allen0308 的大作中提到: 】 : 这还不够高效么？ : bitmap---对于某数i，插入置bitmap[i]为1，删除置bitmap[i]为0，查询直接bitmap[i]==1即可，当然前提数非负非重复整数集 : RBT--除线性的hashtable外，应该也算高效的了吧 ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 11:05:39 2009) 提到: 那就可以用数组做hash table，而当插入时发生collision的情况下，则可以用list来解决。但最坏情况的复杂度不能保证【在 camelBUPT 的大作中提到: 】 : 恩，也行哈。 : 不过貌似可以结合数组和链表来设计一种满足这种需求的数据结构。 ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 13:17:24 2009) 提到: 恩，用bitmap时也要看数据集是什么样的，如果数很少，但范围很大则用bitmap就没必要了。空间需要权衡。检索bitmap时直接判断bitmap[i]==1就可以找到i了，没必要二分，时间是有保证的。碎片这个问题我不是很清楚的。【在 jmpesp 的大作中提到: 】 : 数据大了，这个bitmap的空间也不容小视吧？还有检索这个所谓的i因为数组是有序的，所以用二分查找复杂度也有O（lgn）吧，所以综合各个方面来讲，用Bitmap的复杂度应该不是O（1）。还有，频繁的增删，用bitmap会导致碎片是不是很大呢？ ☆─────────────────────────────────────☆ Django (贱狗) 于 (Tue Oct 27 13:25:17 2009) 提到: hash链表跳表 ☆─────────────────────────────────────☆ jmpesp (垃圾|人渣|缅甸果敢第一司令) 于 (Tue Oct 27 15:27:45 2009) 提到: 【在 allen0308 的大作中提到: 】 : 恩，用bitmap时也要看数据集是什么样的，如果数很少，但范围很大则用bitmap就没必要了。空间需要权衡。 : 检索bitmap时直接判断bitmap[i]==1就可以找到i了，没必要二分，时间是有保证的。 : 碎片这个问题我不是很清楚的。查找bitmap[i]==1这个不是那么简单吧。。。如果我要查找某条记录，也要经过一个检索过程吧？所以bitmap[i]==1如何时间有保证呢~~ ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 15:33:17 2009) 提到: 如果你说的记录是整数的话：以32bits interger为例，查找整数i是否在bitmap中的操作为 int test(int i) { return bitmap[i>>5] & ( 1 << ( i & 0x1f ) ) ; } 这当然是常数时间【在 jmpesp 的大作中提到: 】 : 查找bitmap[i]==1这个不是那么简单吧。。。如果我要查找某条记录，也要经过一个检索过程吧？所以bitmap[i]==1如何时间有保证呢~~ ☆─────────────────────────────────────☆ jmpesp (垃圾|人渣|缅甸果敢第一司令) 于 (Tue Oct 27 15:39:13 2009) 提到: 【在 allen0308 的大作中提到: 】 : 如果你说的记录是整数的话： : 以32bits interger为例，查找整数i是否在bitmap中的操作为 : int test(int i) : ................... 你看来不明白我意思了~~我的意思是说，假设我们要检索数组内的某一条记录，那么如何根据这个bitmap来保证时间？ ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 15:50:25 2009) 提到: 没太明白你的意思...具体点儿？【在 jmpesp 的大作中提到: 】 : 你看来不明白我意思了~~我的意思是说，假设我们要检索数组内的某一条记录，那么如何根据这个bitmap来保证时间？ ☆─────────────────────────────────────☆ jmpesp (垃圾|人渣|缅甸果敢第一司令) 于 (Tue Oct 27 15:58:55 2009) 提到: 【在 allen0308 的大作中提到: 】 : 没太明白你的意思...具体点儿？举个例子吧，假设有序数组a[] = { 1,3,4,27,44,89,565,777,777,888...} 现在，我要对数据777进行删除，那么，你这个要获得对应的bitmap的i是不是要对数组有一个检索过程吧？ ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 16:08:43 2009) 提到: 你所说的是用数组存储而我的意思是根本没有这个你说的这个整数数组，只有bitmap。将整数 1,3,4,27,44,89,565,777,777,888...对应到bitmap中相应的bit位上并置为1，其余位为0。删除777时将bitmap[777]置为0即可，置0方法类似test，常数时间。所以没有检索过程。【在 jmpesp 的大作中提到: 】 : 举个例子吧，假设有序数组a[] = { 1,3,4,27,44,89,565,777,777,888...} : 现在，我要对数据777进行删除，那么，你这个要获得对应的bitmap的i是不是要对数组有一个检索过程吧？ ☆─────────────────────────────────────☆ jmpesp (垃圾|人渣|缅甸果敢第一司令) 于 (Tue Oct 27 16:18:51 2009) 提到: 【在 allen0308 的大作中提到: 】 : 你所说的是用数组存储 : 而我的意思是根本没有这个你说的这个整数数组，只有bitmap。将整数 1,3,4,27,44,89,565,777,777,888...对应到bitmap中相应的bit位上并置为1，其余位为0。删除777时将bitmap[777]置为0即可，置0方法类似test，常数时间。所以没有检索过程。哇，这个。。。其实你这个就是hash~~这个空间占用会吓死人的~~ ☆─────────────────────────────────────☆ allen0308 (明光村小村长) 于 (Tue Oct 27 16:23:24 2009) 提到: 呵呵，所以我说空间需要权衡的，就看数据集是什么样了，空间换时间嘛。32bits的interger理论上得占0.5G。其实我觉得最好的方法应该是hash+list了【在 jmpesp 的大作中提到: 】 : 哇，这个。。。其实你这个就是hash~~这个空间占用会吓死人的~~ ☆─────────────────────────────────────☆ jmpesp (垃圾|人渣|缅甸果敢第一司令) 于 (Tue Oct 27 16:31:49 2009) 提到: 【在 allen0308 的大作中提到: 】 : 呵呵，所以我说空间需要权衡的，就看数据集是什么样了，空间换时间嘛。32bits的interger理论上得占0.5G。 : 其实我觉得最好的方法应该是hash+list了恩，算法这种东西很值得考虑，权衡的东西太多了，还是得具体问题具体分析~~ ☆─────────────────────────────────────☆ snowdown (公子陌离) 于 (Tue Oct 27 18:52:50 2009) 提到: 我觉得用AVL实现比较合适吧

[合集] 需要保存一组有序数据，这组数据需要高速的检索，并增删