java – 使用多线程的Sudoku解算器
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – 使用多线程的Sudoku解算器,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3990字,纯文字阅读大概需要6分钟。
内容图文
![java – 使用多线程的Sudoku解算器](/upload/InfoBanner/zyjiaocheng/728/a0fd7c77e5d34bf0a3dcb50837a07e0d.jpg)
我已经使用回溯实现了一个数独求解器,但我遇到了性能问题,主要问题是isAvailable()函数检查该数字是否对当前位置有效.不使用线程的执行时间需要61ms:
protected boolean flag;
public boolean isAvailable(int sudoku[][], int row, int col, int num){
flag = true;
int rowStart = (row / 3) * 3;
int colStart = (col / 3) * 3;
for (int i = 0; i < 9; ++i) {
if (sudoku[row][i] == num) {
flag = false;
}
}
for (int i = 0; i < 9; ++i) {
if (sudoku[i][col] == num) {
flag = false;
}
}
for (int i = rowStart; i < (rowStart + 3); ++i) {
for (int j = colStart; j < (colStart + 3); ++j) {
if (sudoku[i][j] == num)
flag = false;
}
}
return flag;
}
结果:
Answer found
Time elapsed = 61.63ms
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
但是,如果我使用不同的线程,一个用于检查另一个用于检查列,另一个用于检查列,我希望执行时间更短,但需要大约312秒
protected boolean flag;
public boolean isAvailable(int sudoku[][], int row, int col, int num) throws InterruptedException {
flag = true;
int rowStart = (row / 3) * 3;
int colStart = (col / 3) * 3;
Thread t1 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i < 9; ++i) {
if (sudoku[row][i] == num) {
flag = false;
}
}
}
});
t1.start();
Thread t2 = new Thread(new Runnable() {
public void run() {
for (int i = 0; i < 9; ++i) {
if (sudoku[i][col] == num) {
flag = false;
}
}
}
});
t2.start();
Thread t3 = new Thread(new Runnable() {
public void run() {
for (int i = rowStart; i < (rowStart + 3); ++i) {
for (int j = colStart; j < (colStart + 3); ++j) {
if (sudoku[i][j] == num)
flag = false;
}
}
}
});
t3.start();
t1.join();
t2.join();
t3.join();
return flag;
}
结果:
Answer found
Time elapsed = 312514.63ms
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
如果您需要我的完整代码:
import java.text.DecimalFormat;
public class Main {
public static void main(String[] args){
int sudoku[][] = {{8, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 3, 6, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 9, 0, 2, 0, 0},
{0, 5, 0, 0, 0, 7, 0, 0, 0},
{0, 0, 0, 0, 4, 5, 7, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 3, 0},
{0, 0, 1, 0, 0, 0, 0, 6, 8},
{0, 0, 8, 5, 0, 0, 0, 1, 0},
{0, 9, 0, 0, 0, 0, 4, 0, 0}};
Main m = new Main();
long starttime = System.nanoTime();
boolean k = m.fillsudoku(sudoku, 0, 0);
long endtime = System.nanoTime();
DecimalFormat df = new DecimalFormat("#.##");
if (k) {
System.out.println("Answer found");
System.out.println("Time elapsed = " + df.format((double) (endtime - starttime) / 1000000) + "ms");
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(sudoku[i][j] + " ");
}
System.out.println();
}
} else {
System.out.println("Not found");
}
}
public boolean fillsudoku(int sudoku[][], int row, int col){
if(row < 9){
if(sudoku[row][col] != 0){
if(col < 8){
return fillsudoku(sudoku, row, col+1);
}
else if(row < 8){
return fillsudoku(sudoku, row+1, 0);
}
return true;
}
else{
for(int i=1;i<=9;i++){
if(isAvailable(sudoku, row, col, i)){ // <- checking function
sudoku[row][col] = i;
if(col == 8){
if(fillsudoku(sudoku, row+1, 0)){
return true;
}
}
else{
if(fillsudoku(sudoku, row, col+1)){
return true;
}
}
sudoku[row][col] = 0;
}
}
return false;
}
}
return true;
}
protected boolean flag;
public boolean isAvailable(int sudoku[][], int row, int col, int num){
........
........
}
}
我如何使用线程,任何建议来提高性能,我是否正确思考.
解决方法:
不幸的是,你不会从多线程中获得任何好处.
每次方法调用创建3个线程比连续运行3个简单循环更昂贵.
实际上,27个检查和重新分配迭代不值得并行化.
说到改进,我们可以通过使用ExecutorService的线程池重写该方法.我试了一下,结果如下:
54.25ms // your plain version
65397.06ms // your multithreading version
5500.82ms // ExecutorService version
我简单地将Thread变量转换为Runnable变量,将它们传递给ExecutorService#submit并调用Future#get:
Runnable r1 = () -> { ... };
// other Runnables
final Future<?> f1 = executorService.submit(r1);
// other Futures
try {
f1.get();
// other gets
} catch (ExecutionException e) { ... }
内容总结
以上是互联网集市为您收集整理的java – 使用多线程的Sudoku解算器全部内容,希望文章能够帮你解决java – 使用多线程的Sudoku解算器所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。