I'm trying to increase the performance of my N Queens Puzzle solution. I'd find some threads on SO already but they don't appear to help me to increase performance.
My best solution, however, is a strategy with a constant amount of working threads. I also tried to implement a solution with RecursiveTasks
. But it appears that the first solution overcomes all my other tries. I think that is because the computer receives too many Tasks and looks for completion of working tasks most of the time.
However, I'd come up with two solutions:
First, the slow one with an implementation of RecursiveTask
which needs 2449 ms for the calculation of N = 14:
public class DamenProblemFork extends RecursiveTask<Integer>{
private static final long serialVersionUID = -6502127276625965624L;
static int N = 14;
public static void main(String[] args) throws InterruptedException {
if (args.length == 1) {
N = Integer.parseInt(args[0]);
}
long start = System.currentTimeMillis();
DamenProblemFork dpf_root = new DamenProblemFork(0L, 0L, 0L, N - 1);
Integer result = dpf_root.fork().join();
System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
System.out.println("Result for " + N + ": " + result);
}
private long diagR;
private long diagL;
private long mid;
private int depth;
public DamenProblemFork(long diagR, long diagL, long mid, int depth) {
this.diagR = diagR;
this.diagL = diagL;
this.mid = mid;
this.depth = depth;
}
@Override
protected Integer compute() {
List<DamenProblemFork> ldpf = new ArrayList<>();
long valid = mid | diagL | diagR;
int resBuffer = 0;
for (int i = 0; i < N; i++) {
int pos = 1 << i;
if ((valid & pos) > 0) {
continue;
}
if (depth == 0) {
resBuffer++;
continue;
}
long n_mid = mid | pos;
long n_diagL = (diagL | pos) >> 1;
long n_diagR = (diagR | pos) << 1;
DamenProblemFork dpf = new DamenProblemFork(n_diagR, n_diagL, n_mid, depth - 1);
ldpf.add(dpf);
}
if(depth == 0) {
return resBuffer;
}
return ldpf.stream().parallel().map(d -> d.fork()).mapToInt(x -> x.join()).sum();
}
}
The next solution I'd come up with is with a dedicated thread pool with thread number equal to processor count. This, however, just needs 124ms for the calculation of 14:
public class DamenProblem {
static AtomicInteger result = new AtomicInteger(0);
static int N = 14;
public static void main(String[] args) throws InterruptedException {
if (args.length == 1) {
N = Integer.parseInt(args[0]);
}
int processors = Runtime.getRuntime().availableProcessors();
int availableProcessors = processors < N ? processors : N;
BlockingQueue<Runnable> workQueue = new ArrayBlockingQueue<>(N);
ThreadPoolExecutor tpe = new ThreadPoolExecutor(availableProcessors, availableProcessors, 100,
TimeUnit.MILLISECONDS, workQueue);
Semaphore sem = new Semaphore(0);
long start = System.currentTimeMillis();
if(N%2 == 0) {
for (int i = 0; i < N/2; i++) {
int pos = 1 << i;
tpe.execute(() -> {
int res = run(pos << 1, pos >> 1, pos, N - 2);
result.getAndAdd(res);
sem.release();
});
}
sem.acquire(N/2);
System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
System.out.println("Result for " + N + ": " + result.get()*2);
}
else {
for (int i = 0; i < N; i++) {
int pos = 1 << i;
tpe.execute(() -> {
int res = run(pos << 1, pos >> 1, pos, N - 2);
result.getAndAdd(res);
sem.release();
});
}
sem.acquire(N);
System.out.println("End time: " + (System.currentTimeMillis() - start) + " ms");
System.out.println("Result for " + N + ": " + result.get());
}
System.exit(0);
}
static int run(long diagR, long diagL, long mid, int depth) {
long valid = mid | diagL | diagR;
int resBuffer = 0;
for (int i = 0; i < N; i++) {
int pos = 1 << i;
if ((valid & pos) > 0) {
continue;
}
if (depth == 0) {
resBuffer++;
continue;
}
long n_mid = mid | pos;
long n_diagL = (diagL | pos) >> 1;
long n_diagR = (diagR | pos) << 1;
resBuffer += run(n_diagR, n_diagL, n_mid, depth - 1);
}
return resBuffer;
}
}
My CPU is an AMD ryzen 5 2600K with 12 cores.
Do you guys have an idea how to improve this code to make it even faster? I thought something of including symmetry. But does this work? I think using symmetry just increases performance if N is greater than the number of processors times two.
What do you think?
for (int i = 0; i < N / 2; i++) {
inmain
and then doubleresult
and run again withint i = Math.ceil(N / 2)
ifN
is uneven \$\endgroup\$ – Jonas Wilms Jun 14 '18 at 19:42