源代码中的什么导致了依赖于平台的结果

Question

我用 C 编写了合并排序算法，并在本地和远程编译了它。我假设源代码中的某些内容导致了平台依赖性。

#include <stdio.h>
#include <limits.h>
#include <math.h>

void merge(int A[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (int i = 0; i < n1; ++i) {
        L[i] = A[p + i];
    }

    for(int j = 0; j < n2; ++j) {
        R[j] = A[q + j + 1];
    }

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;

    int i = 0;
    int j = 0;

    for (int k = p; k <= r; ++k) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i = i + 1;
        } else {
            A[k] = R[j];
            j = j + 1;
        }
    }
}

void merge_recurse(int A[], int p, int r) {
    if (p < r) {
        int q = floor((p + r) / 2);
        merge_recurse(A, p, q);
        merge_recurse(A, q + 1, r);
        merge(A, p, q, r);
    }
}

void merge_sort(int A[], size_t length) {
    merge_recurse(A, 0, (int)length - 1);
}

int main() {
    int length = 9;
    int A[] = { 3, 7, 61, 3, 40, 4, -1, 8, 10 };

    merge_sort(A, length);

    for (int i = 0; i < length; ++i) {
        printf("%i, ", A[i]);
    }

    return 0;
}

编译后 online 返回正确的结果。

-1, 3, 3, 4, 7, 8, 10, 40, 61,

然而，当我在 Linux 上本地编译源代码时，返回的结果不正确。

-1, 4, 8, 10, 2147483647, 3, 7, 40, 61

源代码中的什么导致了这些不同的结果？

Answer 1

L[n1] = INT_MAX; 写入数组末尾。声明 int L[n1]; 创建一个可以从 0 到 n1-1 索引的数组。没有L[n1]。 R[n2] = INT_MAX;

同样的事情

当代码写入超过数组末尾时，它可能会以改变代码行为的方式踩踏另一个变量。或者它可能没有任何可观察到的效果。在线编译器恰好以一种没有发生任何坏事的方式在内存中安排变量。它是完全不可预测的，被称为 undefined behavior.

Answer 2

该代码具有未定义的行为：L[n1] = INT_MAX; 和 R[n2] = INT_MAX; 都超出了各自数组的末尾。

未定义的行为可能没有可见的影响，这是您在在线编译器上观察到的，或者产生您在 Linux 系统上看到的不正确的结果，或者产生灾难性的结果，例如程序崩溃或更糟.

请注意，您的实现使用了令人困惑的约定和不安全的方法：

传递 r 作为最后一个元素的索引在 C 语言中比使用下一个元素的索引更为惯用。使用这种替代约定，切片的长度只是 r - p，初始调用 merge_recurse(A, 0, length);，并且没有令人困惑的 +1/-1 调整。
在临时数组的末尾使用哨兵是不安全的，因为值 INT_MAX 可能实际上存在于数组中，导致不正确的结果或定义为索引 i 或 [=21 的行为=] 可能会超出其各自数组的末尾。这种方法不应该在学校教授，它存在根本性的缺陷。只需测试索引边界。
而不是使用 int q = floor((p + r) / 2); 你应该使用整数算法：
```
int q = p + (r - p) / 2;
```

这是修改后的版本：

#include <stdio.h>

void merge(int A[], int p, int q, int r) {
    int n1 = q - p;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (int i = 0; i < n1; ++i) {
        L[i] = A[p + i];
    }

    for (int j = 0; j < n2; ++j) {
        R[j] = A[q + j];
    }

    int i = 0;
    int j = 0;

    for (int k = p; k < r; ++k) {
        if (i < n1 && (j >= n2 || L[i] <= R[j])) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
    }
}

void merge_recurse(int A[], int p, int r) {
    if (r - p > 1) {
        int q = p + (r - p) / 2;
        merge_recurse(A, p, q);
        merge_recurse(A, q, r);
        merge(A, p, q, r);
    }
}

void merge_sort(int A[], size_t length) {
    merge_recurse(A, 0, length);
}

int main() {
    int length = 9;
    int A[] = { 3, 7, 61, 3, 40, 4, -1, 8, 10 };

    merge_sort(A, length);

    for (int i = 0; i < length; ++i) {
        printf("%i, ", A[i]);
    }
    printf("\n");

    return 0;
}

源代码中的什么导致了依赖于平台的结果

What in the source is causing platform dependent results

c

mergesort

cross-platform