c++ - 小数因子的缩小数组

Question

是否有有效的方法来按小数因子缩小数组中的元素数量？

我想按一定比例缩小一个数组中的元素。

例子:如果我有 10 个元素并且需要按因子 2 缩小。

1 2 3 4 5 6 7 8 9 10
scaled to
1.5 3.5 5.5 7.5 9.5

将 2 按 2 分组并使用算术平均值。

我的问题是，如果我需要将包含 10 个元素的数组缩减为 6 个元素怎么办？理论上我应该对 1.6 个元素进行分组并求出它们的算术平均值，但该怎么做呢？

Answer 1

在提出解决方案之前，让我们以更正式的方式定义“缩小规模”。我会建议这个定义:

Downsizing starts with an array a[N] and produces an array b[M] such that the following is true:

1. M <= N - otherwise it would be upsizing, not downsizing
2. SUM(b) = (M/N) * SUM(a) - The sum is reduced proportionally to the number of elements
3. Elements of a participate in computation of b in the order of their occurrence in a

让我们考虑一下您缩小规模的示例 1, 2, 3, 4, 5, 6, 7, 8, 9, 10到六个元素。您的数组总数为 55，因此新数组的总数为 (6/10)*55 = 33 .我们可以通过两个步骤实现这一总数:

• 遍历数组a对其元素求和，直到我们达到 N/M 的整数部分分数(根据上述规则 1 必须是假分数)
• 假设a[i]是 a 的最后一个元素我们可以在当前迭代中将其作为一个整体。取 a[i+1] 的分数等于N/M的小数部分
• 继续下一个数字，从 a[i+1] 的剩余部分开始
• 完成后，您的数组 b将包含 M总数为 SUM(a) .再次遍历数组，并将结果缩放 N/M .

以下是它如何与您的示例一起工作:

b[0] = a[0] + (2/3)*a[1]              = 2.33333
b[1] = (1/3)*a[1] + a[2] + (1/3)*a[3] = 5
b[2] = (2/3)*a[3] + a[4]              = 7.66666
b[3] = a[5] + (2/3)*a[6]              = 10.6666
b[4] = (1/3)*a[6] + a[7] + (1/3)*a[8] = 13.3333
b[5] = (2/3)*a[8] + a[9]              = 16
                                        --------
                                Total = 55

按比例缩小 6/10产生最终结果:

1.4 3 4.6 6.4 8 9.6 (Total = 33)

这是一个简单的 C++ 实现:

double need = ((double)a.size()) / b.size();
double have = 0;
size_t pos = 0;
for (size_t i = 0 ; i != a.size() ; i++) {
    if (need >= have+1) {
        b[pos] += a[i];
        have++;
    } else {
        double frac = (need-have); // frac is less than 1 because of the "if" condition
        b[pos++] += frac * a[i];   // frac of a[i] goes to current element of b
        have = 1 - frac;
        b[pos] += have * a[i];     // (1-frac) of a[i] goes to the next position of b
    }
}
for (size_t i = 0 ; i != b.size() ; i++) {
    b[i] /= need;
}

Demo.