【昕宝爸爸小模块】深入浅出之并发并行
??博客首页???????https://blog.csdn.net/Java_Yangxiaoyuan
???????欢迎优秀的你👍点赞、🗂?收藏、加??关注哦。
???????本文章CSDN首发，欢迎转载，要注明出处哦！
???????先感谢优秀的你能认真的看完本文，有问题欢迎评论区交流，都会认真回复！
深入浅出之并发并行的概念
一、?典型解析
并发(Concurrent) ，在操作系统中，是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行。
那么，操作系统是如何实现这种并发的呢?
现在我们用到操作系统，无论是Windows、Linux还是MacOS等，其实都是多用户多任务分时操作系统。使用这些操作系统的用户是可以 “同时” 干多件事的。
但是实际上，对于单CPU的计算机来说，在CPU中，同一时间是只能干一件事儿的。为了看起来像是 "同时干多件事” ，分时操作系统是把CPU的时间划分成长短基本相同的时间区间,即 ”时间片” ，通过操作系统的管理，把这些时间片依次轮流地分配给各个用户使用。
如果某个作业在时间片结束之前，整个任务还没有完成，那么该作业就被暂停下来，放弃CPU，等待下一轮循环再继续做。此时CPU又分配给另一个作业去使用。
由于计算机的处理速度很快，只要时间片的间隔取得适当，那么一个用户作业从用完分配给它的一个时间片到获得下一个CPU时间片，中间有所 ”停顿” ，但用户察觉不出来,好像整个系统全由它”独占“ 似的。
所以，在单CPU的计算机中，我们看起来“同时干多件事”，其实是通过CPU时间片技术，并发完成的。
提到并发，还有另外一个词容易和他混淆，那就是并行。
2.1 ?并发与并行之间的关系
并行(Parallel)，当系统有一个以上CPU时，当一个CPU执行一个进程时，另一个CPU可以执行另个进程，两个进程互不抢占CPU资源，可以同时进行，这种方式我们称之为 并行(Parallel) 。
Erlang 之父 Joe Armstrong 用 张比较形象的图解释了并发与并行的区别：
并发是两个队伍交替使用一台咖啡机。并行是两个队伍同时使用两台咖啡机。
映射到计算机系统中，上图中的咖啡机就是CPU，两个队伍指的就是两个进程。
二、?拓展知识仓
2.1 ?并发和并行之间的区别
并发和并行是计算机科学和编程中的两个重要概念，它们都涉及到同时处理多个任务或操作，但有不同的含义和实现方式。
并发（Concurrent）是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。并发是逻辑上的同时发生，而并行是物理上的同时发生。并发可以在单处理器和多处理器系统中都存在，而并行只存在于多处理器系统中。并发要求程序假装同时执行多个操作，而并行要求程序能够同时执行多个操作。
并行（Parallel）是指多个处理器或者是多核的处理器同时处理多个不同的任务。并行是指多个事件在同一时刻发生。并行可以提高系统性能和响应速度，因为多个任务可以同时得到处理。
并发和并行都是处理多个任务或操作的方式，但并发更侧重于时间上的重叠和顺序执行，而并行更侧重于同时执行和独立异步性。并发和并行在现代计算机系统中都有广泛的应用，可以提高系统性能和响应速度。
2.1.1 ?常见的例子
并发和并行的例子如下：
- 并发：一个学生同时做多个任务，如一边听音乐一边写作业。
- 并行：多个学生同时做多个任务，如多个学生同时进行考试。
- 并发：一个线程同时检查多个网络连接，检查是否有新的数据包到来。
- 并行：多个线程同时处理多个网络连接，每个线程处理一个网络连接。
- 并发：一个程序同时处理多个用户请求，如Web服务器同时处理多个HTTP请求。
- 并行：多个程序同时处理多个用户请求，如多个Web服务器同时处理多个HTTP请求。
并发和并行都是处理多个任务或操作的方式，但并发更侧重于时间上的重叠和顺序执行，而并行更侧重于同时执行和独立异步性。在实际应用中，根据不同的需求和场景选择适合的方式可以提高系统性能和响应速度。
2.1.2 ?并发的应用场景
并发在许多应用场景中都发挥着重要的作用，以下是常见的并发应用场景：
- 多任务处理：并发编程可以同时处理多个任务，如并发网络服务器等。
- 大规模数据处理：并发编程可以实现同时处理多个数据的目的，如MapReduce框架就是一种典型的大规模数据并发处理方式。
- 并发数据结构：并发编程可以实现同时访问某些数据结构，如并发队列和并发集合。
- 实时系统：在实时系统中，任务需要在特定时间内完成，并发编程可以帮助处理多个实时任务。
- 游戏和仿真：游戏和仿真中经常需要同时处理多个事件，如并发游戏实体移动和碰撞检测。
- 数据库系统：数据库系统中的并发控制用于管理多个用户对数据库的并发访问。
- Web应用程序：Web应用程序需要同时处理大量用户的请求，并发编程可以帮助提高Web应用程序的性能和响应速度。
- 图形渲染：图形渲染需要大量的计算和数据处理，并发编程可以提高渲染速度和质量。
- 分布式系统：在分布式系统中，多个节点需要协同工作，并发编程可以帮助协调这些节点的任务和处理。
- 流处理：在流处理中，数据流经一系列转换操作，并发编程可以同时处理多个数据流。
2.2 ?如何实现并发和并行
实现并发和并行的方法有很多，下面介绍一些常见的实现方式：
- 多线程编程：多线程编程是实现并发和并行的一种常见方式。通过创建多个线程，可以让它们同时执行不同的任务或操作，从而实现并发和并行。在Java、Python等语言中，可以使用内置的线程库或框架来实现多线程编程。
- 异步编程：异步编程是一种实现并发和并行的有效方式。通过异步编程，可以让一个任务在等待I/O操作或其他阻塞操作时执行其他任务，从而提高程序的效率和响应速度。在JavaScript、Python等语言中，可以使用异步函数或协程来实现异步编程。
- 并行计算：并行计算是实现大规模数据处理和计算的常用方式。通过将一个任务拆分成多个子任务，然后将子任务分配给多个处理器或核心进行计算，可以实现大规模数据的并行处理和计算。常见的并行计算框架包括Hadoop、Spark等。
- 事件驱动编程：事件驱动编程也是一种实现并发和并行的方式。通过事件触发和回调机制，可以让程序在等待事件发生时执行其他任务或操作。在JavaScript、Python等语言中，可以使用事件驱动编程框架来实现并发和并行。
- 分布式计算：分布式计算是实现大规模并行处理和计算的常用方式。通过将一个任务拆分成多个子任务，然后将子任务分配给多个节点进行计算和处理，可以实现大规模数据的分布式处理和计算。常见的分布式计算框架包括Hadoop、Spark等。
看一个模拟场景的Demo：
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
/**
* @author xinbaobaba
* 场景: 并发和并行业务示例，模拟了一个在线购物网站的系统架构
*/
public class ComplexBusinessExample {
public static void main(String[] args) {
// 创建线程池
ExecutorService executor = Executors.newFixedThreadPool(10);
// 提交用户请求任务
executor.submit(() -> {
System.out.println("User request task started.");
// 处理用户请求，包括获取商品信息、验证用户身份等操作
// ...
System.out.println("User request task completed.");
});
// 提交库存更新任务
executor.submit(() -> {
System.out.println("Inventory update task started.");
// 更新库存信息，包括检查库存数量、更新商品状态等操作
// ...
System.out.println("Inventory update task completed.");
});
// 提交订单生成任务
executor.submit(() -> {
System.out.println("Order generation task started.");
// 生成订单，包括计算订单金额、生成订单号等操作
// ...
System.out.println("Order generation task completed.");
});
// 等待所有任务完成
executor.shutdown();
try {
if (!executor.awaitTermination(60, TimeUnit.SECONDS)) {
executor.shutdownNow(); // 非正常关闭线程池
}
} catch (InterruptedException e) {
executor.shutdownNow(); // 非正常关闭线程池
}
}
}
可以看到：创建了一个固定大小的线程池来处理多个任务。首先，我们提交了一个用户请求任务，用于处理用户的购物请求，包括获取商品信息、验证用户身份等操作。然后，我们提交了一个库存更新任务，用于更新库存信息，包括检查库存数量、更新商品状态等操作。接下来，我们提交了一个订单生成任务，用于生成订单，包括计算订单金额、生成订单号等操作。最后，我们通过调用
executor.shutdown()方法等待所有任务完成。在每个任务中，我们简单地模拟了业务处理时间，并通过输出语句展示了业务逻辑。通过这种方式，我们可以将复杂的业务逻辑与并发和并行处理结合起来，实现高效的多任务处理。
2.3 ?并行算法都有哪些
并行算法是一类适用于并行计算机的算法，可以分为数值并行算法和非数值并行算法。根据进程之间的依赖关系，并行算法可以分为同步并行算法和异步并行算法。常见的并行算法包括：
- 并行排序算法：如快速排序、归并排序等。
- 并行图算法：如深度优先搜索、广度优先搜索等。
- 并行计算模型：如MapReduce、Dryad等。
- 并行机器学习算法：如随机梯度下降、小批量梯度下降等。
- 并行决策树算法：如CART、ID3等。
三、 ?数值并行算法和非数值并行算法，他们之间有什么区别
数值并行算法和非数值并行算法在处理方式和应用场景上存在一些区别。
数值并行算法主要针对需要进行数值计算的问题，如物理模拟、科学计算等。这类问题通常涉及到大规模的数值计算和迭代，如矩阵乘法、线性方程组求解等。数值并行算法的核心是通过将问题分解成多个子问题，并利用并行计算资源同时解决这些子问题，以提高整体计算效率。
非数值并行算法则更广泛地应用于各类问题，如字符串匹配、模式识别、图算法等。这类问题通常涉及到逻辑运算和数据处理，如排序、搜索、决策树等。非数值并行算法通常通过将问题分解成多个独立的子任务，并利用并行计算资源同时处理这些子任务，以提高整体处理速度。
数值并行算法和非数值并行算法的主要区别在于处理方式和应用场景的不同。数值并行算法更注重于大规模数值计算和迭代，而非数值并行算法则更注重于逻辑运算和数据处理。在实际应用中，需要根据具体的问题和需求选择适合的并行算法。
3.1 ?并行矩阵乘法
并行矩阵乘法是一种数值并行算法，用于加速矩阵乘法的计算过程。该算法将一个大矩阵分成多个小矩阵，并利用多个处理器同时进行计算，以提高整体计算速度。
并行矩阵乘法可以分为以下几个步骤：
- 分块：将一个大矩阵分成多个小矩阵，每个小矩阵的大小可以根据实际情况进行调整。
- 分配任务：将分好的小矩阵分配给多个处理器进行计算。每个处理器计算一个小矩阵，并利用并行计算资源进行计算。
- 合并结果：最后将各个处理器计算得到的结果合并起来，得到最终的矩阵乘法结果。
在实现并行矩阵乘法时，需要注意以下几个问题：
1. 数据通信开销：在并行计算中，各个处理器之间的数据通信开销是一个重要的问题。为了避免过大的通信开销，可以采用压缩技术、分布式存储技术等手段来降低通信开销。
2. 负载均衡：在并行计算中，各个处理器的工作量可能不均衡，导致一些处理器空闲而其他处理器还在忙碌。为了实现负载均衡，可以采用动态任务调度、资源管理等手段来优化处理器之间的任务分配。
3. 精度问题：在并行计算中，由于各个处理器之间的计算环境可能存在差异，可能会导致计算结果的精度问题。为了解决精度问题，可以采用误差检测和修正等技术来保证计算结果的精度。
并行矩阵乘法是一种通过将大矩阵分解成小矩阵并利用并行计算资源进行加速的数值并行算法。在实际应用中，需要根据具体的问题和需求选择适合的并行算法和实现方式。
Demo:
/**
* @author xinbaobaba
* 使用多线程实现并行矩阵乘法
*/
public class ParallelMatrixMultiplication {
private static final int NUM_THREADS = 4; // 线程数
private static final int MATRIX_SIZE = 1000; // 矩阵大小
public static void main(String[] args) {
// 创建两个矩阵
double[][] A = new double[MATRIX_SIZE][MATRIX_SIZE];
double[][] B = new double[MATRIX_SIZE][MATRIX_SIZE];
for (int i = 0; i < MATRIX_SIZE; i++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
A[i][j] = i + j;
B[i][j] = i * j;
}
}
// 计算矩阵乘积的结果
double[][] C = new double[MATRIX_SIZE][MATRIX_SIZE];
for (int i = 0; i < MATRIX_SIZE; i++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
C[i][j] = 0;
}
}
// 使用多线程进行矩阵乘法的计算
ExecutorService executor = Executors.newFixedThreadPool(NUM_THREADS);
for (int i = 0; i < MATRIX_SIZE; i += NUM_THREADS) {
int end = Math.min(i + NUM_THREADS, MATRIX_SIZE);
executor.execute(new MatrixMultiplicationTask(A, B, C, i, end));
}
executor.shutdown(); // 关闭线程池
// 输出结果矩阵的每个元素
for (int i = 0; i < MATRIX_SIZE; i++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
System.out.print(C[i][j] + " ");
}
System.out.println();
}
}
}
class MatrixMultiplicationTask implements Runnable {
private double[][] A; // 矩阵A
private double[][] B; // 矩阵B
private double[][] C; // 结果矩阵C
private int start; // 当前计算的起始下标
private int end; // 当前计算的结束下标
public MatrixMultiplicationTask(double[][] A, double[][] B, double[][] C, int start, int end) {
this.A = A;
this.B = B;
this.C = C;
this.start = start;
this.end = end;
}
@Override
public void run() {
for (int i = start; i < end; i++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
C[i][j] += A[i][j] * B[i][j]; // 计算矩阵乘积的每个元素
}
}
}
}
示例中：首先创建了两个矩阵A和B，并填充了一些随机值。然后，我们创建了一个结果矩阵C，用于存储矩阵乘积的结果。接下来，我们使用
ExecutorService创建了一个固定大小的线程池，用于执行矩阵乘法的计算任务。在主线程中，我们将矩阵乘法的计算任务分解成多个子任务，每个子任务负责计算一部分矩阵乘积的结果。然后，我们将这些子任务提交给线程池进行并行计算。最后，我们关闭线程池并输出结果矩阵的每个元素。在MatrixMultiplicationTask类中，我们实现了Runnable接口，定义了矩阵乘法的计算任务。在run()方法中，我们使用两个嵌套的循环遍历矩阵A和B的对应元素，并计算矩阵乘积的每个元素。最后，我们将计算得到的结果存储到结果矩阵C中。
3.2 ?并行数值积分
并行数值积分是一种数值并行算法，用于加速数值积分的计算过程。该算法将积分区间分成多个子区间，并利用多个处理器同时进行积分计算，以提高整体计算速度。
具体来说，并行数值积分可以分为以下几个步骤：
1. 分区：将积分区间分成多个子区间，每个子区间的长度可以根据实际情况进行调整。
2. 分配任务：将分好的子区间分配给多个处理器进行计算。每个处理器计算一个子区间的积分值，并利用并行计算资源进行计算。
3. 合并结果：最后将各个处理器计算得到的结果合并起来，得到最终的数值积分结果。
在实现并行数值积分时，需要注意以下几个问题：
1. 数据通信开销：在并行计算中，各个处理器之间的数据通信开销是一个重要的问题。为了避免过大的通信开销，可以采用压缩技术、分布式存储技术等手段来降低通信开销。
2. 负载均衡：在并行计算中，各个处理器的工作量可能不均衡，导致一些处理器空闲而其他处理器还在忙碌。为了实现负载均衡，可以采用动态任务调度、资源管理等手段来优化处理器之间的任务分配。
3. 精度问题：在并行计算中，由于各个处理器之间的计算环境可能存在差异，可能会导致计算结果的精度问题。为了解决精度问题，可以采用误差检测和修正等技术来保证计算结果的精度。
并行数值积分是一种通过将积分区间分解成子区间并利用并行计算资源进行加速的数值并行算法。在实际应用中，需要根据具体的问题和需求选择适合的并行算法和实现方式。
Demo：
/**
* @author xinbaobaba
* 使用多线程实现并行数值积分
*/
public class ParallelNumericalIntegration {
private static final int NUM_THREADS = 4; // 线程数
private static final double INTEGRATION_RANGE = 1.0; // 积分区间
private static final double FUNCTION_VALUE = 2.0; // 被积函数值
public static void main(String[] args) {
// 定义被积函数
Function<Double, Double> function = x -> FUNCTION_VALUE;
// 计算积分结果
double result = parallelIntegrate(function, INTEGRATION_RANGE, NUM_THREADS);
System.out.println("Integral value: " + result);
}
public static double parallelIntegrate(Function<Double, Double> function, double integrationRange, int numThreads) {
// 将积分区间分成多个子区间
double subRange = integrationRange / numThreads;
// 创建并初始化累加器数组
double[] accumulators = new double[numThreads];
for (int i = 0; i < numThreads; i++) {
accumulators[i] = 0;
}
// 使用多线程进行积分计算
ExecutorService executor = Executors.newFixedThreadPool(numThreads);
for (int i = 0; i < numThreads; i++) {
int start = (int) (i * subRange);
int end = (int) (start + subRange);
executor.execute(() -> {
for (double x = start; x < end; x += 0.01) { // 假设被积函数在每个子区间内是常数函数
accumulators[i] += function.apply(x); // 计算子区间的积分值，并累加到累加器数组中对应位置的值上
}
});
}
executor.shutdown(); // 关闭线程池
// 等待所有线程执行完毕，并返回最终的积分结果
double integral = 0;
for (double accumulator : accumulators) {
integral += accumulator; // 将累加器数组中的值相加得到最终的积分结果
}
return integral;
}
}
代码解析：首先定义了一个被积函数，该函数返回一个常数值。然后，我们使用多线程实现了并行数值积分。具体来说，我们将积分区间分成多个子区间，并使用ExecutorService创建了一个固定大小的线程池。每个线程负责计算一个子区间的积分值，并将计算结果累加到累加器数组中对应位置的值上。最后，我们将累加器数组中的值相加得到最终的积分结果。在并行计算中，我们需要注意数据通信开销、负载均衡和精度问题等问题。在实际应用中，需要根据具体的问题和需求选择适合的并行算法和实现方式。
3.3 ? 并行字符串匹配
并行字符串匹配是一种利用并行计算加速字符串匹配的方法。下面是一个简单的并行字符串匹配算法的步骤：
-
将目标字符串（也称为模式字符串）拆分成多个子字符串。这些子字符串应该具有相同的长度，以便能够并行处理。
-
将目标字符串的每个子字符串分配给一个处理器（线程或进程）进行处理。
-
每个处理器使用传统的串行字符串匹配算法（如KMP算法、Boyer-Moore算法等）来查找其分配到的子字符串在目标字符串中的出现位置。
-
处理器将找到的所有出现位置报告给主程序。
-
主程序将所有处理器报告的位置合并，并去除重复的位置，得到最终的匹配结果。
该算法的优点是可以利用多核处理器或多线程环境来加速字符串匹配过程。然而，它也有一些限制和挑战，例如如何选择合适的子字符串长度以最大化并行度，如何处理处理器之间的通信开销等。
Demo：
/**
* @author xinbaobaba
* 使用多线程实现并行字符串匹配
*/
public class ParallelStringMatcher {
private static final int NUM_THREADS = 4; // 线程数
private static final String TEXT = "abcdefghijklmnopqrstuvwxyz"; // 目标字符串
private static final String PATTERN = "abc"; // 模式字符串
public static void main(String[] args) {
// 将模式字符串拆分成多个子字符串
String[] substrings = splitSubstrings(PATTERN);
// 创建并初始化结果数组
int[] matches = new int[NUM_THREADS];
// 使用多线程进行匹配计算
ExecutorService executor = Executors.newFixedThreadPool(NUM_THREADS);
for (int i = 0; i < NUM_THREADS; i++) {
final int index = i;
executor.execute(() -> {
int start = index * substrings[index].length(); // 计算当前线程负责的子字符串在目标字符串中的起始位置
int end = start + substrings[index].length(); // 计算当前线程负责的子字符串在目标字符串中的结束位置
for (int j = start; j < end; j++) { // 在当前线程负责的子字符串范围内进行串行匹配计算
if (TEXT.startsWith(substrings[index], j)) {
matches[index] = j; // 将匹配位置记录到结果数组中对应位置的值上
break; // 找到一个匹配位置后，无需继续匹配剩余字符，直接跳出循环
}
}
});
}
executor.shutdown(); // 关闭线程池
// 等待所有线程执行完毕，并输出最终的匹配结果
for (int match : matches) {
System.out.println("Match found at position: " + match);
}
}
private static String[] splitSubstrings(String pattern) {
String[] substrings = new String[pattern.length()];
for (int i = 0; i < pattern.length(); i++) {
substrings[i] = pattern.substring(i, i + 1); // 将模式字符串拆分成单个字符组成的子字符串
}
return substrings;
}
}
代码解析：首先将模式字符串拆分成多个子字符串，并将每个子字符串分配给一个线程进行处理。每个线程使用传统的串行字符串匹配算法（在本例中为startsWith方法）在目标字符串的指定范围内进行匹配计算，并将找到的匹配位置记录到结果数组中对应位置的值上。最后，我们将结果数组中的值输出即可得到最终的匹配结果。
3.4 ? 并行图算法
并行图算法是一种利用并行计算技术来加速图算法执行的方法。由于图算法通常具有较高的计算复杂度，因此在处理大规模图数据时，串行算法的执行时间较长。通过将图算法并行化，可以将计算任务分配给多个处理器核心或计算机节点，从而加快计算速度。
并行图算法的基本思想是将图划分为多个子图，并在多个处理器上并行执行计算任务。这些子图可以是图的顶点、边或子图，具体取决于算法的要求。在每个处理器上，算法执行一部分计算任务，并与其他处理器进行通信以共享信息。
并行图算法的一般流程包括数据划分、任务分配、结果合并等步骤。首先，需要将原始图数据划分为多个子图，以便分配给不同的处理器进行处理。然后，根据算法的要求，每个处理器执行相应的计算任务。在计算过程中，处理器之间需要进行通信以共享信息。最后，将各个处理器计算的结果进行合并，得到最终的输出。
并行图算法的应用场景非常广泛，包括社交网络分析、推荐系统、生物信息学等领域。例如，在社交网络分析中，可以使用并行图算法对用户关系进行挖掘和分析，从而发现潜在的用户群体或社交圈子。在推荐系统中，可以使用并行图算法对用户的行为进行分析和预测，从而为用户提供个性化的推荐服务。
实现并行图算法需要利用并行编程技术，如多线程、进程间通信、数据分区等。同时，还需要注意算法的正确性和效率问题，以确保并行化后的算法能够正确地处理大规模图数据，并具有较好的性能表现。
Demo：
import java.util.LinkedList;
import java.util.Queue;
/**
* @author xinbaobaba
* 实现并行图算法中的广度优先搜索（BFS）算法
*/
public class ParallelBFS {
private static final int NUM_THREADS = 4; // 线程数
private static final int V = 6; // 顶点数
public static void main(String[] args) {
// 创建邻接矩阵表示的图
int[][] graph = {
{0, 1, 1, 0, 0, 0},
{1, 0, 1, 1, 1, 0},
{1, 1, 0, 0, 1, 1},
{0, 1, 0, 0, 1, 0},
{0, 1, 1, 1, 0, 1},
{0, 0, 1, 0, 1, 0}
};
// 将图划分为多个子图，每个子图由一个线程处理
int[][][] subGraphs = new int[NUM_THREADS][V][V];
for (int i = 0; i < V; i++) {
int threadId = i % NUM_THREADS;
for (int j = 0; j < V; j++) {
subGraphs[threadId][i % V][j % V] = graph[i][j];
}
}
// 使用多线程并行执行BFS算法
Queue<Integer>[] bfsQueues = new LinkedList[NUM_THREADS];
for (int i = 0; i < NUM_THREADS; i++) {
bfsQueues[i] = new LinkedList<>();
}
bfsQueues[0].add(0); // 从顶点0开始搜索
boolean[] visited = new boolean[V]; // 记录顶点是否被访问过
while (!bfsQueues[0].isEmpty()) {
int currentVertex = bfsQueues[0].poll(); // 出队一个顶点
visited[currentVertex] = true; // 将该顶点标记为已访问
System.out.print(currentVertex + " "); // 输出访问过的顶点编号
for (int neighbor = 0; neighbor < V; neighbor++) {
if (subGraphs[0][currentVertex][neighbor] == 1 && !visited[neighbor]) {
bfsQueues[neighbor % NUM_THREADS].add(neighbor); // 将邻居顶点加入相应线程的队列中
}
}
}
}
}
代码解析：首先创建了一个邻接矩阵表示的图，并将其划分为多个子图，每个子图由一个线程处理。然后，我们使用多线程并行执行BFS算法。在每个线程中，我们使用一个队列来存储待访问的顶点，并使用一个布尔数组来记录顶点是否被访问过。我们从顶点0开始搜索，并将它加入到第一个线程的队列中。然后，在主线程中循环处理队列中的顶点，将已访问的顶点输出，并将未访问的邻居顶点加入相应线程的队列中。通过这种方式，我们可以并行地执行BFS算法，加快计算速度。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- SCAU:18054 输出不同的数
- RHCE9学习指南 第9章 权限管理
- 【Angular教程240104】01 目录结构分析 创建组件 声明属性的方式、ts定义属性、绑定数据、绑定属性0
- java swing 药品销售系统 mysql
- GaussianEditor：通过用户指令编辑 GS 三维场景
- HTTP相关
- 一篇文章带你搞懂---全排序
- 读书笔记-《数据结构与算法》-摘要8[桶排序]
- pytorch 多卡训练 accelerate gloo
- 【排序】对各种排序的总结