所以我目前正在制作一个游戏,其中的指令是使用存储在标记索引(在本例中为圆圈)处的整数在数组中向左或向右移动,直到我们可以将圆圈移至数组的最后一个索引.数组的最后一个整数始终为 0。
例如,
[4] 1 2 3 1 0,这里我们从圆圈 0(索引)开始
我们向右移动4,4 1 2 3 [1] 0
然后向右 1 次,4 1 2 3 1 [0]。游戏到此结束,我们赢了。
我的递归方法代码如下:
public static boolean rightWing (int circle, int[] game, List<Integer> checkerList){
int last = game.length-1;
if (circle == last){ // base case for recursion
return true;
}
if (circle < 0){ // if we go out of bounds on the left
return false;
}
if (circle > last){ // if we go out of bounds on the right
return false;
}
if (checkerList.contains(circle)){ // check for the impossible case
return false;
}
checkerList.add(circle); // adds the circle value for the last check to checkerList so we can check for the impossible case
int moveRight = circle + game[circle]; // these two integers help the game move according to the value of the int at circle
int moveLeft = circle - game[circle];
return rightWing( moveRight, game, checkerList) || rightWing(moveLeft, game,checkerList);
}
这很好用,但唯一的问题是它是递归的而且很慢。我正在尝试使用循环和堆栈/队列重新设计它以使其更有效率,但在写完这篇文章后我被卡住了(伪):
Boolean rightWing (int circle, List<int> game, List<int> checkerList)
Int lastPlace = game.size() - 1
For int i <- 0 to game.size() - 1 do
If i equals lastPlace then // returns true when i is at the last position of the game
Return true
任何关于如何前进的意见都将不胜感激!
最佳答案
最重要的一点:在针对运行缓慢问题调试应用时,您应该先收集一些性能数据,以确定您的应用将大部分时间花在了哪些地方。否则固定性能效率低下。您可以使用与 jdk 捆绑在一起的 jvisualvm
。
数据结构统治性能世界
它可能变慢的一个原因是:
if (checkerList.contains(circle)){ // check for the impossible case
return false;
}
列表中的项目越多,它变得越慢。对于 contains
方法,List 具有线性复杂度
。如果您使用 HashSet
,则可以使它恒定复杂度
。例如。如果您有包含 100 个元素的列表,使用 List
这部分的速度将比使用 HashSet
慢 100 倍左右。
另一件可能需要一些时间的事情是装箱/拆箱:每次将元素放入列表时,int
都会被包装到新的 Integer
对象中 - 这是称为拳击。您可能希望使用 IntSet
来避免装箱/拆箱并节省 GC 时间。
转换为迭代形式
我不希望这会影响您的申请速度,但只是为了回答的完整性。
将递归应用程序转换为迭代形式非常简单:在每次调用您的(或其他函数)时,隐藏的每个方法参数都存储在一个隐藏的堆栈中。在转换期间,您只需创建自己的堆栈并手动管理它
public static boolean rightWingRecursive(int circle, int[] game) {
Set<Integer> checkerList = new HashSet<Integer>();
Deque<Integer> statesToExplore = new LinkedList<>();
int last = game.length - 1;
statesToExplore.push(circle);
while (!statesToExplore.isEmpty()) {
int circleState = statesToExplore.pop();
if (circleState == last) { // base case for recursion
return true;
}
if (circleState < 0) { // if we go out of bounds on the left
continue;
}
if (circleState > last) { // if we go out of bounds on the right
continue;
}
if (checkerList.contains(circle)) { // check for the impossible case
continue;
}
checkerList.add(circle); // adds the circle value for the last check to
// checkerList so we can check for the
// impossible case
int moveRight = circle + game[circle]; // these two integers help the
// game move according to the
// value of the int at circle
int moveLeft = circle - game[circle];
statesToExplore.push(moveRight);
statesToExplore.push(moveLeft);
}
return false;
}
关于java - 在java中使用循环将递归方法转换为非递归方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40115510/