2

标题相当模糊，所以我在那里道歉。

我想做的是：

每个数据集我有三个数字。X、Y 和 Z。它们总是正数，Z 是 2 的幂。我需要在 X 和 Y、Z 次之间进行插值。每次插值从 X 到 Y 的距离是当前迭代除以 Z 的百分比。然后使用round to nearest对插值的返回进行四舍五入。然后我需要计算每个数据集存在多少每个结果。

像这样：n(i) = Round(x + (y - x) * (i / (Z-1)))

示例（为简单起见仅保留 3 位小数）：

X, Y, Z
3, 5, 8

不四舍五入的值：

3.000   3.286   3.571   3.857   4.143   4.429   4.714   5.000

四舍五入的值：

3 3 4 4 4 4 5 5

最终目标：

2 3's, 4 4's, 2 5's.

这个，我可以做的很好。然而，我想要做的是找出有 2 个 3、4 个 4 和 2 个 5（按此顺序），而不必实际插值 8 次，如示例所示。实际上，数字更像是 291、3472、8192；我需要相当快地处理数千个这样的问题。

如何在不迭代每个数据集 Z 次的情况下做到这一点？

编辑：Y 并不总是大于 X。在这个例子中，如果它是 5、3、8.. 我想知道有 2 个 5、4 个 4 和 2 个 3 的顺序。

4

1 回答 1

1

在某些情况下，您可以使用小于 Z 值的计算来执行此操作，但我不确定它是否会比直接的 Z 计算更快。

首先，您需要区分三种情况。

案例 1：Z > Y - X

在这种情况下，所有计数都为 1，问题是哪些数字具有该计数。唯一知道的方法是计算所有 Z 数。

案例2：Z == Y - X

简单：X 和 Y 之间的每个数字都计数为 1。

案例 3：Z < Y - X

我的想法如下：除了第一次和最后一次计数外，数字不会有太大差异。事实上，我认为（但尚未证明，所以我的直觉可能是错误的）最小和最大数量永远不会超过 1 个。

所以你可以有一个像 (number:count) 这样的序列

1:1 2:5 3:5 4:4 5:5 6:4 7:5 8:2

但不是

1:1 2:5 3:5 4:3 5:5 6:4 7:5 8:2

然后，您可以执行以下操作：

首先以直接的方式计算 X 的计数

然后用直截了当的方式计算 X + 1 的计数，我们称之为 C，并记住最后一个非四舍五入的数字，我们称之为 N。所以 ROUND(N) == X + 1。

然后，对于 X + 2 到 Y - 1，测试计数是 C - 1、C 还是 C + 1

你怎么能那样做？简单计算

N + ((Y - X) / Z) * (C - 1)
N + ((Y - X) / Z) * (C)
N + ((Y - X) / Z) * (C + 1)

围住他们，看看会发生什么。

但是：这将导致代码复杂且难以理解和维护，并且可能不会比直接方式更快（除非 Z 比 Y - X 大几个数量级）。YMMV。

更新：

您观察到在案例 3 中计数是对称的是正确且非常有用的：它允许您将所需计算的数量减少一半。

于 2013-10-30T16:49:38.797 回答