标题翻译
Generate unique prime numbers by multiple threads in Java
问题
在下面的代码中，多个生产者线程有时会生成相同的质数。我如何确保不同的生产者始终生成唯一的质数？
public class UniquePrimes {
private static BlockingQueue<Integer> linkedBlockingQueue = new LinkedBlockingQueue<Integer>();
static ConcurrentHashMap<Integer, String> primesproduced = new ConcurrentHashMap<Integer, String>();
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
System.out.print("Enter number of threads you want to create: ");
int NOOFTHREADS = reader.nextInt();
reader.close();
ExecutorService executorPool = Executors.newFixedThreadPool(NOOFTHREADS);
AtomicInteger currentPrime = new AtomicInteger();
Runnable producer = () -> {
String threadName = Thread.currentThread().getName();
int p = 0;
try {
synchronized (currentPrime) { // 添加同步块以确保原子性递增
p = generateNextPrime(currentPrime.incrementAndGet());
}
linkedBlockingQueue.put(p);
primesproduced.put(p, threadName);
System.out.println("Thread " + threadName + " produced prime number " + p);
} catch (InterruptedException e) {
e.printStackTrace();
}
};
List<Runnable> tasks = new ArrayList<Runnable>();
for (int i = 0; i < NOOFTHREADS; i++) {
tasks.add(producer);
}
CompletableFuture<?>[] futures = tasks.stream().map(task -> CompletableFuture.runAsync(task, executorPool))
.toArray(CompletableFuture[]::new);
CompletableFuture.allOf(futures).join();
executorPool.shutdown();
System.out.println("\nTotal unique primes produced: " + primesproduced.size() + " and they are: ");
System.out.print(
primesproduced.entrySet().stream().filter(map -> map.getKey().intValue() > 0).map(k -> "[" + k + "]")
.collect(Collectors.joining(",")));
}
private static int generateNextPrime(int currentPrime) {
currentPrime++;
if (currentPrime < 2) {
currentPrime = 2;
return currentPrime;
}
for (int i = 2; i < currentPrime; i++) {
if (currentPrime % i == 0) {
currentPrime++;
i = 2;
} else {
continue;
}
}
return currentPrime;
}
}
目前，多个生产者可能会生成相同的质数值。如何确保每个生产者生成的质数值不会由其他生产者先前生成？
谢谢您的帮助。
英文翻译
In this code below multiple producer threads sometimes generate the same prime numbers. How I can ensure that different producers always generate a unique prime number?
public class UniquePrimes {
private static BlockingQueue<Integer> linkedBlockingQueue = new LinkedBlockingQueue<Integer>();
static ConcurrentHashMap<Integer, String> primesproduced = new ConcurrentHashMap<Integer, String>();
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
System.out.print("Enter number of threads you want to create: ");
int NOOFTHREADS = reader.nextInt();
reader.close();
ExecutorService executorPool = Executors.newFixedThreadPool(NOOFTHREADS);
AtomicInteger currentPrime = new AtomicInteger();
Runnable producer = () -> {
String threadName = Thread.currentThread().getName();
int p = 0;
try {
p = generateNextPrime(currentPrime.incrementAndGet());
linkedBlockingQueue.put(p);
primesproduced.put(p, threadName);
System.out.println("Thread " + threadName + " produced prime number " + p);
} catch (InterruptedException e) {
e.printStackTrace();
}
};
List<Runnable> tasks = new ArrayList<Runnable>();
for (int i = 0; i < NOOFTHREADS; i++) {
tasks.add(producer);
}
CompletableFuture<?>[] futures = tasks.stream().map(task -> CompletableFuture.runAsync(task, executorPool))
.toArray(CompletableFuture[]::new);
CompletableFuture.allOf(futures).join();
executorPool.shutdown();
System.out.println("\nTotal unique primes produced: " + primesproduced.size() + " and they are: ");
System.out.print(
primesproduced.entrySet().stream().filter(map -> map.getKey().intValue()>0).map(k -> "[" + k + "]").collect(Collectors.joining(",")));
}
}
private static int generateNextPrime(int currentPrime) {
currentPrime++;
if (currentPrime < 2) {
currentPrime = 2;
return currentPrime;
}
for (int i = 2; i < currentPrime; i++) {
if (currentPrime % i == 0) {
currentPrime++;
i = 2;
} else {
continue;
}
}
return currentPrime;
}
}
Currently multiple producers can generate the same prime value.
How can I ensure that each producer generates a new prime value not generated previously by other producers?
Thanks for any help.
答案1
得分: 0
你需要采取不同的策略。你目前的策略是让线程从 currentPrime + 1 开始搜索素数。由于每个线程都在做相同的事情，这意味着它们将在重叠的素数范围内进行搜索。这是低效的（重复工作），并且会导致两个或多个线程偶尔发现相同的素数。
一个更好的策略是确保每个线程搜索不同的范围。例如，
value = atomicInt.addAndGet(1000);
将 1000 添加到 atomicInt 并在成功添加之前立即将 value 设置为 atomicInt 的值。因此，你可以将 value 视为分配给当前线程用于搜索的包含 1000 个整数的范围的起始值。
另一个提示：如果你想要更好的性能，可以查看埃拉托斯特尼筛法（Sieve of Eratosthenes）。
我猜你正在将这作为一项作业或学习练习进行，所以我不会为你编写代码。
英文翻译
You need a different strategy. Your current strategy is for threads to start searching for a prime at currentPrime + 1. Since each thread is doing the same thing, which means that they will be searching overlapping regions to primes. This is inefficient (duplicated work), and leads to two or threads occasionally discovering the same prime.
A better strategy is to make sure that each thread searches a different range. For example
value = atomicInt.addAndGet(1000);
adds 1000 to atomicInt and sets value to the value of atomicInt immediately prior to the successful add. So you could view value as the start of a range of 1000 integers that are assigned to the current thread for searching.
Another hint: look at the Sieve of Eratosthenes if you want better performance.
I am guessing that you are doing this as a homework or learning exercise, so I won't code it for you.
专注分享java语言的经验与见解，让所有开发者获益！
评论