0

我想就我遇到的以下问题寻求一些帮助。

我想创建一个应用程序，用最佳解决方案解决魔方问题。我下载了以下库，据说它使用 Kociemba 的算法就是这样做的。

http://kociemba.org/twophase.jar

显然它可以在 0.5 秒内解决多维数据集，但在我的应用程序中，由于内存问题，它从未返回解决方案。我知道它有效，我用错误的输入对其进行了测试，它返回了记录的错误代码。

我在我的 onCreate 方法中这样调用它：

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

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

它很快就吃光了内存。

我用 IntentService 尝试过，但没有成功。我的意思是它并没有真正改变任何东西。

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

有什么办法可以在 Android 上完成这项工作，还是像我想象的那样不可能？

4

1 回答 1

1

可能有点晚了，但是我最近在使用 Android 智能手机扫描魔方并计算解决方案的魔方求解机器人时也遇到了这个问题，所以我将在这里放置什么我发现了。

问题是什么？

让我们从讨论导致该性能问题的问题的实际位置开始。

这么慢的原因是 class CoordCube，它看起来（非常简化）像这样：

class CoordCube {
    short[] pruneTables;

    static {
        /* compute and save ~50MB data in `pruneTables` */
    }
}

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

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

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

可能的解决方案：

既然我们已经确定了问题出在哪里，那么我们来关注如何解决它。

我提出了 3 种不同的方法，其中第一种可能是最简单的（但也是最慢的执行方式......），并且也用于我的应用程序中。另外两个只是关于如何进一步提高性能的想法。

方法一：

第一种也是最简单的方法是手动预加载查找表，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 */
    }
}

在使用 myPruneTableLoader时，所有表的加载都需要40s在 mySamsung Galaxy S3上使用250 MB RAM free。（相比之下，well over 2min自动加载它们时需要它，而且通常会导致崩溃......）

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

方法2：（未经测试）

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

方法3：（未经测试）

嗯，最难也是几十年来工作成本最高的解决方案是，简单地重写整个算法，C或者C++在应用程序中通过JNI. （据我所知，Herbert Kociemba还没有发表他的作品……）C-sourcecode

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

总而言之，方法 1可能是一开始就努力/受益的最佳方法（对我来说也是如此），所以我建议您使用它，以防加载时间对您的应用程序来说不是那么大的问题.

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

于 2014-08-16T15:00:59.820 回答