搜索
搜索

如何找到已知大小的数组中的最大元素？

Alex 发表于 Dev
33
亚历克斯

我需要在包含正好16个整数的数组中找到最大的元素。我正在考虑两种可能的实现。首先，明智的实现：

int largest = array[0];
for (int i = 1; i < 16; i++) {
  const int val = array[i];
  if (val > largest) {
    largest = val;
  }
}

然后是一个有点疯狂的实现，它利用了已知数组大小的事实：

const int max_value =
  max(
    max(
      max(
        max(array[0], array[1]),
        max(array[2], array[3])),
      max(
        max(array[4], array[5]),
        max(array[6], array[7]))),
    max(
      max(
        max(array[8], array[9])
        max(array[10], array[11])),
      max(
        max(array[12], array[13])
        max(array[14], array[15]))));

哪个更好的实现？是max通常在硬件中实现？

尼尔·多尔科

让我们编译它们，看看会得到什么！

首先，AFAIK在C标准中没有定义“最大”功能/宏。因此，我添加了一个（看起来很复杂，因为它避免了对其输入的双重评估）。

#define max(a,b) ({ \
    const __typeof__ (a) _a = (a); \
    const __typeof__ (b) _b = (b); \
    _a > _b ? _a : _b; \
})

int __attribute__ ((noinline)) test1(const int* array) {
    int largest = array[0];
    for (int i = 1; i < 16; i++) {
      const int val = array[i];
      if (val > largest) {
        largest = val;
      }
    }
    return largest;
}

int __attribute__ ((noinline)) test2(const int* array) {
    const int max_value =
      max(
        max(
          max(
            max(array[0], array[1]),
            max(array[2], array[3])),
          max(
            max(array[4], array[5]),
            max(array[6], array[7]))),
        max(
          max(
            max(array[8], array[9]),
            max(array[10], array[11])),
          max(
            max(array[12], array[13]),
            max(array[14], array[15]))));
    return max_value;
}

我的gcc版本，在谈到优化时很重要：

tmp$ gcc --version
gcc (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

-O2用于优化，-S输出组装，-o -输出到stdout。

tmp$ gcc -std=c99 -O2 -S test.c -o -
    .file   "test.c"
    .text
    .p2align 4,,15
    .globl  test1
    .type   test1, @function
test1:
.LFB0:
    .cfi_startproc
    movl    (%rdi), %eax
    xorl    %edx, %edx
    .p2align 4,,10
    .p2align 3
.L3:
    movl    4(%rdi,%rdx), %ecx
    cmpl    %ecx, %eax
    cmovl   %ecx, %eax
    addq    $4, %rdx
    cmpq    $60, %rdx
    jne .L3
    rep ret
    .cfi_endproc
.LFE0:
    .size   test1, .-test1
    .p2align 4,,15
    .globl  test2
    .type   test2, @function
test2:
.LFB1:
    .cfi_startproc
    movl    (%rdi), %edx
    cmpl    %edx, 4(%rdi)
    cmovge  4(%rdi), %edx
    movl    8(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    12(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    16(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    20(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    24(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    28(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    32(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    36(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    40(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    44(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    48(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    52(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    56(%rdi), %eax
    cmpl    %eax, %edx
    cmovl   %eax, %edx
    movl    60(%rdi), %eax
    cmpl    %eax, %edx
    cmovge  %edx, %eax
    ret
    .cfi_endproc
.LFE1:
    .size   test2, .-test2
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

好吧，所以test2()看起来肯定更长了。但是，它根本不分支。每个元素只有3条指令（内存加载，比较，条件移动）。test1()有6条指令（内存加载，比较，条件移动，循环计数器递增，循环计数器比较，条件分支）。中的许多分支机构test1可能会很麻烦（取决于您的体系结构分支预测的水平）。另一方面，test2增加了代码大小，这必然会将其他内容从指令缓存中推出。而且test2（还有test1……）中存在很多数据危险-也许我们可以重写它，以使用一些额外的寄存器来减少流水线停顿的数量？

因此，如您现在可能已经看到的那样，这不是一个容易回答的问题。

唯一真正知道的方法是测量它。即使这样，它也会根据每个CPU模型的内部实现/优化/缓存大小而有所不同。

所以我写了一个小基准：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>

#define N (1000000)

int main() {
    printf("    %12s %12s  %12s %12s\n", "test1 time", "test2 time", "test1 out", "test2 out");
    int* data = malloc(N * 16 * sizeof(int));
    srand(1);
    for (int i=0; i<16*N; ++i) {
        data[i] = rand();
    }

    const int* a;
    struct timespec t1, t2, t3;
    for (int attempt=0; attempt<10; ++attempt) {
        uint32_t sum1 = 0;
        uint32_t sum2 = 0;

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t1);
        a = data;
        for (int i=0; i<N; ++i) {
            sum1 += test1(a);
            a += 16;
        }

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t2);
        a = data;
        for (int i=0; i<N; ++i) {
            sum2 += test2(a);
            a += 16;
        }

        clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &t3);
        uint64_t nanos1 = (t2.tv_sec - t1.tv_sec) * 1000000000L + (t2.tv_nsec - t1.tv_nsec);
        uint64_t nanos2 = (t3.tv_sec - t2.tv_sec) * 1000000000L + (t3.tv_nsec - t2.tv_nsec);
        printf("%2d: %12lu %12lu  %12u %12u\n", attempt+1, nanos1, nanos2, sum1, sum2);
    }
    return 0;
}

结果：

tmp$ gcc -std=gnu99 -O2 test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:     16251659     10431322    4190722540   4190722540
 2:     16796884     10639081    4190722540   4190722540
 3:     16443265     10314624    4190722540   4190722540
 4:     17194795     10337678    4190722540   4190722540
 5:     16966405     10380047    4190722540   4190722540
 6:     16803840     10556222    4190722540   4190722540
 7:     16795989     10871508    4190722540   4190722540
 8:     16389862     11511950    4190722540   4190722540
 9:     16304850     11704787    4190722540   4190722540
10:     16309371     11269446    4190722540   4190722540
tmp$ gcc -std=gnu99 -O3 test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:      9090364      8813462    4190722540   4190722540
 2:      8745093      9394730    4190722540   4190722540
 3:      8942015      9839356    4190722540   4190722540
 4:      8849960      8834056    4190722540   4190722540
 5:      9567597      9195950    4190722540   4190722540
 6:      9130245      9115883    4190722540   4190722540
 7:      9680596      8930225    4190722540   4190722540
 8:      9268440      9998824    4190722540   4190722540
 9:      8851503      8960392    4190722540   4190722540
10:      9767021      8875165    4190722540   4190722540
tmp$ gcc -std=gnu99 -Os test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:     17569606     10447512    4190722540   4190722540
 2:     17755450     10811861    4190722540   4190722540
 3:     17718714     10372411    4190722540   4190722540
 4:     17743248     10378728    4190722540   4190722540
 5:     18747440     10306748    4190722540   4190722540
 6:     17877105     10782263    4190722540   4190722540
 7:     17787171     10522498    4190722540   4190722540
 8:     17771172     10445461    4190722540   4190722540
 9:     17683935     10430900    4190722540   4190722540
10:     17670540     10543926    4190722540   4190722540
tmp$ gcc -std=gnu99 -O2 -funroll-loops test.c -o test
tmp$ ./test 
      test1 time   test2 time     test1 out    test2 out
 1:      9840366     10008656    4190722540   4190722540
 2:      9826522     10529205    4190722540   4190722540
 3:     10208039     10363219    4190722540   4190722540
 4:      9863467     10284608    4190722540   4190722540
 5:     10473329     10054511    4190722540   4190722540
 6:     10298968     10520570    4190722540   4190722540
 7:      9846157     10595723    4190722540   4190722540
 8:     10340026     10041021    4190722540   4190722540
 9:     10434750     10404669    4190722540   4190722540
10:      9982403     10592842    4190722540   4190722540

结论：在具有4 MB高速缓存的Intel Core i7-3517U上，max（）版本更快（并且我不会要求更多，因为同样，结果可能会因微体系结构而异）。

此外，-funroll-loops或者通过实施的进取性（不太安全）优化-O3确实对test1情况产生了巨大的影响，本质上使其在时间上相等test2-也许甚至更好-funroll-loops，但接近度足以使我们无法自信从我得到的数字得出结论。在test1那里查看组装可能会很有趣，但是我将其留给读者作为练习。;）

因此，我猜答案是“取决于”。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

快速找到二维数组中的最大元素

如何从CLIPS中的列表中找到最大元素？

向数组中插入绝对差后，找到数组中的第k个最大元素

在数组中查找最大元素

C 中的递归 - 数组的最大元素

dailogflow中数组的最大元素

使用“ ==”获取数组中的最大元素

Java中数组的最大元素

将数组中的每个元素相减并找到其中的最大元素

如何找到n维numpy数组的第i个最大元素的索引？

如何在数组的左侧和右侧找到最大元素？

如何在 PL/SQL 中找到数组的第一个最大元素

此代码无法在nasm中找到数组中的最大元素

仅使用队列查找大小为 K 的所有连续子数组中的最大元素

C递归程序从数组中找到最大元素

在Scala中，如何找到数组元素的大小

如何找到有条件的海龟列表中的最大元素

如何在 C++ 中递归地找到最大元素的索引？

如何交换数组中的最后一个元素和最大元素？

如何找到最高序列号的最大元素

数组中每个元素右侧的最大元素

在numpy中的3d数组中。如何提取三维最大元素的索引？

如何对数组中的三个最大元素进行排序和查找？

如何在多个数组中查找最大元素值？

如何使用Lodash从数组中获取唯一和最大元素

如何每次在常量数组中打印下一个最大元素？

如何查找/打印数组的“n”个最大元素？

如何在O（n）中长度为n的未排序数组中找到第k个最大元素？

使用递归查找数组中的最大元素

TOP 榜单

  1. 1

    UITableView的项目向下滚动后更改颜色，然后快速备份

  2. 2

    Linux的官方Adobe Flash存储库是否已过时？

  3. 3

    用日期数据透视表和日期顺序查询

  4. 4

    应用发明者仅从列表中选择一个随机项一次

  5. 5

    Mac OS X更新后的GRUB 2问题

  6. 6

    验证REST API参数

  7. 7

    Java Eclipse中的错误13，如何解决？

  8. 8

    带有错误“ where”条件的查询如何返回结果？

  9. 9

    ggplot：对齐多个分面图-所有大小不同的分面

  10. 10

    尝试反复更改屏幕上按钮的位置 - kotlin android studio

  11. 11

    如何从视图一次更新多行（ASP.NET - Core）

  12. 12

    计算数据帧中每行的NA

  13. 13

    蓝屏死机没有修复解决方案

  14. 14

    在 Python 2.7 中。如何从文件中读取特定文本并分配给变量

  15. 15

    离子动态工具栏背景色

  16. 16

    VB.net将2条特定行导出到DataGridView

  17. 17

    通过 Git 在运行 Jenkins 作业时获取 ClassNotFoundException

  18. 18

    在Windows 7中无法删除文件（2）

  19. 19

    python中的boto3文件上传

  20. 20

    当我尝试下载 StanfordNLP en 模型时，出现错误

  21. 21

    Node.js中未捕获的异常错误，发生调用

热门标签

归档