一些背景信息:我做了一个程序,它给出了一个字母数组列表,一个整数数组可以找到这个数组列表中可能存在的所有单词组合,其中单词长度是 int 数组 (wordSizes( 中的整数之一。即给定 h、o、p、n、c、i、e、t、k 以及整数 5 和 4,解决方案为:电话滴答声。
我现在的问题:输入通常约为 25 个字符,输出通常应返回 5 个单词组合。我最初将其作为dekstop的控制台应用程序,运行时通常不到1分钟。我决定将其移植到 android 上,运行时间超过 35 分钟。我是一个初学者,不确定如何在Android上运行CPU密集型任务。
public void findWordsLimited(ArrayList<Character> letters) {
for (String s1 : first2s) {
for (String s2 : possibleSeconds) {
boolean t = true;
String s1s2 = s1.concat(s2);
ArrayList<Character> tempLetters = new ArrayList<Character>(letters);
for (int i = 0; i < s1s2.length(); i++) {
if (tempLetters.contains(s1s2.charAt(i)))
tempLetters.remove(Character.valueOf(s1s2.charAt(i)));
else
t = false;
}
if (t) {
helperFindWordsL(tempLetters, s1 + " " + s2, 2);
}
}
}
}
public void helperFindWordsL(ArrayList<Character> letters, String prefix , int index) {
boolean r;
if (letters.size() <= 1) {
output += "Success : " + prefix + "n";
Log.i(TAG, prefix);
}
else if (index < wordSizes.size()){
for (String s : lastCheck) {
if (s.length() == wordSizes.get(index)) {
ArrayList<Character> templetters = new ArrayList<Character>(letters);
r = true;
for (int j = 0; j < s.length(); j++) {
if (templetters.contains(s.charAt(j)))
templetters.remove(Character.valueOf(s.charAt(j)));
else {
r = false;
templetters = new ArrayList<Character>(letters);
}
}
if (r)
helperFindWordsL(templetters, prefix + " " + s, index + 1);
}
}
}
}
我不太关心算法,因为这可能会令人困惑,因为它是解决文字游戏难题的更大项目的一部分。几个问题:
如何以最快的速度完成这样的 CPU 密集型任务?现在我从我的 MainActivity 调用方法findWordsLimited((。在我的桌面应用程序上(它说输出 += 成功...在 HelperFindWordsL 中(我会将所有解决方案打印到控制台,但现在我已经这样做了,以便该方法添加到并最终返回一个巨大的字符串(字符串输出(返回到 MainActivity,其中包含所有解决方案,并且该字符串被放入 TextView 中。这是显示数据的低效方式吗?如果是这样,你能帮忙解释一个更好的方法吗?
我应该将其作为后台/前台进程或线程运行,而不仅仅是从 MainActivity 调用它吗?
如何在我的安卓设备上获得目前比我的桌面快 20 倍的运行时?
尝试用循环代替递归,并使用数组而不是列表,以避免插入等,直接访问数组成员要快得多。主要注意使用templetters.contains(s.charAt(j))
的最内部循环,优化这部分代码将产生主要效果。
您可以在t = false;
后添加break;
String s1s2 = s1.concat(s2);
- 在这种情况下创建新的字符串对象是不好的 - 这会给 GC 带来不必要的工作。我会用 2 个周期替换它s1
然后s2
您可以使用"字母"而不是ArrayList<Character> tempLetters = new ArrayList<Character>(letters);
,只需将那里的某些项目标记为已删除。无需创建本地克隆。