什么是以下列方式总结数组元素的有效方法？

Suppose you are given an n sized array A and a integer k
Now you have to follow this function:

假设你有一个n大小的数组A和一个整数k现在你必须遵循这个函数:

long long sum(int k)
{
    long long sum=0;
    for(int i=0;i<n;i++){
        sum+=min(A[i],k);
    }
    return sum;
}

what is the most efficient way to find sum?

找到总和最有效的方法是什么?

EDIT: if I am given m(<=100000) queries, and given a different k every time, it becomes very time consuming.

编辑:如果给出m(<= 100000)个查询,并且每次给出不同的k,则变得非常耗时。

4 个解决方案

#1

If set of queries changes with each k then you can't do better than in O(n). Your only options for optimizing is to use multiple threads (each thread sums some region of array) or at least ensure that your loop is properly vectorized by compiler (or write vectorized version manually using intrinsics).

如果查询集随每个k而变化,那么你不能比O(n)做得更好。您优化的唯一选择是使用多个线程(每个线程对数组的某个区域求和)或至少确保您的循环由编译器正确地向量化(或使用内在函数手动编写向量化版本)。

But if set of queries is fixed and only k is changed, then you may do in O(log n) by using following optimization.

但是如果修复了一组查询并且只更改了k,则可以使用以下优化在O(log n)中进行。

Preprocess array. This is done only once for all ks:

预处理数组。所有ks只执行一次:

Sort elements
Make another array of the same length which contains partial sums

创建另一个包含部分和的长度相同的数组

For example:

inputArray: 5 1 3 8 7
sortedArray: 1 3 5 7 8
partialSums: 1 4 9 16 24

Now, when new k is given, you need to perform following steps:

现在,当给出新的k时,您需要执行以下步骤:

Make binary search for given k in sortedArray -- returns index of maximal element <= k

在sortedArray中对给定的k进行二进制搜索 - 返回最大元素<= k的索引

Result is partialSums[i] + (partialSums.length - i) * k

结果是partialSums [i] +(partialSums.length - i)* k

#2

You can do way better than that if you can sort the array A[i] and have a secondary array prepared once.

如果你可以对数组A [i]进行排序并准备一次辅助数组,那么你可以做得更好。

The idea is:

这个想法是:

Count how many items are less than k, and just compute the equivalent sum by the formula: count*k

计算有多少项小于k,只计算公式的等价和:count * k

Prepare an helper array which will give you the sum of the items superior to k directly

准备一个辅助数组,它将直接为您提供优于k的项目的总和

Preparation

Step 1: sort the array

第1步:对数组进行排序

std::sort(begin(A), end(A));

Step 2: prepare an helper array

第2步:准备一个辅助数组

std::vector<long long> p_sums(A.size());
std::partial_sum(rbegin(A), rend(A), begin(p_sums));

Query

long long query(int k) {
  // first skip all items whose value is below k strictly
  auto it = std::lower_bound(begin(A), end(A), k);

  // compute the distance (number of items skipped)
  auto index = std::distance(begin(A), it);

  // do the sum
  long long result = index*k + p_sums[index];
  return result;
}

The complexity of the query is: O(log(N)) where N is the length of the array A.

查询的复杂性为:O(log(N))其中N是数组A的长度。

The complexity of the preparation is: O(N*log(N)). We could go down to O(N) with a radix sort but I don't think it is useful in your case.

制备的复杂性是:O(N * log(N))。我们可以用基数排序到O(N),但我不认为它对你的情况有用。

References

#3

What you do seems absolutely fine. Unless this is really absolutely time critical (that is customers complain that your app is too slow and you measured it, and this function is the problem, in which case you can try some non-portable vector instructions, for example).

你做的似乎绝对没问题。除非这确实是绝对时间关键的(即客户抱怨你的应用程序太慢并且你测量它,并且这个功能是问题,在这种情况下你可以尝试一些非便携式矢量指令,例如)。

Often you can do things more efficiently by looking at them from a higher level. For example, if I write

通常,您可以通过从更高级别查看它们来更有效地执行操作。例如,如果我写

for (n = 0; n < 1000000; ++n)
   printf ("%lld\n", sum (100));

then this will take an awful long time (half a trillion additions) and can be done a lot quicker. Same if you change one element of the array A at a time and recalculate sum each time.

那么这将花费很长时间(增加五万亿)并且可以更快地完成。如果您一次更改数组A的一个元素并且每次重新计算总和,则相同。

#4

Suppose there are x elements of array A which are no larger than k and set B contains those elements which are larger than k and belongs to A.

假设有数组A的x个元素不大于k,而集合B包含那些大于k且属于A的元素。

Then the result of function sum(k) equals

然后函数sum(k)的结果等于

k * x + sum_b

,where sum_b is the sum of elements belonging to B.

,其中sum_b是属于B的元素之和。

You can firstly sort the the array A, and calculate the array pre_A, where

您可以先对数组A进行排序,然后计算数组pre_A,其中

pre_A[i] = pre_A[i - 1] + A[i] (i > 0),
        or 0 (i = 0);

Then for each query k, use binary search on A to find the largest element u which is no larger than k. Assume the index of u is index_u, then sum(k) equals

然后对于每个查询k,在A上使用二进制搜索来找到不大于k的最大元素u。假设u的索引是index_u,则sum(k)等于

 k * index_u + pre_A[n] - pre_A[index_u]

. The time complex for each query is log(n).

。每个查询的时间复杂度为log(n)。

In case array A may be dynamically changed, you can use BST to handle it.

如果可以动态更改阵列A,则可以使用BST来处理它。

#1