Cách tìm phần tử lớn nhất của một mảng có kích thước đã biết?

Question

Tôi cần phải tìm phần tử lớn nhất trong một mảng chứa chính xác 16 số nguyên. Tôi đang xem xét hai triển khai có thể. Đầu tiên, việc thực hiện hợp lý:

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

Và sau đó có việc thực hiện hơi điên mà lợi dụng thực tế là kích thước của mảng được biết:

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])))); 

Đó là việc thực hiện tốt hơn? max thường được triển khai trong phần cứng?

Answer 1

Hãy biên dịch chúng và xem những gì chúng tôi nhận được!

Trước hết, AFAIK, không có hàm "macro"/macro được xác định trong tiêu chuẩn C. Vì vậy, tôi đã thêm một (có vẻ phức tạp vì nó tránh đánh giá gấp đôi các đầu vào của nó).

#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; 
} 

phiên bản My gcc, mà là có liên quan khi nói về tối ưu hóa:

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 cho việc tối ưu, -S để lắp ráp đầu ra, -o - để xuất ra thiết bị xuất chuẩn.

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 

Được rồi, vì vậy test2() chắc chắn sẽ lâu hơn nữa.Tuy nhiên, nó không chi nhánh chút nào. Và nó chỉ ~ 3 hướng dẫn (tải bộ nhớ, so sánh, di chuyển có điều kiện) cho mỗi phần tử. test1() có 6 hướng dẫn (tải bộ nhớ, so sánh, di chuyển có điều kiện, tăng truy cập vòng lặp, so sánh vòng lặp, chi nhánh có điều kiện). Rất nhiều chi nhánh trong test1, có thể khó chịu (tùy thuộc vào dự đoán chi nhánh của kiến ​​trúc của bạn tốt như thế nào). Mặt khác, test2 tăng kích thước mã, điều này nhất thiết sẽ đẩy thứ gì đó khác ra khỏi bộ nhớ cache lệnh. Và có rất nhiều mối nguy hiểm dữ liệu trong test2 (tốt, và test1 ...) - có lẽ chúng ta có thể viết lại nó để sử dụng một vài thanh ghi bổ sung để giảm số lượng các quầy hàng đường ống?

Vì vậy, như bạn có thể thấy ngay bây giờ, đây không phải là câu hỏi dễ trả lời.

Cách duy nhất để biết là đo lường nó. Và thậm chí sau đó, nó sẽ thay đổi tùy thuộc vào việc thực hiện nội bộ/tối ưu hóa/kích thước bộ nhớ cache của mỗi mô hình CPU.

Vì vậy, tôi đã viết một chuẩn mực nhỏ:

#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; 
} 

Và kết quả:

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 

Kết luận: max() phiên bản nhanh trên Core i7-3517U Intel của tôi với 4 MB bộ nhớ cache (và tôi sẽ không yêu cầu nhiều hơn thế nữa bởi vì, một lần nữa, kết quả có thể khác với vi kiến ​​trúc).

Ngoài ra, -funroll-loops hoặc tối ưu hóa ngoại tích cực (và ít an toàn) được kích hoạt bởi -O3 thực sự tạo ra một sự khác biệt lớn đối với trường hợp test1, về cơ bản làm cho nó bình đẳng về thời gian để test2 - thậm chí tốt hơn một chút với -funroll-loops, nhưng gần đủ để chúng tôi không thể rút ra một kết luận đáng tin cậy từ những con số tôi nhận được. Nó có lẽ sẽ là thú vị khi nhìn vào hội đồng cho test1 ở đó, nhưng tôi sẽ để nó như một bài tập cho người đọc. ;)

Vì vậy, tôi đoán câu trả lời là "nó phụ thuộc".

Answer 2

Hãy thử sử dụng chức năng này:

int max_array(int a[], int count) { 
    int i, 
    max = a[0]; 

    for (i = 1; i < count; i++) { 
    if (a[i] > max) { 
     max = a[i]; 
    } 
    } 

    return max; 
} 

Edit:

Xin lỗi, đã không thấy rằng bạn đã cố gắng mà ra. Nhưng dù sao - đây là việc thực hiện tốt hơn, thứ hai bạn đề xuất chỉ là quái dị. Tôi nghĩ rằng nếu bạn muốn giữ mã của bạn sạch sẽ, điều này là xa như bạn đi.

Answer 3

Rõ ràng là thứ nhất, nó dễ đọc và mạnh mẽ hơn. Có thể max() không được triển khai trong phần cứng. của một implementation của max

Hare trong C++

template <class T> const T& max (const T& a, const T& b) { 
    return (a<b)?b:a;  // or: return comp(a,b)?b:a; for version (2) 
} 

Và gcc-4.9.2 thi hành C max xác định như

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

Vì vậy, nó là tốt hơn để sử dụng đầu tiên. Mặc dù kích thước nhỏ hơn 3 có thể được xem xét để thực hiện với thứ hai.

Answer 4

Theo như tôi biết, không có hàm tối đa hoặc tối thiểu trong thư viện chuẩn C hoặc GNU. Cách đầu tiên sẽ tốt hơn để sử dụng. Ngoài ra, bạn có thể so sánh trực tiếp mảng [i] để hiển thị tối đa.

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

Answer 5

Thứ nhất rõ ràng là triển khai đơn giản nhất.

Tuy nhiên, vấn đề này liên quan đến khái niệm Sorting Networks, đó là một lý thuyết phức tạp đáng ngạc nhiên về sắp xếp các tập hợp dữ liệu có kích thước cố định.