在Haskell中高效地处理稀疏缺失数据

Question

我尝试使用Haskell进行数据分析。因为我的数据集相当大（数十万到可能是数百万个观测值），所以我最好使用未装箱的数据结构以提高效率，比如Data.Vector.Unboxed。

问题在于数据中包含一些缺失值。我希望避免将它们编码为“99”或类似的数字，因为那只是一种丑陋的hack和潜在的错误来源。从我的Haskell新手角度来看，我能想到以下选项：

1. 一个装箱向量，其中包含未打包的Maybe值。类似于（如果不正确请纠正）：
   data myMaybe a = Nothing | Just {-# UNPACK #-} !a
2. 一个（可打包）元组的未装箱向量，其中包含表示缺失值的布尔元素：
   newtype instance Data.Vector.Unboxed.Vector (MyDatum a) = MyDatum (Data.Vector.Unboxed.Vector (Bool,a))
   这可能是这个问题提问者选择的相同方法（用Int替换Bool），但唯一的答案似乎没有明确解决缺失值/稀疏性问题（而是关注如何将整个数组解包，而不是作为装箱向量的未装箱向量）。
3. 一个元组的未装箱向量，其中一个向量包含值，另一个向量包含要插入缺失值的索引，或非缺失值的运行长度，或一些等效信息。如果缺失值很稀疏，则可能比选项2更可取？

我试图保持在向量表示内，而不是像这样，因为是缺失值是稀疏的，而不是数据。

欢迎对这些选项的相对优点/可行性/现成可用性/可能表现提出任何评论，或者提供完全不同的替代方案的指针！

编辑：

• 有人指出答案可能取决于我打算在数据上执行什么样的操作。目前，将每个观察结果存储在单个向量中似乎更为方便，而不是每个变量。由于向量中的条目将因此引用不同的变量，因此“折叠”类操作不太可能。
• 我猜测2.会根据需要自动存储类似于3.的“有效位”向量，因此可以删除3.？

- Bilal Barakat

---

你想要存储“有效”位的方式取决于你将如何处理数据。例如，如果你将在数据上映射某些函数，你可以保持位分离，因为即使在映射之后它们也是正确的。但是，如果你将对数据进行折叠等操作，将位与数据项一起保留更方便。 - augustss

Answer 1

我会选择选项3，但是你不应该使用向量来存储缺失的索引：这会使你的查找时间达到 O(nMissing)，除非缺失的数据是极其稀疏的，否则这样会非常慢。你可以使用Data.IntMap来解决这个问题，然后可以轻松地使用member函数来检查一个索引是否指向缺失的观察值。哈希表甚至更好，但可能不是必要的。

- leftaroundabout

---

如果缺失索引的向量已排序，则二分查找也可以为其提供O(log nMissing)。 - Daniel Fischer

@DanielFischer：没错，但是**a)实际上保持数组排序很麻烦，而且b)**与Data.Map相比，Data.IntMap通常搜索速度更快，不是吗？（我不确定，证明我错了） - leftaroundabout

关于 a)：你只需要找到要插入或删除的位置并移动后面的项目。这只是慢（除非缺少的项目非常少），而不是“麻烦的”。 关于 b)：IntMap查找通常也需要O（log size）比较（因为size <= 2 ^ WORD_SIZE_IN_BITS），因此哪个具有更快的查找取决于常数因子，我可以轻松地相信任何一个都会获胜。然而，由于IntMap具有更好的插入/删除行为和更合适的API，我也建议使用它（直到经验证明不足为止）。 - Daniel Fischer

谢谢，这些是很好的观点。但是你认为为什么你提到的任何一种策略会比Data.Vector.Unboxed选择的“专业表示”更有效呢？我很乐意被说服手动微调会表现得更好，只是想理解为什么。 - Bilal Barakat

@BilalBarakat：问题在于，Data.Vector的elem函数，你可能会用它来确定索引是否丢失，但它的复杂度为O(n)，因为它不能假设数组已排序。所以你要么需要确保它已排序并实现自己的例如elemInSorted函数，要么使用一些关联容器（如Data.IntMap，仍然是我的建议），或者使用完全不同的表示方法。 - leftaroundabout