Быстрый алгоритм сравнения сумм двух массивов?

Question

Предположим, что у меня есть 2 целых массива, они могут быть не такой же длины, а значение для любого индекса - действительное целое число (min ~ max). таких как:

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; 

}