java - 稀疏 vector ，它们是什么？

Question

我在朴素贝叶斯分类器中使用 Mahout API。其中一个功能是 SparseVectorsFromSequenceFiles虽然我已经尝试过旧的谷歌搜索，但我仍然不明白什么是稀疏 vector 。最接近我的解释是这个 site这并没有帮助我理解它。

Answer 1

从概念上讲， vector 代表数组的泛化，即允许使用索引任意访问其元素的数据结构。 Java 的内置数组，Vector<T>和 ArrayList<T>是实现“常规”(密集) vector 概念的数据结构示例。

密集 vector 通过使用一个简单的公式将 vector 索引转换为内存地址来提供对其元素的恒定时间访问 baseAddress + index * elementSize .这意味着内存中的大小与 vector 需要支持的最大索引成正比。

虽然在您希望放入 vector 中的元素数量和可能的最高索引彼此相对接近的情况下，这是可以接受的。但是，如果您希望使用大范围的索引来索引相对较少的元素(例如，1,000 个元素散布在具有 100,000 个索引的 vector 中)，则分配 100,000 个空间是一种浪费。您可以通过实现公开 vector 接口(interface)但使用较少内存量用于其内部表示的数据结构来节省内存，但会占用 CPU 周期。

您链接中的示例显示了一种可能的实现方式。其他实现也是可能的，具体取决于数据中索引的分布。如果索引是随机分布的，您可以使用 HashMap<Integer,T>作为稀疏 vector 的后备存储。如果索引聚集在一起，您可以按“页面”拆分索引空间，并仅将实际数组分配给您需要的页面。这种实现类似于将物理内存分配给虚拟内存空间的方式。