java - Android:AsyncTask.doInBackground 中可取消的 Java Collection 排序

Question

我正在为 Android 手机编写一个应用程序。

我有一个 java.util.ArrayList，其中包含需要自定义 java.util.Comparator 才能正确排序的对象。

我知道我可以使用 java.util.Collections.sort() 但数据量太大，我想在 中对 ArrayList 进行排序android.os.AsyncTask.

我不想使用多个 AsyncTask 对象，每个对象都会对数据的子集进行排序。

任何 AsyncTask 都可以取消，因此我想在排序时定期调用 AsyncTask.isCancelled()。如果它返回 true，我就放弃排序(以及我的整个数据集)。

我在 Google 上搜索，但找不到一种 AsyncTask 友好的方式来排序，同时定期检查取消情况。

我可以在 java.util.Comparator.compare() 的实现中调用 isCancelled() 并抛出我自己的 java 子类。 lang.RuntimeException 如果返回 true。然后针对该特定异常尝试 {java.util.Collections.sort(ArrayList, Comparator);} catch () {}。我对这种方法不太满意。

或者，我可以使用中间 java.util.TreeSet 并编写 2 个循环，每个循环在每次迭代之前检查取消情况。第一个循环会将 ArrayList 的所有项目添加到 TreeSet 中(并且我的 Comparator 实现使它们在插入时保持排序)。第二个循环会将 TreeSet 中的所有对象以正确的顺序添加回 ArrayList，这要归功于 TreeSet 的自然 java.util.Iterator。这种方法会使用一些额外的内存，但肯定会起作用。

我能想到的最后一种方法是自己实现我在 Android 中实际寻找的东西:使用 java.util.List 进行通用 java.util.List (最好是快速)排序。 util.Comparator 和定期检查取消的 android.os.AsyncTask。

有人发现了吗？
您还有其他解决方案吗？

编辑:

虽然我没有考虑过排序方法签名会是什么样子，但我也非常乐意使用 android.os.CancellationSignal 来决定何时放弃排序。

Answer 1

我将尝试在这里描述我的思考过程。如果有人在任何时候有更好的报价......

让我们再次确认我们想要实现的目标。我们需要一个具有以下属性的排序算法

1. 在单个任务上运行

2. 就位，即不使用额外的内存

3. 我们应该能够随意取消排序，即当我们决定不再需要它时立即返回或非常接近它。

4. 提高效率

5. 不会使用异常来控制应用程序的完全正常流程。你对那个感到不舒服是对的☺

   据我所知，没有原生 Android 工具可以做到这一点

让我们先关注一下要求 3。

这里引用 asycTask documentation , 关于取消任务的部分

BlockquoteTo ensure that a task is cancelled as quickly as possible, you should always check the return value of isCancelled() periodically from doInBackground(Object[]), if possible (inside a loop for instance.) ".

意思是，迭代排序算法(在每次迭代中您必须检查 isCancalled() 标志)将满足此要求。问题是简单的迭代排序算法，例如插入排序，通常效率不是很高。对于小输入来说这应该不重要，但既然你说你的典型输入是一个巨大的数组列表，并且无论如何都会触发我们的任务，所以我们需要尽可能保持高效。

既然你确实提到了快速排序，我就想，它已经拥有我们需要的一切了!它高效、到位、只运行一项任务。只有一处不足。它的经典形式是递归的，这意味着它不会在取消后立即返回。幸运的是，简短的 Google 搜索会产生许多可以提供帮助的结果，包括 this one 。简而言之，您可以找到迭代快速排序的变体。这是通过用一个堆栈替换递归调用堆栈来完成的，该堆栈存储递归实现用于预形成“分区”的相同索引。采用这个算法，在每次迭代中添加一个检查是否 asyncTask.isCancelled() ，然后您就得到了一个满足所有要求的解决方案。