Android 字典 TreeSet 更快的加载时间

Question

我的字典里有大约 300000 个单词(实际上以 txt 格式(新行分隔)保存在我的 Android 设备的 sdcard 上)。我想构建一个数据结构，它会花费尽可能少的时间从我的 txt 文件中插入单词(String-s)到这个数据结构中。而且这个 DS 必须非常快才能检查字典(这个 DS)中是否存在单词。我尝试了几种内置 DS，最快的 IMO 是 TreeSet。是否有任何其他(非内置)DS 可以更快地插入/创建 DS 并且与 TreeSet 一样用于搜索？

还有一件事是我可以通过重新排列“帮助”TreeSet 更快地插入我的 txt 文件(按正确顺序排列单词)。

问候

Answer 1

首先，在为您的应用程序找到最佳结构方面的试验做得很好。通常人们会在没有尝试各种选项来获取真实性能数据的情况下争论不休。

如果你想节省构建时间，并且你的 words 文件不会经常更改，那么明显的构建速度改进是缓存数据结构。无论您使用什么数据结构，构建一次结构，然后将结构存储到 SD 卡(而不是只存储字符串)。可以使用 Serialization 存储标准的 java.util 结构.

如果你想要最快的构建时间，并且你的单词列表按字母顺序排序，或者可以，那么你可以只存储在一个字符串数组中。构建时间将再次非常快，搜索时间将类似于 TreeSet(使用 Arrays.binarySearch() )。

如果您想要更快的查找，您可能需要查看 Perfect Hash荷兰国际集团或Trie s，但这些不在 Java 标准库中。

trie 比其中任何一个都更有效地存储内存，这可能会使其更快。 ( Information on finding an implementation )

我很惊讶 TreeSet 在您的实验中比 HashSet 更快，这意味着您可能在内存分配昂贵的情况下操作。分配HashSet的时候记得设置初始容量吗？请记住，为避免代价高昂的重新哈希，您需要将初始容量至少设置为项目数/0.75(加载因子)。