期待重复值运行时压缩列表，同时保持索引查找

Question

短版：

我有一个包含一些重复值（双的）中存在的与奔跑穿插重复值的运行列表对象改变价值。我想减少这个List对象占用的内存空间，而不损害索引和值之间的关联。我也想尽可能地保持O（1）算法查找时间，使用索引作为查找。例如，如果您有一个包含元素{0,0.1,0.1,0.1,0.2}的列表，那么如果给定索引1,2或3，则新对象/实体将始终返回0.1。我希望我需要创建我自己的对象（也许实现IList），或者使用现有的对象。我有一个关于如何实现这个算法O（log（m））的想法，其中，m是相同值的运行次数（在我的例子中，只有1次运行）。但是，如果可能的话，我宁愿不推出自己的产品。

这样的对象是否存在用于C＃，还是我需要滚动自己的？

动机/长版：

我有一个是做一些繁重的科学计算的桌面应用程序。这些计算会生成大量数据，并且这些数据是基于时间组织的。也就是说，对于时间50，存在变量x，y和z的值。对于时间51，存在变量x，y和z的另一个值。我有一个包含所有计算运行时间的列表。每个变量都有一个List，其索引与时间列表的索引相同。也就是说，如果您查看时间数组的索引234，则可能会得到时间46（秒）。然后，在时间46（秒）的每个变量的计算将在该变量的列表的索引234处找到。

大约有100,000个这样的变量（因此有100,000个列表），但只有一次列表。我也期望增加更多的变量。这显然是一个记忆问题。 （目前至少有200 MB左右的原始空间:-)）。这也应该解释为什么我想使用索引作为在特定时间查找某个变量的值的方法。

变量在前x个插槽中只有0的情况是相当典型的。或者在索引y之后，变量保持不变直到结束。我想说的是，对于值恒定的期间数的最坏情况，可能在单个列表中约为30，但更通常在2和5之间。每个阵列中的总值的数量通常可以是约250.

编辑：

请注意，我期望添加更多的变量比100,000，所以这是比只有200 MB更大的问题。为了解释更多的动机，我的应用程序目前运行在大约1 GB以上，并且我看到200 MB作为降低内存使用率的低成本成果。

EDIT2：

我认识到一个非常重要的编辑对我explanation-我上面editted它和这里解释。这些列表可能会在其中运行，但它们也具有值从索引变为索引的部分。因此，我可能列出的一个更好的示例是：

0 0 0 0 0 0 ....（50个重复的0）... 0.1 0.2 0.4 0.5 0.6 ...（50个更改的值） ... 200.45 200.45 200.45 200.55 ...（50更多重复值）....等

Answer 1

我假设你的O（log（m））的想法是基本上创建一个二叉搜索树，使用索引范围来订购结果。

我绝对会用这个解决方案。如果每个列表只能运行约30次，那么您确实不需要担心它与m的比例关系，因为m永远不会特别大......您可能会发现任何恒定时间解决方案实际上都更糟糕在任何真实世界的情况下比你的搜索树方法。

事实上，我可能会最初去运行一个简单的列表（其中每个运行的索引范围和值）和O（M）查找...如果你典型大小2-5，那么它不会特别糟糕，而且实现起来会更简单。一旦你有一个简单的方法工作，然后你可以优化。

事实上，我从一开始就没有做这个“运行”版本。除非你需要在特别有限的手机上运行这个功能，否则200MB左右的数据并不算太大。应用程序将在哪些机器上运行？你有没有理由相信他们买不起半个千兆字节的应用程序？

同样值得注意的是，二叉搜索树的开销或运行列表可能意味着您不会像预期的那样保存多少。

基本上，我会在这个顺序实施：奔跑

• 阵列
• 列表
• 二叉搜索树

基准在每一步的性能（时间和空间） ，并确保你有足够好的具体目标。

编辑：随着编辑的版本，你可能希望有某种接口IPortion的搭配：

int MinIndexInclusive { get; } 
int MaxIndexExclusive { get; } 
double FindValue(int index); 

有两种实现方式：ArrayPortion和TreePortion。例如，TreePortion的每个节点都有左侧和右侧，每个节点都是另一个IPortion--例如，可以让嵌入在TreePortion内。

还是有些简单，你可以只保持平坦，并有List<IPortion>每个IPortion要么是一个ArrayPortion或RunPortion其中RunPortion只知道一个单一的价值和它的指数范围。然后，您可以在列表上进行二进制搜索以找到正确的部分，然后询问索引处的值。

Answer 2

对我来说，你可以用List<T>和二分查找来做到这一点。您不需要存储运行列表。你真正需要存储的是时间变化时的索引和值。

所以，有一个简单的结构：

struct ValueChange 
{ 
    public int TimeIndex; // or whatever type you use for the index 
    public double Value; 
    // Add constructor here 
} 

（是的，我知道，在结构可变值是坏我编写这种方式为简洁起见在实际的代码，这些将与私人只读属性。支持领域。）

然后你有一个List<ValueChange>。只要值发生变化，您就会将其中的一个附加到列表中。你可以告诉当值改变很轻松地：

if (currentValue != theList[theList.Count-1].Value) 
{ 
    theList.Add(new ValueChange(timeIndex, currentValue)); 
} 

而当你想要查找的值在特定时间的索引，你做的时间索引二进制搜索。如果您查找的索引不存在，List.BinarySearch的返回值将告诉您包含您要查找的值的项目的索引。

任何种类的游程压缩的缺点当然是短程运行将其变成数据扩展器而不是压缩器。在这个特殊情况下，为了达到平衡，你需要一个总体平均数为2的平均数。也就是说，如果要表示N个时间段的值，则不能有超过N/2个值的更改，因为ValueChange结构的大小是您的double的两倍。