我目前有一个 AsyncTask
,它目前使用 OpenCV 使用 冒泡排序
技术比较图像。比如,我必须将 400
图像相互比较。这意味着 400*401/2=80,200
比较。假设一次比较需要 1 秒。所以,那是 80,200 秒
,大约是 22.27 小时
,长得离谱。因此,我开发了这种类型的算法:
它将 400
图像分成 5
组。因此每组中有 80
个图像。
算法的第一部分是在组成员中比较自己的图像。
因此,image1
会将自己与 image2-80
进行比较,这意味着有 79
次比较。 image2
将有 78
比较等等。这使得 3,160
比较。或者 3,160 秒
。同样,image81
会将自己与 image82-160
进行比较,依此类推。所以所有“组比较”都在 3,160 秒
内完成,因为它们是并行运行的。
算法的第二部分将比较group 1
元素和group 2
元素,group 2
和group 3
, group 3
和 group 4
等等。这意味着 image1
将与 image81-160
进行比较,这是 80
比较,因此 group 1
之间的总比较> 和 group 2
将是 80*80=6400
比较。是否可以将每个图像比较与组比较同时进行?也就是说,如果 image1
正在将自己与 image81-160
进行比较,那么 image2
应该做同样的事情等等,而其他组也在做同样的事情.因此,这部分应该只需要 6400 秒
。
现在,group1
将与group3
、group2
与group4
、group3
进行比较code> 与 group5
。 -6400 秒
之后,group1 将与 group4
和 group2
与 group5
进行比较。 -6400 秒
所以比较所有的组。
总时间 = 3160+6400+6400+6400=22,360sec
。我意识到小组越多,花费的时间就越多。因此,我必须增加小组人数以减少时间的增加。无论哪种方式,它都会将时间缩短到实际时间的将近 1/4
。
这个算法不现实吗?如果是这样,为什么?它的缺陷是什么?我将如何解决它?有没有更好的算法来更快地比较图像列表?显然不是quick sort
,我无法按升序或降序排列图像。或者我可以吗?
这个算法是否可行?实现它的最佳方法是什么? Thread
还是 AsyncTask
?
最佳答案
这是一个现实的算法,但理想情况下,您会希望能够在整个程序中使用相同数量的工作线程。为此,您需要使用偶数个线程,比如 8 个。
在 Pass1 上,线程 1 处理图像 1-50,线程 2 处理图像 51-100,等等。
在 Pass2 上,线程 1 和线程 2 都处理图像 1-100。 Thread1处理图像1-25和50-75,Thread2处理图像26-50和图像76-100。然后 Thread1 处理图像 1-25 和 76-100,Thread2 处理图像 26-75。
通过 3 到 8 遵循相同的模式 - 分配给正在处理的两个组的两个线程将它们之间的组分开。这样您就可以让所有线程都处于忙碌状态。但是,为了简化组分区,您需要偶数个线程。
4线程的示例代码
class ImageGroup {
final int index1;
final int index2;
}
class ImageComparer implements Runnable {
final Image[] images;
ImageGroup group1;
ImageGroup group2;
public ImageComparer(Image[] images, ImageGroup group1, ImageGroup group2) {
...
}
public void run() {
if(group2 == null) { // Compare images within a single group
for(int i = group1.index1; i < group1.index2; i++) {
for(int j = i + 1; j < group1.inex2; j++) {
compare(images[i], images[j]);
}
}
} else { // Compare images between two groups
for(int i = group1.index1; i < group1.index2; i++) {
for(int j = group2.index1; j < group2.index2; j++) {
compare(images[i], images[j]);
}
}
}
}
}
ExecutorService executor = new ThreadPoolExecutor(); // use a corePoolSize equal to the number of target threads
// for 4 threads we need 8 image groups
ImageGroup group1 = new ImageGroup(0, 50);
ImageGroup group2 = new ImageGroup(50, 100);
...
ImageGroup group8 = new ImageGroup(450, 500);
ImageComparer comparer1 = new ImageComparer(images, group1, null);
ImageComparer comparer2 = new ImageComparer(images, group3, null);
...
ImageComparer comparer4 = new ImageComparer(images, group7, null);
// submit comparers to executor service
Future future1 = executor.submit(comparer1);
Future future2 = executor.submit(comparer2);
Future future3 = executor.submit(comparer3);
Future future4 = executor.submit(comparer4);
// wait for threads to finish
future1.get();
future2.get();
future3.get();
future4.get();
comparer1 = new ImageComparer(images, group2, null);
...
comparer4 = new ImageComparer(images, group8, null);
// submit to executor, wait to finish
comparer1 = new ImageComparer(images, group1, group3);
...
comparer4 = new ImageComparer(images, group7, group6);
// submit to executor, wait to finish
comparer1 = new ImageComparer(images, group1, group4);
...
comparer4 = new ImageComparer(images, group7, group5);
关于java - 算法优化 - 并行 AsyncTasks 还是线程?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16159699/