请求并行化Spilnuy方法并测算并行版本的加速比

一、修复并完成基础并行实现 #

你的现有代码仅声明了Task数组但未实际创建并行任务，也未等待任务完成并汇总结果。以下是补全后的完整并行版本代码：

using System.Diagnostics;
using System.Threading.Tasks;

const int totalSize = 20_000;
const int taskCount = 8;

var array1 = new int[totalSize];
var array2 = new int[totalSize];
var random = new Random();

// 填充数组
for (int i = 0; i < totalSize; i++)
{
    array1[i] = random.Next(2 * totalSize);
}
for (int i = 0; i < totalSize; i++)
{
    array2[i] = random.Next(2 * totalSize);
}

// 串行执行统计
var watch = new Stopwatch();
watch.Start();
int serialCount = Spilnuy((array1, array2, 0, totalSize));
watch.Stop();
var durationSerial = watch.Elapsed;
Console.WriteLine($"串行模式：公共元素数量为 {serialCount}，耗时 {durationSerial}");

// 并行执行统计
watch.Restart();
var tasks = new Task<int>[taskCount];
var taskSize = totalSize / taskCount;

for (int t = 0; t < taskCount; t++)
{
    int from = t * taskSize;
    // 处理最后一个任务可能的剩余元素（当totalSize不能被taskCount整除时）
    int to = t == taskCount - 1 ? totalSize : (t + 1) * taskSize;
    tasks[t] = Task.Run(() => Spilnuy((array1, array2, from, to)));
}

// 等待所有任务完成并汇总结果
Task.WaitAll(tasks);
int parallelCount = tasks.Sum(t => t.Result);
watch.Stop();
var durationParallel = watch.Elapsed;
Console.WriteLine($"并行模式：公共元素数量为 {parallelCount}，耗时 {durationParallel}");

// 计算加速比
double speedup = durationSerial.TotalMilliseconds / durationParallel.TotalMilliseconds;
Console.WriteLine($"加速比：{speedup:F2}x");

// 并行化的Spilnuy方法
int Spilnuy((int[] array1, int[] array2, int from, int to) param)
{
    int k = 0;
    for (int i = param.from; i < param.to; i++)
    {
        foreach (int v in param.array2)
        {
            if (param.array1[i] == v)
            {
                k++;
                break; // 找到匹配后跳出内层循环，避免重复计数（如果允许重复元素则去掉）
            }
        }
    }
    return k;
}

关键修改说明： #

• 修正了Spilnuy方法的参数类型，直接使用值元组避免object类型的装箱拆箱开销
• 实际创建并行任务，为每个任务分配array1的子区间
• 处理最后一个任务的边界情况，确保所有元素都被统计
• 等待所有任务完成后汇总结果，并计算加速比
• 内层循环添加break，避免同一元素在array2中多次匹配时重复计数（如果你的需求是统计元素出现次数的交集，则移除该break）

二、算法优化：用HashSet降低时间复杂度 #

原代码的双重循环时间复杂度为O(n²)，当数组规模较大时效率极低。可以先将array2存入HashSet，将查询时间降为O(1)，整体时间复杂度优化为O(n)：

using System.Collections.Generic;
using System.Diagnostics;
using System.Threading.Tasks;

const int totalSize = 20_000;
const int taskCount = 8;

var array1 = new int[totalSize];
var array2 = new int[totalSize];
var random = new Random();

// 填充数组
for (int i = 0; i < totalSize; i++)
{
    array1[i] = random.Next(2 * totalSize);
}
for (int i = 0; i < totalSize; i++)
{
    array2[i] = random.Next(2 * totalSize);
}

// 提前将array2转为HashSet，优化查询效率
var set2 = new HashSet<int>(array2);

// 串行执行统计
var watch = new Stopwatch();
watch.Start();
int serialCount = OptimizedSpilnuy((array1, set2, 0, totalSize));
watch.Stop();
var durationSerial = watch.Elapsed;
Console.WriteLine($"串行优化模式：公共元素数量为 {serialCount}，耗时 {durationSerial}");

// 并行执行统计
watch.Restart();
var tasks = new Task<int>[taskCount];
var taskSize = totalSize / taskCount;

for (int t = 0; t < taskCount; t++)
{
    int from = t * taskSize;
    int to = t == taskCount - 1 ? totalSize : (t + 1) * taskSize;
    tasks[t] = Task.Run(() => OptimizedSpilnuy((array1, set2, from, to)));
}

Task.WaitAll(tasks);
int parallelCount = tasks.Sum(t => t.Result);
watch.Stop();
var durationParallel = watch.Elapsed;
Console.WriteLine($"并行优化模式：公共元素数量为 {parallelCount}，耗时 {durationParallel}");

// 计算加速比
double speedup = durationSerial.TotalMilliseconds / durationParallel.TotalMilliseconds;
Console.WriteLine($"加速比：{speedup:F2}x");

// 优化后的统计方法
int OptimizedSpilnuy((int[] array1, HashSet<int> set2, int from, int to) param)
{
    int k = 0;
    for (int i = param.from; i < param.to; i++)
    {
        if (param.set2.Contains(param.array1[i]))
        {
            k++;
        }
    }
    return k;
}

优化说明： #

• 将array2转为HashSet<int>后，单次查询时间从O(n)降为O(1)，整体性能提升显著
• 并行逻辑与基础版本一致，但整体耗时会远低于原双重循环实现

三、加速比计算说明 #

加速比的核心计算公式为：

加速比 = 串行执行时间 / 并行执行时间

需要注意：

• 确保串行和并行统计的是相同的逻辑（比如是否统计重复元素），否则加速比无意义
• 并行时间统计需包含所有任务的执行时间（从任务创建到全部完成）
• 多次运行取平均值，避免单次运行的偶然误差影响结果

内容的提问来源于stack exchange，提问作者Boooeee