咱研究出新的类阵列资料结构的说

嗨咪纳桑，咱是immortalmice，今天要来和各位分享自己研究出的几个新资料结构

这个资料结构支援以下五个操作

1. Random Get (随机存取)
2. Push (尾端插入)
3. Pop (尾端移除)
4. Unshift (首端插入)
5. Shift (首端移除)

乍看之下，好像就是一个支援随机存取的双端伫列
用阵列手刻一个实作出来一点也不难，那我的资料结构究竟是为了什麽而诞生呢
而这就要提到各位修资料结构的课时都被教过的效能问题

• 动态阵列(DynamicArray)在随机存取表现优秀，但SHIFT & UNSHIFT表现差
• 双向连结串列(DoublyLinkedList)在双端插入移除表现优异，但随机存取表现差

因此，本研究在寻找一个可以融合两者优点的类阵列资料结构

首先，来些东西镇楼
这是本研究的Repo，里面包含了Javascript和Java的语言实作以及效能测试报告
(贴心提醒所有的README都有中文喔 >.0)
至於测试报告，举例来说这是Java语言实作的AdaptiveArray的测试报告，其他的可以在README中找到
从图表中可以看到，不管在哪种操作的组合测试中，我的资料结构虽然不是永远的第一名，但他绝不会是最後一名
这证明了我的研究成功地融合了动态阵列和双向连结串列的优点 而不是融合缺点

至於为何可以做到这样，这边我归类出三个最重要的研究方向

1. 让此资料结构同时拥有动态阵列和双向连结串列的特徵，试图获得两个资料结构的优势
2. 用Push操作取代Unshift，避免因插入而移动阵列内既有的元素，并用一个可以为负的index为元素纪录顺序关系
3. 用一个特殊的Refactor机制整理元素，让被整理好的元素在被随机存取时可以更快被找到，同时也加快寻找未被整理元素的动作

在研究过程中，生出了三个资料结构

• LinkArray是最初的一位，包含了上面的三个研究方向，成功的获得了两个资料结构的优势
• AutoLinkArray，在LinkArray中，refactor是影响效能很重要的一个动作，但基於懒人思想，此资料结构会基於策略在自认适合的情况下自动执行refactor的动作，免去了手动执行的功夫
• AdaptiveArray，在测试AutoLinkArray的报告中发现它在阵列内容物少时不具有优势，因此最後的这个资料结构以动态阵列作为初始实作，当阵列长度大於一定程度时自动转换为AutoLinkArray的实作

至於更详细的实作细节，可以观看Repo的README或已经实作出来的两个语言的程序码，这边不再重复一次

最後，关於Contribution
这是一个开源的专案，希望可以获得大大您的帮助

1. 对於本资料结构的意见
   虽然已经查过很多次都没发现有人在做一样的事
   但如果你知道远在天边的另一个研究有在做类似的事情，请不吝告诉我，让我了解
   或是你有改进本资料结构的意见也欢迎提出
2. 新的语言的实作
   除了Java和Javascript之外，本Repo欢迎提供其他的语言实作，请发PR给我，也欢迎透过站内简讯和我讨论
3. 实作的benchmarking程序码和效能测试报告
   现在的Java和Javascript效能测试是由我手工撰写，但本人也不是这方面的专长
   更何况实作和测试都由我写可能有些裁判兼球员的味道在，因此也欢迎新的benchmarking程序码和效能测试报告
   可以发PR给我，也欢迎透过站内简讯和我讨论

最後谢谢看到这里的你，本鼠下台一鞠躬