두 배열의 합계를 비교하는 빠른 알고리즘?

Question

정수 배열이 2 개 있다고 가정하면, 같은 길이가 아니어도 인덱스의 값은 유효한 정수 (최소 ~ 최대)입니다. 예 :

int data1[] = {1227210749, 382745290, 567552295, 1910060611, 
      577735884, 75518037, 742485551, 1202127013, 
      386030509, 308032134}; 

int data2[] = {1729472635, 1258098863, 259427472, 1664987257, 
      994376913, 1581883691, 1728724734, 2034013490}; 

내가 더 빨리 합계를 비교하면 어느 것이 더 큰 금액인지 알 수 있습니까?

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    // compares if the sum of data1 is bigger than sum of data2 
} 

Answer 1

확실한 방법은 두 배열의 합계를 취하여 어느 것이 더 큰지 확인하는 것입니다. 뭔가 이렇게 :

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    return (std::accumulate(a, a+len_a, 0) - std::accumulate(b, b+len_b, 0); 
} 

그러나 이것은 정수 오버플로의 가능성을 소개합니다. 이는 accumulate의 마지막 매개 변수를 0LL 또는 0.0으로 변경하여 피할 수 있습니다.

Answer 2

직관적으로 (내 생각 내 경우에는 매우 약한, 난 하지 알고리즘 전문가)이 한 번 각 숫자를보고 단순히 합계를 계산하지 않고 할 수 없습니다 것처럼 느낀다 . 이것은 정수가 서명 되었기 때문에 배열의 합은 요소를 추가 할 때 0 (또는 음수)이 될 수 있으므로 모든 요소를 ​​살펴야합니다.

그래서,이 같은 기능을 구현하려고 :

int int_array_sum(const int *array, size_t num_elements); 

는 단순히 두 개의 배열의 각에 그에게 전화하고 비교한다.

편집 : Tristan's answer에 지적한대로 잠재적으로 큰 정수를 추가 할 때 오버플로가 발생할 위험이 있습니다. 이것이 문제라면 (실제로 응용 프로그램이 매우 명확합니다. 오버플로 결과가 "더 큰 합계"의 일부 임) 더 넓은 정수 유형으로 전환하거나 double으로 이동할 수 있습니다.

Answer 3

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    long long sum_a = std::accumulate(a, a + len_a, 0ll); 
    long long sum_b = std::accumulate(b, b + len_b, 0ll); 

    return (sum_a < sum_b ? -1 : (sum_a == sum_b ? 0 : 1)); 
} 

Answer 4

int compare(int a[], int len_a, int b[], int len_b) 
{ 
    double sum1=0; 
double sum2=0; 

for(int i=0;i<len_a;i++) 
sum1=sum1+a[i]; 

for(int i=0;i<len_b;i++) 
sum2=sum2+b[i]; 

if(sum1>sum2) 
return 1; 
else 
return 0; 

}