c - 以有效的方式找到最大值和最小值

Question

我有一个数组，如下所示

uint32_t arr1[] = {2, 34, 78, 5, 10, 100};

其中 arr1[0] 表示范围数，即在上面的示例中有两个范围 34 ​​到 78 和 5 到 10 100 是一个单独的值。

我想以一种有效的方式从这个数组中找到最大值和最小值，在 arr1 中，最大值是 100，最小值是 5。

我是这样做的:

max = arr1[1];
min = arr1[1];
int len = sizeof(arr1)/sizeof(arr1[0]);

for(int i = 2; i < len; i++){
  if(arr[i] < min)
     min = arr[i];
  if(arr[i] > max)
     max = arr[i];  
}

另一个例子是

uint32_t arr2[] = {1, 18, 39, 2};

在此示例中，只有一个范围，即 18 到 39 并且 2 是一个单独的值，因此最小值为 2 并且最大值为 39

还有一个例子是

uint32_t arr3[] = {0, 14, 5, 256, 99};

此示例中没有范围，因此最小值为 5，最大值为 256

Answer 1

数组中不寻常的数据结构允许进行一些优化。当您处理由 arr[0] 标识的范围(值对)时，您只需根据最小值测试该对的第一个元素，并根据最大值测试第二个元素。当您处理非范围值时，您必须根据最小值和最大值检查每个元素。

这导致如下代码:

#undef NDEBUG
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>

static void find_min_max(size_t num, uint32_t arr[num], uint32_t *pmin, uint32_t *pmax)
{
    assert(arr != 0 && pmin != 0 && pmax != 0 && num > 1);
    assert(arr[0] <= num);
    assert(arr[0] == 0 || num > 2);

    uint32_t max = arr[1];
    uint32_t min = arr[1];
    uint32_t lim = arr[0] * 2;
    size_t i;

    for (i = 1; i < lim; i += 2)
    {
        assert(arr[i] <= arr[i + 1]);
        if (arr[i] < min)
            min = arr[i];
        if (arr[i + 1] > max)
            max = arr[i + 1];
    }

    for ( ; i < num; i++)
    {
        if (arr[i] < min)
            min = arr[i];
        else if (arr[i] > max)
            max = arr[i];
    }
    *pmin = min;
    *pmax = max;
}

static void test_min_max(const char *tag, size_t num, uint32_t arr[num])
{
    uint32_t lim = arr[0] * 2;
    size_t i;

    printf("%s (%zu):\n", tag, num);
    for (i = 1; i < lim; i += 2)
        printf("  Range %zu: %" PRIu32 "..%" PRIu32 "\n", i / 2, arr[i], arr[i + 1]);
    while (i < num)
        printf("  Value: %" PRIu32 "\n", arr[i++]);

    uint32_t min;
    uint32_t max;
    find_min_max(num, arr, &min, &max);

    printf("%s: min = %" PRIu32 ", max = %" PRIu32 "\n", tag, min, max);
}

int main(void)
{
    uint32_t arr1[] = { 2, 34, 78, 5, 10, 100 };
    uint32_t arr2[] = { 1, 18, 39, 2 };
    uint32_t arr3[] = { 0, 14, 5, 256, 99 };
    uint32_t arr4[] = { 2, 9, 14, 5, 256 };
    uint32_t arr5[] = { 2, 9, 14, 5, 256, 2 };
    uint32_t arr6[] = { 2, 9, 14, 5, 256, 379 };
    uint32_t arr7[] = { 0, 9, };
    uint32_t arr8[] = { 1, 9, 9 };

    test_min_max("arr1", sizeof(arr1) / sizeof(arr1[0]), arr1);
    test_min_max("arr2", sizeof(arr2) / sizeof(arr2[0]), arr2);
    test_min_max("arr3", sizeof(arr3) / sizeof(arr3[0]), arr3);
    test_min_max("arr4", sizeof(arr4) / sizeof(arr4[0]), arr4);
    test_min_max("arr5", sizeof(arr5) / sizeof(arr5[0]), arr5);
    test_min_max("arr6", sizeof(arr6) / sizeof(arr6[0]), arr6);
    test_min_max("arr7", sizeof(arr7) / sizeof(arr7[0]), arr7);
    test_min_max("arr8", sizeof(arr8) / sizeof(arr8[0]), arr8);

    return 0;
}

运行时，它会产生输出:

arr1 (6):
  Range 0: 34..78
  Range 1: 5..10
  Value: 100
arr1: min = 5, max = 100
arr2 (4):
  Range 0: 18..39
  Value: 2
arr2: min = 2, max = 39
arr3 (5):
  Value: 14
  Value: 5
  Value: 256
  Value: 99
arr3: min = 5, max = 256
arr4 (5):
  Range 0: 9..14
  Range 1: 5..256
arr4: min = 5, max = 256
arr5 (6):
  Range 0: 9..14
  Range 1: 5..256
  Value: 2
arr5: min = 2, max = 256
arr6 (6):
  Range 0: 9..14
  Range 1: 5..256
  Value: 379
arr6: min = 5, max = 379
arr7 (2):
  Value: 9
arr7: min = 9, max = 9
arr8 (3):
  Range 0: 9..9
arr8: min = 9, max = 9

这种更复杂的代码是否真的比简单地扫描值(如问题中所示)获得了显着的效率是值得商榷的——或者是可测量的，但测量需要数组中的元素数量大大增加才能被检测到。在显示的阵列大小上，基本上没有可测量的差异。