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 回答