2

在我的项目中，我试图从包含字符串令牌的资产文件夹中加载一个 600KB 的文件。

我需要这些令牌在 o(1) 或任何恒定时间可用/搜索/包含。

我开始HashSet- 但它把字符串数据炸到 10MB - 导致内存不足问题

然后，切换到ArrayList- 但这也吹到了 6MB。

我尝试使用 original String，但是当我构建它时StringBuffer- 方法的固有问题append进来 - 导致内存不足问题。

所以，我主要关心的仍然是这些数据：

  • 它最初是 600KB - 所以集合应该保持在 1 或 2MB 以内
  • 查找最好在 O(1) 内

是否有任何好的 Java 集合（甚至来自任何其他库）可以帮助我？

4

2 回答 2

0

在 1 到 2Mb 的内存中表示这些令牌并支持O(1)查找将非常困难。没有任何标准集合类型能够为您做到这一点，而且我不知道有任何第三方 Java 库可以做到这一点。（S-Space项目有一个TrieSet实现，但我查看了代码，我很确定它不会满足您的空间或性能要求......）

假设字符串中的字符是 ASCII，那么将它们转换为 String 对象会立即使大小翻倍（byte-> char），然后您需要为每个字符串添加 32 个字节的开销。然后，如果将字符串放入 aHashSet中，则集合中的每个条目大约需要 32 个额外的字节。

每个条目的ArrayList<String>开销为 4 个字节，但现在查找是O(N)……或者O(logN)如果您保持列表有序并使用二进制搜索。无论哪种方式，您仍然超出您的内存预算。

为了不超出您的预算，您将不得不使用针对内存使用进行了优化的自定义哈希表数据结构，并将您的字符数据作为单个字节数组保存在内存中。

这是一个假设的实现。

  1. 分配一个int[]作为哈希数组。大小应该是大约是令牌数量的一半到五分之一的素数。
  2. 分配一个byte[]足够大的空间来保存令牌文件。
  3. 对于哈希数组中的每个槽：
    • 逐字节扫描文件以查找其哈希码映射到插槽的所有令牌，
    • 将每个标记复制到字节数组并在其后跟一个终止符字节，
    • 如果您找到任何标记，请将第一个标记开头的字节数组偏移量写入哈希数组槽......否则将其设置为-1.
  4. 要进行查找：
    • 将测试字符串转换为字节，
    • 散列测试字符串的字节（使用与上面相同的散列算法），并将其映射到散列槽，
    • 从哈希槽中的偏移量开始，将测试字符串的字节与byte[]. 重复直到你得到一个匹配，或者你到达下一个哈希数组元素中的偏移量。

如您所见，填充过程byte[]涉及多次扫描输入文件。然而，这可以事先完成，然后可以更新输入文件以包含所需顺序的字节。

空间使用量将是每个字符串数据字节一个字节 + 每个字符串 1 个字节开销 + 主哈希数组中每个插槽的 4 个字节（+ 各种O(1)开销）。查找是O(1)平均的，但常数取决于散列数组的大小。（越大越好。）

上述设计的主要缺点是：

  • 创建数据结构是昂贵的
  • 数据结构不能以空间或时间有效的方式更新
  • 如果迭代集合，则必须创建一堆 String 对象来表示条目......或公开字节数组和偏移量。
于 2012-12-02T15:18:12.187 回答
0

这是一个有趣的问题！我通常使用 util 包中的 HashMap 类进行存储，例如这样。您的问题可能不容易适应 android 设备的内存空间，所以我会建议一个替代方案。

对于存储，Android 设备通常使用固态硬盘，例如通常相当快的 SD 卡，那么为什么不将磁盘上的大部分数据保留在 assets 文件夹中，直到需要时呢？您可以构造一个类来缓存最常用的结果，并且修改数据也应该是合理的。如果这不适合，也许您可​​以使用 android SDK 中可用的数据管理工具，例如 sqlite，这将为您完成一些艰苦的工作。

如果您可以避免使用通常是更好的选择的字符串。字符串的操作可能非常昂贵。如果您使用其他数据类型（甚至是 char 或 byte 数组），您可能会发现代码更复杂但在内存方面更有效。

于 2012-12-03T04:19:14.000 回答