効率的な方法で最大値と最小値を見つける

bugfix> c > 投稿 2020-08-22 17:48

私は次のような配列を持っています

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

ここで、 arr1[0] 範囲の数を示します。つまり、上記の例には 34 to 78 の2つの範囲があります。および 5 to 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 to 39 の1つの範囲しかありませんおよび 2 個々の値であるため、最小値は 2 です最大値は 39 です

もう一つの例は

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

この例には範囲がないため、最小値は 5 です最大値は 256 です

c

回答 1 件

配列内の異常なデータ構造により、ある程度の最適化が可能です。 arr[0] で識別される範囲（値のペア）を扱っている間、ペアの最初の要素を最小値に対して、2番目の要素を最大値に対してテストするだけです。範囲外の値を扱う場合、各要素を最小値と最大値の両方に対してチェックする必要があります。

それは次のようなコードにつながります：

#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

このより複雑なコードが実際に値をスキャンすることよりも効率を大幅に向上させるかどうかは（質問に示されているように）議論の余地があります-または測定可能ですが、測定には検出可能な配列内の非常に多くの要素が必要です。示されている配列サイズでは、本質的に測定可能な差はありません。

Trends

bugfix

効率的な方法で最大値と最小値を見つける

c

関連記事