- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
基本上,我花了几个小时研究实现递归和多线程快速排序和合并排序的最佳方法(这篇文章仅涉及快速排序)。我的目标是获取给定计算机中的每个逻辑处理器并将它们全部固定以获得最大的快速排序速度。
我在创建线程时采用了递归划分问题的方法,直到数组已排序或达到了 cpu 上的处理器数量,在这种情况下,问题的其余部分不会划分到新线程上,而是在自己的核心上执行其余部分。
在创建了一个只能在我的计算机上运行的非常基本的解决方案之后,我遇到了 Fork/Join 框架,我尝试在下面使用它,但我实际上不知道如何使用。我想出的方法在对 0 - 1000 范围内的 10000000 个随机数进行排序时比单线程对应的要慢,但我仍然认为它很有趣,因为在它的 docs 中。它说,它能够从较慢的线程中窃取工作,无论这意味着什么。
然后我最近听说了线程池,并最初创建了所有线程并将它们分发出去,因为创建新线程会给系统带来负担。但我从未尝试去实现这一点。也许我对 Fork/Join 的理解存在偏差,我想知道是否有人可以指出我正确的方向,或者告诉我在当前程序中我做错了什么。
下面您将看到我对多线程快速排序和单线程快速排序的尝试,这就是我试图将其转换为多线程排序的方法。任何帮助表示赞赏。干杯!.
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public class MultithreadedQuicksort {
public static void main(String[] args) {
List<Comparable> nums = new ArrayList<Comparable>();
Random rand = new Random();
for (int i=0; i<10000000; i++) {
nums.add(rand.nextInt(1000));
}
long start = System.currentTimeMillis();
Quicksort quickSort = new Quicksort(nums, 0, nums.size() -1);
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(quickSort);
long end = System.currentTimeMillis();
System.out.println(end - start);
System.out.println(nums.size());
}
}
class Quicksort extends RecursiveAction {
int first;
int last;
private List<Comparable> nums;
Comparable midValue;
int midIndex;
int low;
int high;
public Quicksort(List<Comparable> nums){
this.nums=nums;
this.low = 0;
this.high = nums.size() - 1;
}
public Quicksort(List<Comparable> nums, int first, int last) {
this.first = first;
this.last = last;
this.nums = nums;
this.low = first;
this.high = last;
this.midIndex = (first + last) / 2;
this.midValue = nums.get(midIndex);
}
@Override
protected void compute() {
split();
if (high > first)
invokeAll(new Quicksort(nums, first, high));
if (low < last)
invokeAll(new Quicksort(nums, low, last));
}
public void split() {
while(low < high) {
while (nums.get(low).compareTo(midValue) < 0) {
low++;
}
while (nums.get(high).compareTo(midValue) > 0) {
high--;
}
if (low <= high) {
swap(low, high);
low++;
high--;
}
}
}
public void swap(int index1, int index2)
{
Comparable temp;
temp = nums.get(index1);
nums.set(index1, nums.get(index2));
nums.set(index2, temp);
}
}
单线程
public static void quickSort(List<Comparable> nums, int first, int last) {
int low = first;
int high = last;
int midIndex = (first + last) / 2;
Comparable midValue = nums.get(midIndex);
while(low < high) {
while (nums.get(low).compareTo(midValue) < 0) {
low++;
}
while (nums.get(high).compareTo(midValue) > 0) {
high--;
}
if (low <= high) {
swap(nums, low, high);
low++;
high--;
}
}
if (high > first)
quickSort(nums, first, high);
if (low < last)
quickSort(nums, low, last);
}
最佳答案
我对java不太了解,所以下面的示例代码可能是多线程中runnable的尴尬用法。此示例代码使用 8 个线程,qsortmt() 进行分区并启动 qsort0() 的两个实例。 qsort0() 的每个实例都会进行分区并调用 qsort1() 的两个实例。 qsort1() 的每个实例都会进行分区并调用 qsort2() 的两个实例。 qsort2() 的每个实例都会调用 qsort()。对于本示例中使用的 1600 万个整数,8 线程排序大约需要 1 秒,而非线程排序大约需要 1.6 秒,因此节省的时间并不多。部分问题是分区步骤是在调用线程对子分区进行操作之前完成的。
切换到C++和Windows native 线程,8个线程大约花费0.632秒,非线程大约1.352秒。切换到合并排序,将数组分成8部分,对每个部分进行排序,然后合并8部分大约需要0.40秒,单线程大约1.45秒。
package x;
import java.util.Random;
public class x {
class qsort0 implements Runnable
{
int[] a;
int lo;
int hi;
private qsort0(int[] a, int lo, int hi)
{
this.a = a;
this.lo = lo;
this.hi = hi;
}
@Override
public void run()
{
if(this.lo >= this.hi)
return;
int pi = partition(this.a, this.lo, this.hi);
Thread lt = new Thread(new qsort1(a, this.lo, pi));
Thread rt = new Thread(new qsort1(a, pi+1, this.hi));
lt.start();
rt.start();
try {lt.join();} catch (InterruptedException ex){}
try {rt.join();} catch (InterruptedException ex){}
}
}
class qsort1 implements Runnable
{
int[] a;
int lo;
int hi;
private qsort1(int[] a, int lo, int hi)
{
this.a = a;
this.lo = lo;
this.hi = hi;
}
@Override
public void run()
{
if(this.lo >= this.hi)
return;
int pi = partition(this.a, this.lo, this.hi);
Thread lt = new Thread(new qsort2(a, this.lo, pi));
Thread rt = new Thread(new qsort2(a, pi+1, this.hi));
lt.start();
rt.start();
try {lt.join();} catch (InterruptedException ex){}
try {rt.join();} catch (InterruptedException ex){}
}
}
class qsort2 implements Runnable
{
int[] a;
int lo;
int hi;
private qsort2(int[] a, int lo, int hi)
{
this.a = a;
this.lo = lo;
this.hi = hi;
}
@Override
public void run() {
if(this.lo >= this.hi)
return;
qsort(this.a, this.lo, this.hi);
}
}
// quicksort multi-threaded
@SuppressWarnings("empty-statement")
public static void qsortmt(int[] a, int lo, int hi)
{
if(lo >= hi)
return;
int pi = partition(a, lo, hi);
Thread lt = new Thread(new x().new qsort0(a, lo, pi));
Thread rt = new Thread(new x().new qsort0(a, pi+1, hi));
lt.start();
rt.start();
try {lt.join();} catch (InterruptedException ex){}
try {rt.join();} catch (InterruptedException ex){}
}
@SuppressWarnings("empty-statement")
public static int partition(int []a, int lo, int hi)
{
int md = lo+(hi-lo)/2;
int ll = lo-1;
int hh = hi+1;
int t;
int p = a[md];
while(true){
while(a[++ll] < p);
while(a[--hh] > p);
if(ll >= hh)
break;
t = a[ll];
a[ll] = a[hh];
a[hh] = t;
}
return hh;
}
@SuppressWarnings("empty-statement")
public static void qsort(int[] a, int lo, int hi)
{
while(lo < hi){
int ll = partition(a, lo, hi);
int hh = ll+1;
// recurse on smaller part, loop on larger part
if((ll - lo) <= (hi - hh)){
qsort(a, lo, ll);
lo = hh;
} else {
qsort(a, hh, hi);
hi = ll;
}
}
}
public static void main(String[] args)
{
int[] a = new int[16*1024*1024];
Random r = new Random(0);
for(int i = 0; i < a.length; i++)
a[i] = r.nextInt();
long bgn, end;
bgn = System.currentTimeMillis();
qsortmt(a, 0, a.length-1);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i++){
if(a[i-1] > a[i]){
System.out.println("failed");
break;
}
}
System.out.println("milliseconds " + (end-bgn));
}
}
关于java - 多线程快速排序比预期慢很多,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59123113/
我对java有点陌生,所以如果我犯了一个简单的错误,请原谅我,但我不确定我哪里出错了,我收到的错误是“预期的.class,预期的标识符,而不是声明, ';'预期的。”我尝试了不同的方法,并从这些方法中
This question already has answers here: chai test array equality doesn't work as expected (3个答案) 3年前
我正在学习 Java(对不起,我的英语很差,这不是我的母语),当我在 Eclipse (JavaSE-1.7) 中在我输入的每个“try”中执行“try-finally” block 时,会出现以下消
我收到两个错误,指出 token 上的语法错误,ConstructorHeaderName expected instead & token “(”上的语法错误,< expected 在线: mTM.
我找不到错误。 Eclipse 给我这个错误。每个 { } 都是匹配的。请帮忙。 Multiple markers at this line - Syntax error on token “)”,
代码: import java.awt.*; import javax.swing.*; import java.awt.event.*; public class DoubleIt extends
我正在用 python(Vs 代码)编写代码,但出现此错误: Expected ")" Pylance 错误发生在:def main() 我试着运行我的 main 并将它打印到我的屏幕上。我用谷歌搜
我正在尝试按照 documentation 中的建议使用异步函数。但我收到此错误 意外的 token ,预期 ( async function getMoviesFromApi() { try
Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。 想改善这个问题吗?更新问题,以便将其作为on-topic
Closed. This question does not meet Stack Overflow guidelines。它当前不接受答案。 想改善这个问题吗?更新问题,以便将其作为on-topic
第一行包含一个表示数组长度的整数p。第二行包含用空格分隔的整数,这些整数描述数组中的每个元素。第三行打印一个整数,指示负数组的数量。 package asgn3; import java.util.*
好的,我是初学者,我必须修复此 java 表达式语言代码才能在我的系统 (Windchill) 中工作,但看起来我在语法中遗漏了一些内容: LWCNormalizedObject lwc =
我无法编译我的程序! 我想我缺少一个花括号,但我怎么也看不出在哪里! import javax.swing.*; import java.awt.*;
我的 jQuery 代码有问题,我的 Firebug 向我发出警告:需要选择器。 这是代码: $("img[id$='_tick']").each(function() { $(this).c
我的新类(class) Fountainofyouth 遇到了问题。尝试构建整个项目后,调试器显示 warning: extended initializer lists only available
我已经从 Java 转向 CPP,并且正在努力围绕构造构造函数链进行思考,我认为这是我的问题的根源。 我的头文件如下: public: GuidedTour(); GuidedTour(string
鉴于以下 for(var i=0; i< data.cats.length; i++) list += buildCategories(data.cats[i]); jsLint 告诉我 Expect
我有这个 json,但 Visual Studio Code 在标题中给了我警告。 [ { "title": "Book A", "imageUrl": "https:
我正在尝试编写一个有条件地禁用四个特殊成员函数(复制构造、移动构造、复制赋值和移动赋值)的包装类,下面是我用于测试目的的快速草稿: enum class special_member : uint8_
所以我用 F# 编写了一个非常简单的程序,它应该对 1000 以下的所有 3 和 5 的倍数求和: [1..999] |> List.filter (fun x -> x % 3 = 0 || x %
我是一名优秀的程序员,十分优秀!