1

精简版：

我有一个 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，其索引与时间 List 的索引相同。也就是说，如果您查看时间数组的索引 234，您可能会得到时间 46（秒）。然后将在该变量的列表的索引 234 处找到每个变量在时间 46（秒）的计算。

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

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

编辑：

请注意，我希望添加比 100,000 更多的变量，所以这是比 200 MB 更大的问题。为了解释这样做的更多动机，我的应用程序目前以大约 1+ GB 的速度运行，我认为 200 MB 是减少内存使用量的唾手可得的成果。

编辑2：

我意识到对我的解释进行了非常重要的编辑-我在上面进行了编辑并在此处进行了解释。列表可能在其中运行，但它们也有值从索引更改为索引的部分。因此，我可能拥有的一个更好的列表示例如下：

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 个重复值）.. .. ETC。

4

2 回答 2

5

我假设您的 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- 例如，这可以让您在 a 中ArrayPortion嵌入一个TreePortion。

或者更简单一些，你可以保持它平坦，并且有一个List<IPortion>where eachIPortion要么是 anArrayPortion要么 a RunPortionwhere the RunPortiononly know about a single value and its index bounds。然后，您可以对列表进行二分搜索以找到正确的部分，并在索引处询问它的值。

于 2013-03-25T19:35:11.427 回答
1

在我看来，你可以用一个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.

于 2013-03-25T20:28:50.403 回答