需要帮助将方法从递归更改为迭代

Question

我正在开发一个程序，该程序将在给定数据和正确数据的哈希值的情况下修复数据损坏。即使只处理几个字节的数据，大约 4 或 5 位被损坏后它开始变慢，所以我想我会让它迭代而不是递归。在做了一些研究之后，我发现我可以使用堆栈来做到这一点。我目前无法找到将变量从堆栈中弹出的正确位置。这是原始方法。

private static void fixFile(byte[] data, byte[] hash, byte[] correctHash, MessageDigest hasher, long depth)
{
    int len = data.length;
    outer: for(int i = 0; i < len; i++)
    {
        byte origVal = data[i];
        for(int j = 0; j < 8; j++)
        {
            data[i] = (byte) (data[i] ^ (1 << j));

            if(depth > 1)
                fixFile(data, hash, correctHash, hasher, depth - 1);
            hash = hasher.digest(data);

            if(!Arrays.equals(correctHash, hash))
                data[i] = origVal;
            else
                break outer;
        }
    }
}

这是我尝试使其迭代的修改方法。

private static void fixFile(byte[] data, byte[] hash, byte[] correctHash, MessageDigest hasher, long depth)
{
    Stack stack = new Stack<Integer>();

    int len = data.length;
    outer: for(int i = 0; i < len; i++)
    {
        byte origVal = data[i];
        for(int j = 0; j < 8; j++)
        {
            data[i] = (byte) (data[i] ^ (1 << j));

            if(depth > 1)
            {
                stack.push(depth);
                stack.push(i);
                stack.push(j);
                depth--;
                i = -1;
                j = 0;
                continue outer;
            }
            else
            {
                // where do I put this to make it work.
                j = stack.pop();
                i = stack.pop();
                depth = stack.pop();
            }
            hash = hasher.digest(data);

            if(!Arrays.equals(correctHash, hash))
                data[i] = origVal;
            else
                break outer;
        }
    }
}

Answer 1

我认为你的递归方法是解决这个问题的理想方法，所有时间都将花在摘要函数上。

但是，当您修复深度位时，您可以获得程序速度的阶乘（深度）改进。（因此对于 6 位，这将使程序运行速度提高 6*5*4*3*2*1 = 720 倍。）

问题是您当前的代码当前会切换数据中的深度位，但顺序不限。即当它切换三个位时，它将尝试切换位 1、2、3 和 2、1、3 和 3、1、2 和 3、2、1 和 1、3、2 和 2、3、1（以及许多其他选项）。请注意，在每种情况下，都会切换完全相同的 3 位，因此没有必要对它们进行全部测试。

您可以通过向您的代码传递附加参数来解决此问题，说明最后一位被切换的位置（即，将 i 和 j 作为 i_base 和 j_base 传递），然后只允许您的代码如果新位位于数据中较晚的位置，则切换新位（即如果 i>i_base || (i==i_base && j>j_base)).

需要帮助将方法从递归更改为迭代

Need help changing a method from recursive to iterative

java

algorithm

recursion

stack

iteration