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

本文关键字：索引查找 List 压缩 期望 运行时 | 更新日期: 2023-09-27 18:05:40

简体版:

我有一个List对象，它包含许多重复值(双精度)，这些重复值存在于重复值的运行中，穿插着变化值的运行。我想减少这个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，其索引与times List的索引相同。也就是说，如果查看时间数组的索引234，可能会得到时间46(秒)。每个变量在时间46(秒)时的计算结果将在该变量的List索引234处找到。

大约有100,000个这样的变量(因此有100,000个List)，但只有一个time List。我还希望添加更多的变量。这显然有点内存问题。(目前至少有200 MB的原始空间:-))。这也解释了为什么我要使用索引作为在特定时间查找特定变量值的方法。

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

编辑:

请注意，我希望添加比100,000个变量更多的变量，所以这是一个比200mb更大的问题。为了解释更多的动机，我的应用程序目前运行在1+ GB左右，我认为200mb是减少内存使用的容易实现的目标。

EDIT2:

我意识到我的解释有一个非常重要的编辑-我在上面编辑了它，并在这里解释了它。列表可能在其中运行，但它们也有一些部分，其中的值随着索引的变化而变化。下面是一个更好的列表示例:

0 0 0 0 0 0 0 ....(50个重复的0)…0.1 0.2 0.4 0.5 0.6…(50多个变化的值)………(50多个重复值)....等。

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

我假设你的O(log(m))想法基本上是创建一个二叉搜索树，使用索引范围对结果进行排序。

我绝对同意那个解决方案。如果每个列表最多只能运行30次，那么你真的不需要担心m的扩展方式，因为m从来都不是特别大……你可能会发现，在任何实际情况下，任何常数时间解决方案实际上都比你的搜索树方法更糟糕。

事实上，我可能会最初选择一个简单的运行列表(其中每次运行是一个索引范围和一个值)和O(m)查找…如果您的典型的大小是2-5，那么它不会特别糟糕，并且它将更容易实现。一旦你有了一个简单的方法，然后你可以优化。

事实上，我一开始甚至不做这个"运行"版本。除非您需要在特别有限的移动电话上运行此程序，否则200MB左右的数据集并不算太大。应用程序实际将在哪些机器上运行?您是否有理由相信他们负担不起，比如说，您的应用程序的0.5 gb内存?

同样值得记住的是，二叉搜索树或运行列表的开销很可能意味着您无论如何都不会节省您期望的那么多。

基本上，我将按照这个顺序实现:

    数组
  • 运行列表
  • 二叉搜索树

对每一步的表现(时间和空间)进行基准测试，并确保你有关于什么足够好的具体目标。

编辑:在编辑过的版本中，您可能希望有某种接口IPortion:

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

有两个实现:ArrayPortion和TreePortion。TreePortion的每个节点将有一个左侧和一个右侧，每个都是另一个IPortion -这可以让你在TreePortion中嵌入ArrayPortion，例如。

或者更简单一点，你可以保持它的平直，并且有一个List<IPortion>，其中每个IPortion要么是ArrayPortion，要么是RunPortion，其中RunPortion只知道一个值和它的索引界。然后，您可以对列表进行二分搜索以找到正确的部分，并向它询问索引处的值。

在我看来，你可以用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的两倍大。

相关文章：