Java和计算中的线程 [英] threads in Java and computation
问题描述
我是java的新手，我正在尝试编写一个带有两个参数的程序:
I am new to java, and I am trying to write a program that takes two parameters:
- 我们必须对素数求和的数字
- 我们必须执行此操作的线程数
因此，我使用一种名为 Eratosthene 的方法，该方法存储一个 boolean 数组，如果数字是素数，则将其标记为true，然后标记所有的倍数这个数字是错误的.
So I use a method named Eratosthene that stores an array of boolean and if a number is prime, we mark it true and after that we mark all the multiples of this number false.
我尝试将我的数组划分为每个线程的子数组，并在每个子数组中进行操作，最后将所有子数组的结果求和.
I try to devide my array into sub arrays for each thread and do the operation in each sub arrays, and at the end sum all the results of sub arrays.
但是我不知道我在哪里做错了:有时该程序无法给出良好的结果.
But I don't know where I am doing wrong: sometimes the program doesn't give the good result.
这是我的代码:
SumPrime.java
import java.util.*;
import java.util.concurrent.*;
public class SumPrimes {
private boolean array[];
private int numberOfWorkers;
private Semaphore allFinished;
public SumPrimes(int num, int threads){
array = new boolean[num];
numberOfWorkers = threads;
for (int i = 2; i < num; i++)
array[i] = true;
}
private class SumParallel extends Thread {
int min;
int max;
long sum;
SumParallel(int min, int max){
this.min = min;
this.max = max;
sum = 0;
}
public void run() {
for (int i = min; i < max; i++) {
if (array[i]) {
for (int j = min; j*i < array.length; j++) {
array[i*j] = false;
}
sum += i;
}
}
allFinished.release();
}
public long getSum() {
return sum;
}
}
public void SumInParallel() {
allFinished = new Semaphore(0);
List<SumParallel> workers = new ArrayList<SumParallel>();
int lengthOfOneWorker = array.length / numberOfWorkers;
for (int i = 0; i < numberOfWorkers; i++) {
int start = i * lengthOfOneWorker;
int end = (i+1) * lengthOfOneWorker;
if (i == numberOfWorkers - 1)
end = array.length;
SumParallel worker = new SumParallel(start, end);
workers.add(worker);
worker.start();
}
try {
allFinished.acquire(numberOfWorkers);
} catch (InterruptedException ignored) {}
int sum = 0;
for (SumParallel w : workers){
sum += w.getSum();
}
System.out.println("The sum of prime numbers is: " + sum);
}
public static void main(String[] args) {
int limitNum = Integer.parseInt(args[0]);
int threadNum = Integer.parseInt(args[1]);
SumPrimes sum_primes = new SumPrimes(limitNum, threadNum);
sum_primes.SumInParallel();
}
}
您可以这样运行程序:
java SumPrimes 1000 3
我愿意接受任何有关改进我的代码的建议.
I am open to any suggestions for improving my code.
推荐答案
您需要完全重新考虑线程的逻辑.
You need to entirely re-think the logic of your thread.
各种线程不能访问array的相同范围，例如如果线程具有min = 100和max = 150，则只能使用和/或更改范围在100到149(包括)之间的元素.
The various threads cannot access the same range of the array, e.g. if a thread has min = 100 and max = 150, then only elements in range 100 to 149 (inclusive) may be used and/or changed.
您的代码:
for (int i = min; i < max; i++) {
if (array[i]) {
for (int j = min; j*i < array.length; j++) {
array[i*j] = false;
以开头 ，从而生成i*j = 10000.如果array真的那么大，则意味着您访问array[10000]，但这是不允许的.当然，数组不是那么大，所以代码什么都不做.
starts with i = 100, j = 100 which makes i*j = 10000. If array was really that big, it means you access array[10000], but that is not allowed. Of course, the array isn't that big, so the code does nothing.
啊，您说，第一个线程具有min = 0和max = 50，因此它将更改从索引0(0 * 0)到2401(49 * 49)的值，并且由于数组小于该值，它将更新整个阵列，但是 不允许 .
Ahh, you say, the first thread has min = 0 and max = 50, so it will change values from index 0 (0*0) up to 2401 (49*49), and since array is smaller than that, it will update the entire array, but that is not allowed.
现在，再考虑一下.
如果范围是min = 100, max = 150，则需要先清除该范围内的所有偶数，然后清除所有被3整除的数字，然后是所有...，依此类推，但仅限于该范围.
If the range is min = 100, max = 150, then you need to start by clearing all even numbers in that range, then all numbers divisible by 3, then all ... and so on, but only for that range.
我会让你重新考虑一下逻辑.
I'll leave you to re-think the logic.
更新
要将 Eratosthenes筛子应用于一定范围，我们需要素数最大为该范围的最大值的平方根.
To apply Sieve of Eratosthenes to some range, we need the prime numbers up to the square root of the max of that range.
如果范围是min = 150, max = 200，则是maxPrime = sqrt(200) = 14，因此我们需要从2到14(含)的质数，那么我们可以将范围150-199更新.
If the range is min = 150, max = 200, then maxPrime = sqrt(200) = 14, so we need the primes from 2 to 14 (inclusive), then we can update range 150-199.
假设我们首先更新array以找到2-14范围内的所有素数，我们可以使用它来迭代目标范围(150-199)中这些素数的倍数.为此，我们需要从素数的最低倍数> = min开始，因此我们需要将min舍入为prime的下一个倍数.
Assuming we first update array to find all the primes in range 2-14, we can use that to iterate the multiples of those primes in the target range (150-199). For that we need to start at the lowest multiple of the prime that is >= min, so we need to round up min to the next multiple of prime.
使用整数数学，将四舍五入到下一个倍数，我们计算:
With integer math, to round up to next multiple, we calculate:
lower = (min + prime - 1) / prime * prime
这为我们提供了主要逻辑:
This gives us the main logic:
maxPrime = (int) Math.sqrt(max);
for (int prime = 2; prime <= maxPrime; prime++) {
if (array[prime]) {
int lower = (min + prime - 1) / prime * prime;
for (int i = lower; i < max; i += prime)
array[i] = false
我们还应该让每个线程负责首先设置范围内的所有布尔值，以便该部分也成为多线程.
We should also make each thread responsible for first setting all the booleans in the range, so that part becomes multi-threaded too.
现在，主逻辑必须首先在主线程中找到范围2-sqrt(N)中的质数，然后在线程之间分配剩余范围.
The master logic now has to first find the primes in range 2-sqrt(N) in the main thread, then split the remaining range between the threads.
这是我的尝试:
public static long sumPrimes(int n, int threadCount) {
// Find and sum the "seed" primes needed by the threads
int maxSeedPrime = (int) Math.sqrt(n + 2); // extra to be sure no "float errors" occur
boolean[] seedPrime = new boolean[maxSeedPrime + 1];
AtomicLong totalSum = new AtomicLong(sumPrimes(seedPrime, seedPrime, 0, maxSeedPrime));
// Split remaining into ranges and start threads to calculate sums
Thread[] threads = new Thread[threadCount];
for (int t = 0, rangeMin = maxSeedPrime + 1; t < threadCount; t++) {
int min = rangeMin;
int max = min + (n - min + 1) / (threadCount - t) - 1;
threads[t] = new Thread(() ->
totalSum.addAndGet(sumPrimes(seedPrime, new boolean[max - min + 1], min, max))
);
threads[t].start();
rangeMin = max + 1;
}
// Wait for threads to end
for (int t = 0; t < threadCount; t++) {
try {
threads[t].join();
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
// Return the calculated sum
return totalSum.get();
}
private static long sumPrimes(boolean[] seedPrime, boolean[] rangePrime, int min, int max/*inclusive*/) {
// Initialize range
for (int i = Math.max(min, 2); i <= max; i++) {
rangePrime[i - min] = true;
}
// Mark non-primes in range
int maxPrime = (int) Math.sqrt(max + 1); // extra to be sure no "float errors" occur
for (int prime = 2; prime <= maxPrime; prime++) {
if (seedPrime[prime]) {
int minMultiple = (min + prime - 1) / prime * prime;
if (minMultiple <= prime)
minMultiple = prime * 2;
for (int multiple = minMultiple; multiple <= max ; multiple += prime) {
rangePrime[multiple - min] = false;
}
}
}
// Sum the primes
long sum = 0;
for (int prime = min; prime <= max; prime++) {
if (rangePrime[prime - min]) {
sum += prime;
}
}
return sum;
}
测试
public static void main(String[] args) {
test(1000, 3);
test(100000000, 4);
}
public static void test(int n, int threadCount) {
long start = System.nanoTime();
long sum = sumPrimes(n, threadCount);
long end = System.nanoTime();
System.out.printf("sumPrimes(%,d, %d) = %,d (%.9f seconds)%n",
n, threadCount, sum, (end - start) / 1e9);
}
输出
sumPrimes(1,000, 3) = 76,127 (0.005595600 seconds)
sumPrimes(100,000,000, 4) = 279,209,790,387,276 (0.686881000 seconds)
更新2
上面的代码使用的是lambda表达式:
The code above is using a lambda expression:
threads[t] = new Thread(() ->
totalSum.addAndGet(sumPrimes(seedPrime, new boolean[max - min + 1], min, max))
);
如果您不想使用lambda表达式，例如因此它将在Java 7上运行，您可以改用匿名类:
If you don't want to use a lambda expression, e.g. so it will run on Java 7, you can use an anonymous class instead:
threads[t] = new Thread() {
@Override
public void run() {
totalSum.addAndGet(sumPrimes(seedPrime, new boolean[max - min + 1], min, max));
}
};
这篇关于Java和计算中的线程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
