现有C语言数组交集计算代码可优化吗？为何Matlab intersect性能更高？

1 该代码存在极大的优化空间 #

你当前的实现是暴力三重循环逻辑，最坏时间复杂度为O(len1×len2 + min(len1,len2)²)，数组长度稍大性能就会暴跌，完全不是最优实现。
除此之外原代码还有两处冗余开销：

• 当array1的某个元素在array2中重复出现时，会重复执行tmp数组的去重检查逻辑
• 额外申请了size大小的tmp数组，内存分配本身也会引入固定耗时

常见的两种更优实现思路：

• 排序+双指针法：先对两个数组分别排序，再用双指针遍历求交，同时跳过重复元素，时间复杂度为O(len1 log len1 + len2 log len2)，如果允许修改输入数组可以做到O(1)额外空间，完全不需要内存分配。示例实现如下：

// 排序辅助函数
int cmp_int(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int intersection_opt(int* array1, int* array2, int len1, int len2) {
    qsort(array1, len1, sizeof(int), cmp_int);
    qsort(array2, len2, sizeof(int), cmp_int);
    int i = 0, j = 0, count = 0;
    int last_val;
    int has_val = 0;
    while (i < len1 && j < len2) {
        if (array1[i] == array2[j]) {
            // 去重逻辑
            if (!has_val || array1[i] != last_val) {
                count++;
                last_val = array1[i];
                has_val = 1;
            }
            // 跳过两个数组中当前值的所有重复项
            int cur = array1[i];
            while (i < len1 && array1[i] == cur) i++;
            while (j < len2 && array2[j] == cur) j++;
        } else if (array1[i] < array2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return count;
}

• 哈希表法：先将较短数组的元素存入哈希集合去重，再遍历较长数组匹配元素，同时维护结果去重，时间复杂度为O(len1 + len2)，空间复杂度O(min(len1, len2))，适合内存充足的场景。

2 你之前的判断确实存在错误 #

首先内层break只是减少了单次匹配后的循环次数，属于常数级优化，完全没有改变暴力算法的时间复杂度量级，性能上限非常低，远达不到无法优化的程度。
其次所谓临界区无法并行的判断也不成立：完全可以先对两个数组分别做去重处理，这一步可完全并行执行，再对两个无重复数组求交集，不需要在遍历过程中加锁处理临界区，并行提升空间很大。

3 Matlab的intersect速度快的核心原因 #

• 算法层面：Matlab的intersect内置函数默认使用优化后的排序+双指针或者哈希表方案，时间复杂度比你的暴力实现低了一个量级，数组长度越大性能差距越明显。
• 编译优化：Matlab的内置函数底层都是经过LLVM高度优化编译的本地代码，做了大量的向量化、CPU指令集适配优化，比普通手写未优化的C代码性能高是正常情况。
• 场景适配：Matlab对短数组、重复元素多的数组等特殊场景都做了针对性的分支优化，进一步提升了平均运行效率。

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