gpt4 book ai didi

Java Anagram 内存不足

转载 作者:行者123 更新时间:2023-11-29 10:10:07 25 4
gpt4 key购买 nike

我正在尝试解决古老的字谜问题。感谢那里的许多教程,我能够遍历一组字符串,递归地找到所有排列,然后将它们与英语单词列表进行比较。我发现的问题是,在大约三个词之后(通常是“变形”之类的词),我得到了 OutOfMemory 错误。我尝试将我的批处理分成小集合,因为它似乎是消耗我所有内存的递归部分。但即使只是“变形”也会将其锁定...

这里我从一个文件中读取单词到一个列表中

Scanner scanner = new Scanner(resource.getInputStream());
while (scanner.hasNext()) {
String s = scanner.nextLine();
uniqueWords.add(s.toLowerCase());
}

现在我将它们分解成更小的集合并调用一个类来生成字谜:

List<List<String>> subSets = Lists.partition(new ArrayList(uniqueWords), SET_SIZE);

for (List<String> set: subSets) {
// tried created as class attribute & injection, no difference
AnagramGenerator anagramGenerator = new AnagramGenerator();
List<Word> anagrams = anagramGenerator.createWordList(set);
wordsRepository.save(anagrams);
LOGGER.info("Inserted {} records into the database", anagrams.size());
}

最后是我的发电机:

public class AnagramGenerator {

private Map<String, List<String>> map = new Hashtable<>();
public List<Word> createWordList(List<String> dictionary) {

buildAnagrams(dictionary);

List<Word> words = new ArrayList<>();
for (Map.Entry<String, List<String>> entry : map.entrySet()) {
words.add(new Word(entry.getKey(), entry.getValue()));
}
return words;
}

private Map<String, List<String>> buildAnagrams(List<String> dictionary) {

for (String str : dictionary) {
String key = sortString(str);
if (map.get(key) != null) {
map.get(key).add(str.toLowerCase());
} else {
if (str.length() < 2) {
map.put(key, new ArrayList<>());
} else {
Set<String> permutations = permutations(str);
Set<String> anagramList = new HashSet<>();

for (String temp : permutations) {
if (dictionary.contains(temp) && !temp.equalsIgnoreCase(str)) {
anagramList.add(temp);
}
}
map.put(key, new ArrayList<>(anagramList));
}
}
}
return map;
}

private Set<String> permutations(String str) {
if (str.isEmpty()) {
return Collections.singleton(str);
} else {
Set<String> set = new HashSet<>();
for (int i = 0; i < str.length(); i++)
for (String s : permutations(str.substring(0, i) + str.substring(i + 1)))
set.add(str.charAt(i) + s);
return set;
}
}

编辑:基于出色的反馈,我将生成器从排列更改为工作查找:

public class AnagramGenerator {
private Map<String, Set<String>> groupedByAnagram = new HashMap<String, Set<String>>();

private Set<String> dictionary;

public AnagramGenerator(Set<String> dictionary) {

this.dictionary = dictionary;
}

public List<Word> searchAlphabetically() {

List<Word> words = new ArrayList<>();
for (String word : dictionary) {
String key = sortString(word);
if (!groupedByAnagram.containsKey(key)) {
groupedByAnagram.put(key, new HashSet<>());
}
if (!word.equalsIgnoreCase(key)) {
groupedByAnagram.get(key).add(word);
}
}

for (Map.Entry<String, Set<String>> entry : groupedByAnagram.entrySet()) {
words.add(new Word(entry.getKey(), new ArrayList(entry.getValue())));
}

return words;
}
private String sortString(String goodString) {

char[] letters = goodString.toLowerCase().toCharArray();
Arrays.sort(letters);
return new String(letters);
}

它有更多的调整,所以我没有添加一个词,因为它是自己的变位词,但除此之外,它看起来非常快。而且,代码更简洁。谢谢大家!

最佳答案

对于较长的单词,排列的数量很快就会变得巨大。

/usr/share/dict/british-english Debian 上有 99,156 行。单词列表更长,但让我们以此为例。

九个字母的单词的排列数是 9! = 362,880

因此,对于 9 个或更多字母的单词,与尝试输入单词的每个排列相比,尝试字典中的每个单词所需的计算量更少。

10! milliseconds = ~1 hour
12! milliseconds = ~5.54 days
15! milliseconds = ~41.44 years

而且您很幸运能够每毫秒处理一个排列,因此您很快就会发现许多排列是完全不切实际的。对堆栈和堆的影响以相同的速度增加。

所以,试试算法(伪代码):

 sorted_input = sort_alphabetically(input_word)
for each dictionary_word // probably a file readline()
sorted_dictionary_word = sort_alphabetically(dictionary_word)
if(sorted_dictionary_word = sorted_input)
it's an anagram! Handle it
end
end

同样,您可以相当快速地将所有字典词算法写入查找数据结构。再次伪代码;在 Java 中你可以使用 Map<String, List<String>>MultiMap来自 Apache Commons 或 Guava:

  multimap = new MultiMap<String, String> // or whatever

def build_dict:
for each dictionary_word // probably a file readline()
multimap.add(
sort_alphabetically(dictionary_word),
dictionary_word)
end
end

def lookup_anagrams(word):
return multimap.get(sort_alphabetically(word))
end

这会占用适量的内存(整个字典,加上一些键和映射开销),但这意味着一旦创建了结构,您就可以非常便宜地一遍又一遍地查询。

如果你想找到两个单词的字谜,你将需要一个更复杂和有趣的算法。但即便如此,避免暴力破解整个排列的搜索空间对您的成功至关重要。

关于Java Anagram 内存不足,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42514068/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com