期待重複值運行時壓縮列表，同時保持索引查找

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的兩倍。