安卓魔方科西恩巴最优求解器内存不足

Question

我想就以下问题寻求帮助。

我想创建一个用最优解解决魔方的应用程序。我下载了下面的库，据说它就是用Kociemba的算法来做的。

http://kociemba.org/twophase.jar

显然它可以在0.5秒内解决立方体，但在我的应用程序中，由于内存问题，它从未返回解决方案。我知道它可以工作，我用错误的输入测试了它，它返回了记录的错误代码。

我在onCreate方法中这样调用它:

resultTxt = Search.solution(data, 21, 10, true); 

resultTxt是一个字符串变量，它应该包含解决方案。

它很快地消耗了内存。

我尝试了IntentService，但没有成功。我的意思是它并没有真正改变什么。

由于我没有发现任何证据表明有人在任何android应用程序中使用这个库，我想我应该问一个比我更有经验的人。

有什么方法可以让我在Android上工作，或者这是不可能的，因为我想?

Answer 1

这可能有点晚了，但我最近也遇到了这个问题，当时我正在研究一个使用android智能手机扫描魔方并计算解决方案的魔方解决机器人，所以我将把我发现的东西放在这里。

---

有什么问题?

让我们首先讨论导致性能问题的问题实际位于何处。

速度如此之慢的原因是CoordCube类，它看起来(非常简化)像这样:

class CoordCube {
    short[] pruneTables;
    static {
        /* compute and save ~50MB data in `pruneTables` */
    }
}

基本上，它的作用是将大量数据加载到查找表中，这是快速求解过程所必需的。一旦该类首次实例化，JVM就会自动执行此加载。Search.solution()中的line 159:

/* simplified code of solution() */
if (cube.isValid()) {
    CoordCube c = new CoordCube(); // pruning tables will be loaded on this line

这也是为什么只要传递的多维数据集无效，这个方法执行的时间可以忽略不计的原因，因为它永远不会加载表。

---

可能的解决方式:

既然我们已经确定了问题所在，让我们集中精力解决它。

我想出了3种不同的方法，其中第一个可能是最简单的(但也是最慢的执行方式…)，也在我的应用程序中使用。其他两个只是关于如何进一步提高性能的想法。

方法1:

第一种也是最简单的方法是手动预加载查找表在一种LoadingActivity中，ProgressBar显示我们当前的进度。为此，我们首先希望能够手动控制加载哪些表的准确时间(类首次实例化的时间不够精确)，如下所示:

loadTable1() {
     /* load pruning table number 1 */
}

为此，我在这里编写了一些简单的实用程序(代码太长，无法粘贴)。请务必查看我的说明，了解如何在你的应用中正确导入这些代码。

我们也可能想在后台进行加载，即在AsyncTask中。这就是我在我的应用程序中如何做到的(PruneTableLoader包含在前面的链接中):

private class LoadPruningTablesTask extends AsyncTask<Void, Void, Void> {
    private PruneTableLoader tableLoader = new PruneTableLoader();
    @Override
    protected Void doInBackground(Void... params) {
        /* load all tables if they are not already in RAM */
        while (!tableLoader.loadingFinished()) { // while tables are left to load
            tableLoader.loadNext(); // load next pruning table
            publishProgress(); // increment `ProgressBar` by one
        }
        return null;
    }
    @Override
    protected void onProgressUpdate(Void... values) {
        super.onProgressUpdate(values);
        /* increment `ProgressBar` by 1 */
    }
}

当使用我的PruneTableLoader时，所有表的加载需要在我的Samsung Galaxy S3和250 MB RAM free上加载大约40s。(相比之下，自动加载时需要well over 2min，而且经常导致崩溃…)

考虑到它在PC上需要< 1s，这可能听起来仍然很慢，但至少你必须只做一次，因为Android缓存静态变量，所以你不必在每次启动应用程序时加载它们。

方法2:(未经测试)

我认为将修剪表保存在file或database中并从那里加载它们而不是总是重新计算它们会更快。虽然我还没有测试过，但它可能需要相当多的工作才能使保存和加载正常工作。(也可能由于访问时间的原因，它甚至没有更快)

方法3:(未经测试)

嗯，最困难也是几十年来最昂贵的解决方案是，简单地在C或C++中重写整个算法，并通过JNI在App中调用它。(据我所知Herbert Kociemba还没有出版他的C-sourcecode…)

这肯定是性能方面最快的解决方案。(也适用于求解过程本身)

---

总而言之方法1可能是最努力/最有利的方法(对我来说也是)，所以我建议你采用这种方法，如果加载时间对你的应用程序来说不是一个大问题。

我对自己的表现并不完全满意，所以我可能会尝试方法2，甚至可能在将来的某个时候尝试方法3。如果我这样做了，我会把我的结果更新这篇文章。