问题
[下面是应用程序在哪些约束下应该做什么的描述]
我想要一个数据结构来搜索 string
存在于一个250000字的列表中,同时只使用相当数量的ram,并保持将此数据结构加载到ram所需的时间很短(比如0-8秒)。查找单词所需的时间也应该很快(比如0到0.5秒),但是ram的使用更为重要。它还可以创建多个游戏(更多关于这个游戏的标题是“使用”),而不需要大量的内存。
知道哪些单词以字母开头也是很有价值的 string
,但这还不足以以秒为单位牺牲加载时间。
使用
这是一款android离线游戏。有限的ram可用。根据这篇文章,应用程序可以使用的最大ram量是16-32mbram,具体取决于设备。我的空android应用程序已经使用了大约17mb(在androidstudio中使用内存监视器)。我的android设备将ram的使用限制在26mb,这样我整个系统就有8mb的可用空间 Activity
.
我试过的选择
它们似乎都以不同的方式注定了命运。
哈希Map-将所有单词读入哈希Map对象。
1.1初始化速度:以23秒的速度将每个单词读入哈希图。
1.2内存使用:使用大量的内存,尽管我忘记了具体使用了多少。
1.3搜索速度:当然,快速查找列表中是否存在单词。
1.4缩小可能的单词范围(可选):速度慢,需要遍历整个哈希图并逐个删除。另外,因为它使用的是删除,所以不能使用同一个哈希Map示例玩多个游戏。当添加更多的游戏时,会占用太多的内存,从而无法缩小可能的单词范围。
trie-实现一个radixtree&您可以在这里看到我的实现。
2.1初始化速度:以47秒的速度将每个单词读入radixtree。
2.2内存使用:使用大量的内存,以至于android会暂停线程几次。
2.3搜索速度:快速查找列表中是否存在单词。
2.4缩小可能单词的范围(可选):非常快,因为只需要引用树中的一个节点,就可以找到所有可能单词作为其子级。你可以玩很多游戏来缩小可能的单词范围,因为一个额外的游戏只需要引用树中的一个节点!
扫描器-按顺序浏览word文件
3.1初始化速度:无。
3.2 ram用途:无。
3.3搜索速度:约20秒。
3.4缩小可能的词语范围(可选):不现实。
简单代码:
String word;
String wordToFind = "example";
boolean foundWord = false;
while (wordFile.hasNextLine()) {
word = wordFile.nextLine();
if(word.equals(wordToFind)) {
foundWord = true;
break;
}
}
test.close();
我想到的选择:
长二叉搜索树:将单词列表转换为 long
然后读入这些,对它们进行二进制搜索。
1.1初始化速度:可能与哈希Map相同,或稍短,大约20秒。不过,我希望调用array.sort()不会花费太多时间,目前还不清楚。
1.2 ram用法:如果您只考虑12个字母或以下的单词和26个字母的字母表,则需要5位(2^5=32)来编码字符串。一个long数组需要250000*8位=大约2mb。这不算太多。
1.3搜索速度:arrays.binarysearch()
1.4缩小可能单词的范围(可选):缩小可能单词的范围是可能的,但我不确定如何缩小。根据这篇帖子的评论。
hashmap with storage-创建一个hashfunction,将单词Map到单词列表文件的索引号。然后在这个特定的位置访问文件并从这里查看是否有单词存在。您可以利用字母表的顺序来确定是否仍然可以找到单词,因为单词列表是按自然顺序排列的。
2.1初始化速度:不需要(因为我需要事先把每个单词都放到正确的索引中。)
2.2 ram用途:无。
2.3搜索速度:快。
2.4缩小可能的词语范围(可选):不可能。
我有一些具体的问题
我在“我想到的选项”一节中想到的选项是可行的还是我错过了一些使它们无法实现的东西?
有没有我没有想到的性能更好/相等的选项?
结束语
我已经被困在这大约一个星期了。所以任何新的想法都是非常受欢迎的。如果我以上的任何假设是不正确的,我也很高兴听到他们。
我这样写这篇文章是为了让其他人也能从中吸取教训,要么看看我的错误,要么看看答案中的有用之处。
2条答案
按热度按时间f0brbegy1#
这听起来像是布卢姆过滤器的理想用途。如果你愿意冒着被错误地认为是单词的风险,你可以把你的单词表压缩成一个尽可能小或尽可能大的内存量。
bis0qfac2#
我也遇到了同样的问题,最后我选择了“磁盘上”的trie。也就是说,我使用字节偏移量(而不是指针)将数据结构编码到单个文件中(按相反顺序打包节点,最后写入的是“根”节点)。
只需将文件读入字节数组即可快速加载,trie遍历使用偏移值的方式与指针相同。
我的200k字集适合1.7MB(未压缩),每个字终止节点有一个4字节的值。