2

我有一个 Android 应用程序，它遍历一个包含数千个整数的数组，并将它们用作键值来访问整数对（让我们称它们为 id），以便用它们进行计算。它需要尽可能快地完成，并最终返回对应用程序至关重要的结果。

我尝试将 HashMap 加载到内存中以快速访问这些数字，但它导致 OOM 异常。我还尝试将这些 id 写入 RandomAccessFile 并将它们在文件上的偏移量存储到另一个 HashMap 但它太慢了。另外，只存储偏移量的新 HashMap 仍然占用很大的内存。

现在我正在考虑使用 SQLite，但我不确定它是否会更快。有没有可以帮助我的结构或库？

编辑：密钥数量超过 2000 万，而我只需要访问数千个。我不知道我会事先访问哪些，因为它会随着用户输入而变化。

4

3 回答 3

4

您可以使用 TroveTIntLongHashMap将原始 s 映射int到原始longs（存储int值对的 s）。这为您节省了普通 vanilla 的对象开销Map，这迫使您使用包装器类型。

编辑

由于您的更新表明您有超过 2000 万个映射，因此可能会有比散列映射更节省空间的结构。一种将您的密钥划分为桶的方法，结合一些子密钥压缩，即使是最有效的哈希映射实现，也可能会为您节省一半的内存。

于 2012-05-15T21:11:47.823 回答
1

SQLite 是一个嵌入式关系数据库，它使用索引。我敢打赌它比使用 RandomAccessFile 快得多。你可以试一试。

于 2012-05-15T21:24:26.813 回答
1

我的建议是重新排列 Buckets 中的键 - 我的意思是确定（或多或少）你的键的分布，然后制作对应于每个键范围的文件（关键是每个文件必须包含与可以进入内存，仅此而已）然后当您搜索密钥时，您只需将整个文件读入内存并查找它。

例如，假设key的分布是均匀的，存储0-500k键值对应的500k值，500k-1mil键对应的500k值等等......

编辑：如果你确实尝试了这种方法，但它仍然很慢，我仍然有一些技巧：

  1. 首先确保所有桶之间的划分实际上接近相等。
  2. 尝试通过制作更多的桶来使桶更小。
  3. 关于按范围正确划分存储桶的想法是，当您搜索一个键时，您会转到相应的范围存储桶，并且该键要么在其中，要么不在整个集合中。所以 Concurnetly 读取另一个存储桶没有意义。
  4. 我从来没有这样做过，因为我不确定并发在 I\O 上是否有效，但是用 2 个线程读取整个文件可能会有所帮助，一个从上到下，另一个从下到上，直到它们相遇。（或类似的东西）
  5. 当您将整个存储桶读入内存时，将其拆分为 3-4 个数组列表，运行 3-4 个工作线程以在每个数组上搜索您的密钥，然后搜索必须以更快的速度结束。
于 2012-05-15T21:31:39.437 回答