一点很纱布的想法，一些琐碎的聊天记录

稍微描述一下基本构思和比较一下复杂度（可能很大误），很粗糙的构思，应该还有优化余地
暂时命名为mixedlist
mixedlist

*维护一个链表
*每个节点结构如下 {length，array，next}
*维护一个pre用于遍历时保存上一节点
*cursor 遍历时保存当前节点
*size 大小
*capacity 节点数量*数组容量(如果size/capacity达到阈值则运行碎片整理，阈值是否用户指定再讨论)
*arraylength 保存每个节点内每个数组的长度，由用户指定

常用操作实现与复杂度分析

无序的
随机访问：找到节点，定位索引  O(logN)
插入头部：若首节点满则头部加节点 O(1)，否则插到首节点头部(同arraylist一样可以使用保存头并首尾相连来优化)  O(logN)
插入尾部： 直接丢尾节点,如果满员在尾部加新节点 O(1)
删除头部： 头节点移除首元素 为空则干掉所属节点 O(logN)
删除尾部： 移除尾元素 为空则干掉所属节点 O(1)
随机索引插入： 计算偏移量找到节点 如果不满直接插 如果满了紧接着所属节点开新节点 O(2logN)
随机索引删除： 计算偏移量找到节点 删除并调整数组 如果为空干掉这个节点 O(2logN)
查找数据： 遍历 O(N)
数据前后插入： 查找数据 如果不满直接插 满了开新 O(N+logN)
数据删除： 查找数据 删除并调整数组 如果为空干掉这个节点 O(N+logN)
整理碎片： a遍历节点找未满的，依次将后一节点元素前移（闲置索引）个位置,干掉为空的 O(N+logN)?
b或者干脆新建一个，依次从尾部插入O(N)
我倾向a方案，最起码省内存一点，虽然理论值较差但是感觉上还是比新建一个要好
排序：这种情况显然堆排好（建个新的mixedlist，堆排时重新插入），快排你去死一死吧   O(NlogN)

有序的
(考虑要不要维护一个传统的增长数组，保存区间和每个节点的指针，用于链表的2分查找?)
查找 遍历找到节点 2分找到位置 O(logN+log(logN))
插入 遍历找到节点 2分找到位置 插入(满了开新的) O(2logN+log(logN))
其他与无序相同


arraylist
无序的
随机访问： O(1)
插入头部： O(N) 虽然可以维护一个head但是最坏值仍是O(N)
插入尾部： O(1)
删除头部： O(N)同插入头部
删除尾部： O(1)
随机索引插入：该索引后依次后移  O(N)
随机索引删除，该索引后依次前移  O(N)
查找数据 O(N)
数据(前)后插入：查找数据 后续后移 插入 O(N) 但是这个O(N)肯定是最差情况(遍历了前半部分，移位了后半部分)时间复杂度与前面的
O(N+logN)比只多不少
数据删除：同数据前后插入,最差的O(N)
resize：这个开销理论也只是O(N)，实际上需要申请两倍（常见的实现）于现有容量的内存，挨个复制元素。
排序：这个多了去了..爱用啥用啥

有序的
查找 2分查找没啥好说的 O(logN)
插入 2分查找与常规插入 O(N+logN)

linkedlist
无序的
随机访问：O(N)
插入头部：O(1)
插入尾部：O(1)
删除头部：O(1)
删除尾部：O(1)
随机索引插入：O(N)
随机索引删除：O(N)
查找数据 O(N)
数据(前)后插入：O(N)若是传入节点则为O(1)
数据删除:O(N)若是传入节点则为O(1)
排序:也堆排吧... O(NlogN)

有序的
查找 一般来说还是O(N)吧...不确定
插入 也是O(N)?

总结一下
无序情况下
1.随机访问比链表好比数组差
2.尾插入都差不多，头插入比数组好比链表稍差(如果维护一个head的话则理论是都是常数时间)
3.随机索引插入与删除要优于两者
4.按数据插入删除比数组好比链表差
有序情况下
1.查找比链表好比数组差
2.插入比两者要好
*内存碎片的整理是个大问题，但是拿捏好了应该至少不会比同等状况下的数组resize开销更大。而链表本身维护了N个节点，
还有每次插入都是实时的内存分配,其实开销也并不小吧。

再加上FX说的

RednaxelaFX 写道

小数组的一个重要好处就是locality高，容易整个放到高速cache里，于是访问效率高；访问数组元素时本身indirection次数少自然是效率高的原因之一。这些是链状数据结构再怎么也不比上的。另外，由于下标是一种默认的映射关系，它的空间效率也比链表高。

于是还是有一点存在的价值吧...并不是说完全没有适用场景
分析并不精确，甚至可能是谬误，欢迎指正。
----------------------------------------------------------------
好吧..应NS稍微分析一下哈希的性能
假设索引等同于hash的key
按索引访问 插入 删除 hash的时间复杂度理论上是O(1)
但是实际情况是存在再hash，所以也仅仅是理论上常数时间，实际上跟对数时间不会相差太多

而hash的缺点是无序（不能保证按插入的前后有序），当然要有序也可以，只是要以性能为代价。用来实现队列，堆栈这种纯线性的数据结构就明显不如几个list了。
另外一点是，HASH需要维护key和value两个数组（且这两个数组肯定不是满的，装填因子依实现而异），
空间复杂度比较高。

tree的话应用场景太不同了..就懒得比较了

----------------------我是更新的分割线下面的琐碎聊天记录请选择性无视----------------
NS还在不在
2009-6-6  19:49:30  不健康不阳光不向上  NS  突然有个想法
2009-6-6  21:01:00  NS  不健康不阳光不向上  回来鸟
2009-6-6  21:01:31  不健康不阳光不向上  NS  有个想法
2009-6-6  21:01:41  不健康不阳光不向上  NS  做个可伸缩数组
2009-6-6  21:01:49  不健康不阳光不向上  NS  寻址用偏移量
2009-6-6  21:01:55  不健康不阳光不向上  NS  其实就是变体链表
2009-6-6  21:02:01  不健康不阳光不向上  NS  或者说变体hash
2009-6-6  21:02:17  不健康不阳光不向上  NS  这样的话貌似resize之类的开销要小的多
2009-6-6  21:02:27  不健康不阳光不向上  NS  而且按索引删除插入也小的多
2009-6-6  21:02:38  不健康不阳光不向上  NS  不知道有人做过没
2009-6-6  21:02:45  NS  不健康不阳光不向上  ==，是关于什么的想法？
2009-6-6  21:02:53  不健康不阳光不向上  NS  就是数组分N段
2009-6-6  21:02:58  不健康不阳光不向上  NS  这几个段是一个链表
2009-6-6  21:03:12  不健康不阳光不向上  NS  或者说是一个以索引为key的哈希
2009-6-6  21:03:22  NS  不健康不阳光不向上  貌似…… ArrayList
2009-6-6  21:03:38  不健康不阳光不向上  NS  我想了想各种操作时间复杂度比传统的arraylist和linkedlist要好
2009-6-6  21:03:46  不健康不阳光不向上  NS  不是啊...
2009-6-6  21:03:53  不健康不阳光不向上  NS  arraylist的实现是resize
2009-6-6  21:04:00  不健康不阳光不向上  NS  超过大小了增容
2009-6-6  21:04:07  不健康不阳光不向上  NS  这样就要原样拷贝数组
2009-6-6  21:04:15  不健康不阳光不向上  NS  而win32c有个特性
2009-6-6  21:04:25  不健康不阳光不向上  NS  可以再原有数组的后面直接划空间
2009-6-6  21:04:32  不健康不阳光不向上  NS  失败返回Null
2009-6-6  21:04:41  NS  不健康不阳光不向上  o
2009-6-6  21:04:44  不健康不阳光不向上  NS  因为这个空间我一开始是不知道他在不在的
2009-6-6  21:04:50  不健康不阳光不向上  NS  所以这个方法不保险
2009-6-6  21:05:03  不健康不阳光不向上  NS  因为这个空间我一开始是不知道他有没有被使用的
2009-6-6  21:05:18  不健康不阳光不向上  NS  现在我想做个链表
2009-6-6  21:05:20  NS  不健康不阳光不向上  嗯，扩容失败就重新分配内存
2009-6-6  21:05:21  不健康不阳光不向上  NS  保存各个数组
2009-6-6  21:05:26  不健康不阳光不向上  NS  不是
2009-6-6  21:05:30  不健康不阳光不向上  NS  抛弃这种
2009-6-6  21:05:47  不健康不阳光不向上  NS  定义一种在各个语言里面可用数据结构
2009-6-6  21:05:52  不健康不阳光不向上  NS  就是一个大链表
2009-6-6  21:05:55  不健康不阳光不向上  NS  局部是数组
2009-6-6  21:06:03  不健康不阳光不向上  NS  超过大小我分配新节点
2009-6-6  21:06:14  不健康不阳光不向上  NS  按索引访问我事先初始化偏移量
2009-6-6  21:06:32  不健康不阳光不向上  NS  如果要删除指定索引我就局部resize
2009-6-6  21:06:40  不健康不阳光不向上  NS  你想想同样的操作
2009-6-6  21:06:45  不健康不阳光不向上  NS  以arraylist为例
2009-6-6  21:06:49  不健康不阳光不向上  NS  删除指定所以
2009-6-6  21:06:51  不健康不阳光不向上  NS  索引
2009-6-6  21:06:57  不健康不阳光不向上  NS  后面的元素全部前移
2009-6-6  21:07:05  不健康不阳光不向上  NS  linkedlist则需要遍历
2009-6-6  21:07:13  不健康不阳光不向上  NS  都是全局的线性时间复杂度
2009-6-6  21:07:22  不健康不阳光不向上  NS  而我这个只是局部的线性时间复杂度
2009-6-6  21:07:26  不健康不阳光不向上  NS  其他操作类型
2009-6-6  21:07:27  不健康不阳光不向上  NS  完毕
2009-6-6  21:07:39  不健康不阳光不向上  NS  其实也可以看做一个以索引为key的hash
2009-6-6  21:09:04  NS  不健康不阳光不向上  感觉会有点复杂，指针要小心的整
2009-6-6  21:09:15  不健康不阳光不向上  NS  哪里复杂了
2009-6-6  21:09:18  不健康不阳光不向上  NS  比哈希表简单
2009-6-6  21:09:24  不健康不阳光不向上  NS  其实就是个简化的哈希表
2009-6-6  21:09:30  不健康不阳光不向上  NS  有没有人做过
2009-6-6  21:09:38  不健康不阳光不向上  NS  我想这么简单的想法肯定早就有了吧
2009-6-6  21:11:13  不健康不阳光不向上  NS  我初步设想了一下至少跟现有的list效率不相上下
2009-6-6  21:11:24  不健康不阳光不向上  NS  并且有他自己的适用范围
2009-6-6  21:13:08  不健康不阳光不向上  NS  你猜猜我灵感哪来的 就是那个播放器
2009-6-6  21:13:13  不健康不阳光不向上  NS  因为要播放多段
2009-6-6  21:13:14  NS  不健康不阳光不向上  如果你删除一个元素，局部的其它元素移动不？
2009-6-6  21:13:21  不健康不阳光不向上  NS  seek之类的都需要找偏移量
2009-6-6  21:13:39  不健康不阳光不向上  NS  实际上数组跟一个视频文件是一样的嘛
2009-6-6  21:13:45  不健康不阳光不向上  NS  不过是时间和空间的区别
2009-6-6  21:13:53  不健康不阳光不向上  NS  恩
2009-6-6  21:13:59  不健康不阳光不向上  NS  如果删除一个指定元素
2009-6-6  21:14:06  不健康不阳光不向上  NS  重新分配一个新数组
2009-6-6  21:14:13  不健康不阳光不向上  NS  然后重置偏移量
2009-6-6  21:14:53  NS  不健康不阳光不向上  那么这些小数组不定长，如何访问？
2009-6-6  21:15:06  不健康不阳光不向上  NS  预先初始化偏移量
2009-6-6  21:16:10  不健康不阳光不向上  NS  嘛其实还可以优化
2009-6-6  21:16:15  不健康不阳光不向上  NS  不用重分配数组
2009-6-6  21:16:21  不健康不阳光不向上  NS  设为不可用就行了
2009-6-6  21:16:25  不健康不阳光不向上  NS  维护一个长度
2009-6-6  21:16:31  不健康不阳光不向上  NS  下次还能用
2009-6-6  21:16:48  不健康不阳光不向上  NS  总之还很不成熟
2009-6-6  21:16:54  不健康不阳光不向上  NS  很多细节肯定还能优化
2009-6-6  21:17:50  NS  不健康不阳光不向上  分配是 allocator 的事，先不管.
2009-6-6  21:18:08  不健康不阳光不向上  NS  不是啊
2009-6-6  21:18:16  不健康不阳光不向上  NS  例如我有100个元素
2009-6-6  21:18:25  不健康不阳光不向上  NS  每10个分配一个小数组
2009-6-6  21:18:29  不健康不阳光不向上  NS  我删除第33个
2009-6-6  21:18:47  不健康不阳光不向上  NS  原来是准备把低4个数组重新分配成一个9个元素的
2009-6-6  21:19:06  不健康不阳光不向上  NS  现在时把第33个元素移到第4个数组的末尾
2009-6-6  21:19:14  不健康不阳光不向上  NS  然后第四个数组长度-1
2009-6-6  21:19:22  不健康不阳光不向上  NS  重置偏移量
2009-6-6  21:19:23  不健康不阳光不向上  NS  over
2009-6-6  21:19:33  不健康不阳光不向上  NS  偏移量都可以省了
2009-6-6  21:19:38  不健康不阳光不向上  NS  直接用长度算得了
2009-6-6  21:19:53  不健康不阳光不向上  NS  这个分了很多块开销不会大
2009-6-6  21:20:09  不健康不阳光不向上  NS  错了
2009-6-6  21:20:15  不健康不阳光不向上  NS  这个不会分很多块
2009-6-6  21:20:39  不健康不阳光不向上  NS  数据结构果然是相通的
2009-6-6  21:20:48  不健康不阳光不向上  NS  形似数组
2009-6-6  21:20:52  不健康不阳光不向上  NS  其实是链表
2009-6-6  21:20:57  不健康不阳光不向上  NS  又有点像hash
2009-6-6  21:21:32  NS  不健康不阳光不向上  数据结构无非是数组和链表揉来揉去
2009-6-6  21:21:39  不健康不阳光不向上  NS  对头
2009-6-6  21:21:54  不健康不阳光不向上  NS  想找个地方发一下又不敢去JE
2009-6-6  21:21:58  不健康不阳光不向上  NS  肯定被隐藏
2009-6-6  21:21:58  NS  不健康不阳光不向上  不叫 ArrayList 就叫 ListArray..
2009-6-6  21:22:13  不健康不阳光不向上  NS  你觉得如何？
2009-6-6  21:22:51  NS  不健康不阳光不向上  我觉得，如果你优化插入删除，就会越来越list
2009-6-6  21:23:08  NS  不健康不阳光不向上  如果你优化寻址，就会越来越array
2009-6-6  21:23:40  不健康不阳光不向上  NS  不是啊...我是跟目前主流的arraylist 和linkedlist比
2009-6-6  21:24:09  不健康不阳光不向上  NS  随机访问 肯定不如直接的array 但是比linkedlist快多了
2009-6-6  21:24:28  不健康不阳光不向上  NS  头尾插入删除 三者差不多
2009-6-6  21:24:48  不健康不阳光不向上  NS  随机位置插入删除 比那两个都好
2009-6-6  21:25:04  不健康不阳光不向上  NS  按元素插入删除 都是线性时间
2009-6-6  21:25:19  NS  不健康不阳光不向上  linkedlist 也可以通过修改内存分配方式，达到优化访问的效果..
2009-6-6  21:26:26  不健康不阳光不向上  NS  查找我甚至可以开多线程每个小数组单独遍历..
2009-6-6  21:26:59  不健康不阳光不向上  NS  最大的优势是随机位置的插入删除
2009-6-6  21:27:14  不健康不阳光不向上  NS  还有resize
2009-6-6  21:27:22  不健康不阳光不向上  NS  肯定比arraylist要好多了
2009-6-6  21:27:59  不健康不阳光不向上  NS  有一个潜在的问题是内存碎片
2009-6-6  21:28:14  不健康不阳光不向上  NS  这个需要设计一个算法来重用这些碎片
2009-6-6  21:29:58  不健康不阳光不向上  NS  其实我想这么简单的算法肯定有前辈做过了。。。。
2009-6-6  21:31:24  NS  不健康不阳光不向上  我想，a list of arraylist 比较接近你的说法.. 至于叫什么名字不太清楚..
2009-6-6  21:31:34  不健康不阳光不向上  NS  对对对
2009-6-6  21:31:44  不健康不阳光不向上  NS  但是也可以看成hash的变种
2009-6-6  21:31:53  不健康不阳光不向上  NS  以index为key的特殊hash
2009-6-6  21:33:03  不健康不阳光不向上  NS  FX在忙论文就不请教他了
2009-6-6  21:33:42  NS  不健康不阳光不向上  我数据结构课碰上非典，老师都不讲课了直接给我们满分……
2009-6-6  21:34:39  不健康不阳光不向上  NS  = =这个很浅显吧...
2009-6-6  21:35:46  NS  不健康不阳光不向上  想想还有很多问题要处理，如果别人死命往同一个地方插入..
2009-6-6  21:35:57  不健康不阳光不向上  NS  这好办
2009-6-6  21:36:16  不健康不阳光不向上  NS  不停扩容这个局部数组就行了
2009-6-6  21:36:28  不健康不阳光不向上  NS  大不了跟arraylist同等效率
2009-6-6  21:36:52  不健康不阳光不向上  NS  怕就怕插一堆删一堆然后换个地方插一堆又删一堆
2009-6-6  21:37:01  不健康不阳光不向上  NS  这样就内存碎片恐怖了
2009-6-6  21:37:22  NS  不健康不阳光不向上  如果这个东西一开始是 0 大小，通过单个元素插入来张大..
2009-6-6  21:37:31  不健康不阳光不向上  NS  对了
2009-6-6  21:37:43  不健康不阳光不向上  NS  哦..没事想错了
2009-6-6  21:37:47  不健康不阳光不向上  NS  如果无序的话
2009-6-6  21:37:54  不健康不阳光不向上  NS  甚至可以利用空洞来填
2009-6-6  21:37:58  不健康不阳光不向上  NS  不用扩容
2009-6-6  21:38:10  不健康不阳光不向上  NS  哦..错了
2009-6-6  21:38:18  不健康不阳光不向上  NS  有索引肯定有序
2009-6-6  21:38:23  不健康不阳光不向上  NS  想错了
2009-6-6  21:38:37  不健康不阳光不向上  NS  哦对了
2009-6-6  21:38:47  不健康不阳光不向上  NS  我不会扩容这个局部数组
2009-6-6  21:38:55  不健康不阳光不向上  NS  我会开个新的接在这个后面
2009-6-6  21:38:57  不健康不阳光不向上  NS  这样比较好
2009-6-6  21:39:10  不健康不阳光不向上  NS  例如是设置单个最大100
2009-6-6  21:39:17  不健康不阳光不向上  NS  超过100我开新的
2009-6-6  21:39:33  NS  不健康不阳光不向上  嗯，这样好
2009-6-6  21:39:56  不健康不阳光不向上  NS  这样随机删除优势又明显了
2009-6-6  21:40:02  不健康不阳光不向上  NS  总是只在这100个里面找
2009-6-6  21:40:08  不健康不阳光不向上  NS  不是
2009-6-6  21:40:11  不健康不阳光不向上  NS  不是找
2009-6-6  21:40:18  不健康不阳光不向上  NS  是删除后左移
2009-6-6  21:40:20  NS  不健康不阳光不向上  你得记录每段的长度吧
2009-6-6  21:40:23  不健康不阳光不向上  NS  恩恩
2009-6-6  21:40:30  不健康不阳光不向上  NS  长度就是偏移量
2009-6-6  21:40:37  不健康不阳光不向上  NS  长度之和是偏移量
2009-6-6  21:40:39  不健康不阳光不向上  NS  说错了
2009-6-6  21:40:43  NS  不健康不阳光不向上  随机删除得先按这长度算一遍
2009-6-6  21:40:48  不健康不阳光不向上  NS  恩
2009-6-6  21:41:00  不健康不阳光不向上  NS  这个可以根据需要设定单段大小
2009-6-6  21:41:13  不健康不阳光不向上  NS  如果你要找段快就设大一点
2009-6-6  21:41:21  不健康不阳光不向上  NS  这样块就少找起来快
2009-6-6  21:41:28  不健康不阳光不向上  NS  其实就是分而治之
2009-6-6  21:41:46  NS  不健康不阳光不向上  嗯，就是可以定制，让它更 array 或者更 list...
2009-6-6  21:41:54  不健康不阳光不向上  NS  对对对
2009-6-6  21:42:07  不健康不阳光不向上  NS  但是不管怎么在这方面比前两者性能肯定要高
2009-6-6  21:42:11  NS  不健康不阳光不向上  如果每段长为 0 ，就是 list 了，如果长无穷大，就是array 了
2009-6-6  21:42:20  不健康不阳光不向上  NS  因为前两者是用走的
2009-6-6  21:42:25  不健康不阳光不向上  NS  我是用跳的
2009-6-6  21:42:33  不健康不阳光不向上  NS  跳到一个范围才走
2009-6-6  21:42:57      NS 希望与您开始视频通话。接受 (Alt+C) 拒绝 (Alt+D)
2009-6-6  21:43:06  不健康不阳光不向上  NS  若要进行视频通话，需要使用网络摄像机。现在请插入网络摄像机。如果您没有网络摄像机，可以单击此处购买一个
2009-6-6  21:43:08  不健康不阳光不向上  NS  真那啥
2009-6-6  21:43:09      您错过了来自 NS 的视频通话邀请。
2009-6-6  21:43:15  不健康不阳光不向上  NS  单击此处购买一个
2009-6-6  21:43:21  不健康不阳光不向上  NS  MS你真行
2009-6-6  21:44:03  NS  不健康不阳光不向上  其实你考虑的是 查+插入， log n + log n < n + 1
2009-6-6  21:44:26  不健康不阳光不向上  NS  可以这么说
2009-6-6  21:44:33  不健康不阳光不向上  NS  其他方面也有细微优势
2009-6-6  21:44:53  NS  不健康不阳光不向上  纯查比不上array，纯插入比不上 list，不过这个平衡点是你刚好需要的
2009-6-6  21:45:25  不健康不阳光不向上  NS  纯查怎么比不上array。。。
2009-6-6  21:45:30  不健康不阳光不向上  NS  大家都是线性时间
2009-6-6  21:45:34  不健康不阳光不向上  NS  一个个找
2009-6-6  21:45:50  不健康不阳光不向上  NS  纯插入如果是直接给节点肯定比不上list
2009-6-6  21:46:00  不健康不阳光不向上  NS  但是如果是按元素或者按索引那是一样的
2009-6-6  21:46:10  不健康不阳光不向上  NS  按索引我还要高效
2009-6-6  21:46:28  不健康不阳光不向上  NS  按元素是一样的 按索引我这样高效
2009-6-6  21:46:30  NS  不健康不阳光不向上  如果你的元素无序，得遍历…… 如果有序，人家 array 肯定二分最快
2009-6-6  21:46:37  不健康不阳光不向上  NS  恩
2009-6-6  21:46:41  不健康不阳光不向上  NS  但是我也可以二分
2009-6-6  21:46:46  不健康不阳光不向上  NS  只是没那么方便就是了
2009-6-6  21:47:17  NS  不健康不阳光不向上  肯定比有序array的二分弱一点点，只是有序array构造很费事罢了
2009-6-6  21:47:26  不健康不阳光不向上  NS  恩
2009-6-6  21:47:44  不健康不阳光不向上  NS  只要涉及按索引随机插入删除肯定这样有优势
2009-6-6  21:47:55  不健康不阳光不向上  NS  其他方面只能说半斤八两
2009-6-6  21:48:14  不健康不阳光不向上  NS  但是致命的地方就是内存碎片
2009-6-6  21:48:20  不健康不阳光不向上  NS  这个不能解决肯定是空想
2009-6-6  21:48:51  NS  不健康不阳光不向上  你这个东西需要长时间高性能运行？
2009-6-6  21:49:02  不健康不阳光不向上  NS  恩？
2009-6-6  21:49:12  NS  不健康不阳光不向上  如果是，你就迈上写数据库的道路了……
2009-6-6  21:49:12  不健康不阳光不向上  NS  当然想啊...
2009-6-6  21:49:33  不健康不阳光不向上  NS  数据库我看过一点点MYSQL源码
2009-6-6  21:49:39  不健康不阳光不向上  NS  查找那块的
2009-6-6  21:49:43  不健康不阳光不向上  NS  B+TREE变种
2009-6-6  21:50:01  不健康不阳光不向上  NS  其实这东西有点b+tree的意思
2009-6-6  21:50:09  不健康不阳光不向上  NS  b+tree也是分而治之嘛
2009-6-6  21:50:26  不健康不阳光不向上  NS  b+tree也是分块
2009-6-6  21:50:37  不健康不阳光不向上  NS  也是找块索引


可惜我最近没时间了，回头认真整理一下，各位大大有啥想法请各抒己见，觉得纱布也别嘴下留情尽管喷

评论

7 楼 量产型人型自走炮 2009-06-07  

假设索引等同于hash的key
按索引访问 插入 删除 hash的时间复杂度理论上是O(1)
但是实际情况是存在再hash，所以也仅仅是理论上常数时间，实际上跟对数时间不会相差太多

而hash的缺点是无序（不能保证按插入的前后有序），当然要有序也可以，只是要以性能为代价。用来实现队列，堆栈这种纯线性的数据结构就明显不如几个list了。
另外一点是，HASH需要维护key和map两个数组（且这两个数组肯定不是满的，装填因子依实现而异），
空间复杂度比较高。

tree的话应用场景太不同了..就懒得比较了

6 楼 night_stalker 2009-06-07  

对了，似乎结果还是 hash map 及其变种的 (查找 + 插入/删除) 速度最快……

5 楼 量产型人型自走炮 2009-06-07  

晚上躺床上想好的......于是清早起来更新一下，不然今天一天考试没精神...

幸存者 写道

N久前我用C#实现过一个极为类似的数据结构，就是一个节点为数组的链表，下标访问慢于ArrayList但快于链表，插入删除快于ArrayList也不比链表慢（考虑链表必须遍历）。一时找不到了，等我再找找。不过说实话，真实场景能用到这种数据结构的情况实在太少。

恩，能找到最好了，先拿过来试试性能如何。真实场景的话我认为还是有点用场的，具体的主楼已经更新，欢迎指正

4 楼 幸存者 2009-06-07  

N久前我用C#实现过一个极为类似的数据结构，就是一个节点为数组的链表，下标访问慢于ArrayList但快于链表，插入删除快于ArrayList也不比链表慢（考虑链表必须遍历）。
一时找不到了，等我再找找。
不过说实话，真实场景能用到这种数据结构的情况实在太少。

3 楼 night_stalker 2009-06-06  

我订阅了你们，就不 mark 了……
题外，话说 ArrayList 干嘛不乖乖叫 AsyncVector 呢

2 楼 量产型人型自走炮 2009-06-06  

RednaxelaFX 写道

好吧，我也想过把ArrayList串起来的LinkedList。基本上跟这段讨论开头的部分差不多？讨论的后半部分没看，回头再说……先mark下来等NS踩。小数组的一个重要好处就是locality高，容易整个放到高速cache里，于是访问效率高；访问数组元素时本身indirection次数少自然是效率高的原因之一。这些是链状数据结构再怎么也不比上的。另外，由于下标是一种默认的映射关系，它的空间效率也比链表高。不过把数组跟链混起来嘛……hmm其实要想的话还有很多的东西可以尝试混混看呢。例如把跳表的概念也混进来toka（一阵狂汗

其实灵感来源是我不久前些的弹幕播放器，因为视频跟数组其实是一样的，只是seek的矢量不同，一个是时间，一个事空间（或者说内存）

1 楼 RednaxelaFX 2009-06-06  

好吧，我也想过把ArrayList串起来的LinkedList。基本上跟这段讨论开头的部分差不多？讨论的后半部分没看，回头再说……先mark下来等NS踩。
小数组的一个重要好处就是locality高，容易整个放到高速cache里，于是访问效率高；访问数组元素时本身indirection次数少自然是效率高的原因之一。这些是链状数据结构再怎么也不比上的。另外，由于下标是一种默认的映射关系，它的空间效率也比链表高。
不过把数组跟链混起来嘛……hmm
其实要想的话还有很多的东西可以尝试混混看呢。例如把跳表的概念也混进来toka（一阵狂汗