我正在尝试使用多个线程来解决N Queen问题。但是，它的单线程版本运行速度更快，或与多线程版本大致相同。
本质上，我使用所有线程共享的队列。它们从队列中弹出状态并展开它们，然后将它们添加到队列中。我试过使用线程数，但无济于事，在8之后，我添加的线程越多，性能下降。该算法是正确的，因为两个版本的输出相同。
有什么想法吗？
这里是代码：
public class Queens {
//Thread
static class Runner implements Runnable {
private BlockingQueue<Configuration> queue;
private final AtomicInteger total;
public Runner(BlockingQueue<Configuration> q, AtomicInteger total) {
this.queue = q;
this.total = total;
}
public void run() {
while(!queue.isEmpty()) {
Configuration currentConfiguration = null;
try {
currentConfiguration = queue.take();
}
catch(InterruptedException e) {
}
if(currentConfiguration.done()) {
//currentConfiguration.printConfiguration();
total.incrementAndGet();
System.out.println("Solution");
continue;
}
for(int i = 0; i < currentConfiguration.getSize(); i++) {
if(safe(currentConfiguration, i, currentConfiguration.getColumn())) {
Configuration childConfig = new Configuration(currentConfiguration.getColumn() + 1,
currentConfiguration.getBoard());
childConfig.place(i, currentConfiguration.getColumn());
queue.add(childConfig);
}
}
}
}
//Returns true if we can place a queen on that row and column.
private boolean safe(Configuration current, int row, int col) {
for (int i = 0; i < col; i++)
if (current.getBoard()[row][i] == 1)
return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (current.getBoard()[i][j] == 1)
return false;
for (int i = row, j = col; j >= 0 && i < current.getSize(); i++, j--)
if (current.getBoard()[i][j] == 1)
return false;
return true;
}
}
//Board configuration class.
static class Configuration {
private int column;
private int[][] board;
private int size;
public Configuration(int column, int[][] b) {
this.column = column;
this.board = new int[b.length][b.length];
this.size = b.length;
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
board[i][j] = b[i][j];
}
}
}
public int getSize() {
return size;
}
public int getColumn() {
return column;
}
public int[][] getBoard() {
return board;
}
public boolean done() {
if(column == size)
return true;
return false;
}
public void place(int row, int column) {
board[row][column] = 1;
}
//Method prints the current configuration.
public synchronized void printConfiguration() {
synchronized(Configuration.class) {
System.out.println(Thread.currentThread().getName());
for(int i = 0; i < size; i++) {
for(int j = 0; j < size; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
}
public static void main(String[] args) throws InterruptedException {
Configuration x = new Configuration(0, new int[13][13]);
int threads = 10;
AtomicInteger totalSolutions = new AtomicInteger(0);
List<Thread> mythreads = new ArrayList<Thread>();
BlockingQueue<Configuration> q = new LinkedBlockingDeque<>();
//Initially the board is empty
q.put(x);
long startTime = System.currentTimeMillis();
//Run 10 threads
for(int i = 0; i < threads; i++) {
Thread newthread = new Thread(new Runner(q, totalSolutions));
newthread.start();
mythreads.add(newthread);
}
for(Thread t : mythreads) {
try {
t.join();
}
catch(Exception e) {};
}
System.out.println(totalSolutions.get());
long endTime = System.currentTimeMillis();
System.out.println("Time: " + (endTime - startTime));
}
}
这对于评论来说太长了，因此我必须将其写为答案，对此表示歉意。
在运行方法中，我添加了以下内容：
System.out.println(Thread.currentThread().getName() + " taking " + currentConfiguration.toString() + " out of " + queue.size() + " elem");
运行单线程程序时，它看起来像这样：
Thread-0 taking jobs.DeleteMe$Configuration@279b9032 out of 925326 elem
Thread-0 taking jobs.DeleteMe$Configuration@15ced747 out of 925327 elem
Thread-0 taking jobs.DeleteMe$Configuration@42689f59 out of 925328 elem
Thread-0 taking jobs.DeleteMe$Configuration@29aeeda2 out of 925329 elem
运行10个线程时，日志看起来像：
Thread-6 taking jobs.DeleteMe$Configuration@2775c7e7 out of 39393 elem
Thread-7 taking jobs.DeleteMe$Configuration@4e0ae08b out of 39308 elem
Thread-6 taking jobs.DeleteMe$Configuration@5eb0ba9 out of 39404 elem
Thread-9 taking jobs.DeleteMe$Configuration@12321211 out of 39401 elem
Thread-0 taking jobs.DeleteMe$Configuration@13a07923 out of 39383 elem
Thread-9 taking jobs.DeleteMe$Configuration@442cf86a out of 39415 elem
Thread-0 taking jobs.DeleteMe$Configuration@49366e2a out of 39420 elem
Thread-8 taking jobs.DeleteMe$Configuration@1c4bcfa5 out of 39378 elem
所以似乎没有什么可以阻止多个线程工作。
由于您的代码密集使用一种资源，即内存。
所以我猜测原因是，当运行单个线程而不是多个线程时，可以更有效地使用内存缓存。这意味着单线程访问通常是已经在CPU高速缓存中的Configuration，而在运行多线程时则会丢失更多内容。
请参阅：Is multi-thread memory access faster than single threaded memory access?
在旁注中，采用最新添加的配置可能会比较有效，BlockingQueue采用第一个配置，使用LinkedBlockingDeque可能会更高效。
所以我尝试了具有10个线程的LinkedBlockingDeque，时间：3753有1个线程：时间：3352
（对我来说，它的速度是LinkedBlockingQueue的3倍）。
来源：
import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.atomic.AtomicInteger;
/**
*
* @author mladen
*/
public class DeleteMe {
//Thread
static class Runner implements Runnable {
private LinkedBlockingDeque<Configuration> queue;
private final AtomicInteger total;
public Runner(LinkedBlockingDeque<Configuration> q, AtomicInteger total) {
this.queue = q;
this.total = total;
}
public void run() {
while (!queue.isEmpty()) {
Configuration currentConfiguration = null;
//try {
currentConfiguration = queue.removeLast();
//System.out.println(Thread.currentThread().getName() + " taking " + currentConfiguration.toString() + " out of " + queue.size() + " elem");
// } catch (InterruptedException e) {
//
// }
if (currentConfiguration.done()) {
//currentConfiguration.printConfiguration();
total.incrementAndGet();
System.out.println("Solution");
continue;
}
for (int i = 0; i < currentConfiguration.getSize(); i++) {
if (safe(currentConfiguration, i, currentConfiguration.getColumn())) {
Configuration childConfig = new Configuration(currentConfiguration.getColumn() + 1,
currentConfiguration.getBoard());
childConfig.place(i, currentConfiguration.getColumn());
queue.add(childConfig);
}
}
}
}
//Returns true if we can place a queen on that row and column.
private boolean safe(Configuration current, int row, int col) {
for (int i = 0; i < col; i++) {
if (current.getBoard()[row][i] == 1) {
return false;
}
}
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (current.getBoard()[i][j] == 1) {
return false;
}
}
for (int i = row, j = col; j >= 0 && i < current.getSize(); i++, j--) {
if (current.getBoard()[i][j] == 1) {
return false;
}
}
return true;
}
}
//Board configuration class.
static class Configuration {
private int column;
private int[][] board;
private int size;
public Configuration(int column, int[][] b) {
this.column = column;
this.board = new int[b.length][b.length];
this.size = b.length;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
board[i][j] = b[i][j];
}
}
}
public int getSize() {
return size;
}
public int getColumn() {
return column;
}
public int[][] getBoard() {
return board;
}
public boolean done() {
if (column == size) {
return true;
}
return false;
}
public void place(int row, int column) {
board[row][column] = 1;
}
//Method prints the current configuration.
public synchronized void printConfiguration() {
synchronized (Configuration.class) {
System.out.println(Thread.currentThread().getName());
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
}
public static void main(String[] args) throws InterruptedException {
Configuration x = new Configuration(0, new int[13][13]);
int threads = 1;
AtomicInteger totalSolutions = new AtomicInteger(0);
List<Thread> mythreads = new ArrayList<Thread>();
LinkedBlockingDeque<Configuration> q = new LinkedBlockingDeque<>();
//Initially the board is empty
q.put(x);
long startTime = System.currentTimeMillis();
//Run 10 threads
for (int i = 0; i < threads; i++) {
Thread newthread = new Thread(new Runner(q, totalSolutions));
newthread.start();
mythreads.add(newthread);
}
for (Thread t : mythreads) {
try {
t.join();
} catch (Exception e) {
};
}
System.out.println(totalSolutions.get());
long endTime = System.currentTimeMillis();
System.out.println("Time: " + (endTime - startTime));
}
}