Mar*_*tin 5 arrays string algorithm data-structures
什么数据结构和/或算法有利于实现插入的字符数组.典型的工作负载是几个"随机"读取循环,然后是"随机"插入.阵列将是巨大的,大约为千兆字节.
编辑:在极端情况下,算法需要能够有效地建立一个带有单字节插入的千兆字节字符串.
由于此数据结构应允许各种极端情况(如插入长字符串或大量单个字符,表示非常长的数组,可能是内存受限),因此单个众所周知的数据结构不太可能满足所有需求.
您可以考虑这两种数据结构:
或者您可以使用基于绳索或分层矢量的定制数据结构.
如果你期望太多的小插入,并希望避免过多的绳索分裂,你可以使用数组树; 当它很短时插入到数组的中间; 但是如果数组的大小增长到某个极限,则下一个插入应该将其拆分,就像在绳索中一样.树节点引用的数组应该相当大(大约1000字节或更多),以便在访问树节点时获得非常昂贵的缓存未命中之间的更好平衡(因此我们应该最小化不适合缓存的节点数)和稍微便宜的memmoves.
这些数组的最合适的内存分配方案是这样的:当数组不适合其分配的空间时,将其拆分为2个相等的部分,为每一半分配一些固定数量的字节(如2000),然后将每一半复制到中间分配的空间.在靠近此数组末尾插入字符时,请将尾部字符移到右侧.在开头附近插入字符时,请将前面的字符向左移动.所以memmove的平均长度只是平均数组长度的1/4.两个邻居分配空间可以在它们之间共享未使用的字节,因此我们只需要在一个块的字节即将覆盖其他块的已用字节时进行分割.这种方法很简单,但需要一些额外的空间来允许阵列增长.我们可以使用一些通用分配器来获得数组实际使用的空间(或允许非常有限的增长空间),但它要慢得多,最有可能导致内存碎片甚至更大量的未使用内存.保存一些内存的可能更好的方法是使用几个固定的分配空间(如1500,1700,2000)并保留每个大小的块的固定数量(通过实验确定).保存内存的其他方法是(而不是将一个2000字节的数组拆分成两个1000字节的数组)合并两个相邻的数组(如2000 + 1600),然后将结果拆分为三个数组(1200 + 1200 + 1200).
您已经提到"将位打包在一起"以减少RAM使用率.对于这样的数据结构(如果您的数据是可压缩的),这并非不可能.实际上,这里可以使用两种压缩算法而不牺牲太多性能:霍夫曼编码或LZ4.对于霍夫曼编码,您需要一个静态频率表(事先预先计算).对于读取,您只需要解码大约平均数组大小的1/4,然后转到正确的位置加上要读取的字符串的长度.对于插入,您需要解码相同1/4的平均数组大小,然后移动相同大小的比特流,然后对插入的字符串进行编码.使用LZ4,不需要处理比特流,只使用整个字节; 可能值得增加数组的大小以获得更好的压缩.
可以优化分层向量以使缓存更友好.为每个块添加大约100-200字节的保留空间.每次插入memmove字节到这个空间.并且只有在下一个memmove没有空间之后,才开始在块之间交换数据(不是像原始数据结构中的单个字节,而是一次100-200个字节).
为了提高O(sqrt(n))插入时间,可以将分层向量视为trie的特例,只有2个级别.我们可以添加一个级别.然后(插入后)我们可以在第二级块结束时停止块间数据交换,分配额外的第一级块,并在那里放置额外的字节.当一个或多个附加块被填满时,我们可以继续在第三级块(trie的根)上进行数据交换.从理论上讲,这可以扩展到log(n)级别,以保证O(log(n))单字符插入和读取.但实际上,3或4级可能是更好的选择,因此我们有O(n 1/3)或O(n 1/4)分摊插入复杂度.