在期望运行重复值时压缩List,同时保持索引查找

Question

精简版:

我有一个List对象,其中包含重复值运行中存在的多个重复值(double),其中散布着更改值的运行.我希望减少此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,其中包含运行计算的所有时间.每个变量都有一个List,其索引与时间List的索引相同.也就是说,如果查看时间数组的索引234,则可能会得到时间46(秒).然后,在该变量的List的索引234处找到时间46(秒)处的每个变量的计算.

大约有100,000个这样的变量(因此有100,000个列表),但只有一个时间列表.我还希望增加更多变量.这显然是一个内存问题.(目前至少约200 MB的原始空间:-)).这也应该解释为什么我想使用索引作为在特定时间找到某个变量的值的方法.

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

编辑:

请注意,我希望添加的变量比100,000更多,所以这个问题比200 MB更大.为了解释更多这方面的动机,我的应用程序目前运行在大约1 GB以上,我看到200 MB是减少内存使用率的最低成果.

EDIT2:

我意识到对我的解释进行了非常重要的编辑 - 我已经在上面进行了编辑并在此处进行了解释.列表可能已在其中运行,但它们也具有值从索引到索引更改的部分.所以我可能有一个更好的列表示例如下:

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- 例如,它可以让你ArrayPortion嵌入一​​个TreePortion.

或者稍微简单一点,你可以保持它平坦,并且List<IPortion>每个IPortion都是一个ArrayPortion或RunPortion哪个RunPortion只知道单个值及其索引边界的地方.然后,您可以在列表上执行二进制搜索以找到正确的部分,并询问它在索引处的值.