最小化两个列表之间的增量

Question

给定两个列表，其中一个列表按某个因数alpha缩放：

from random import randint

alpha = 1.2
x = [randint(1, 100) for x in range(1000)]
y = [int(alpha * i) for i in x]

我想过滤两个列表中低于某个阈值的值，从而使两个列表中返回的元素数量的增量最小化。因此，如果我的x的阈值是40，那么len([i for i in x if i < 40]) ~ 400我想知道当alpha未知时y的阈值应该是多少，因此返回的元素数是~400，即本例中的48。

Answer 1

您可以计算平均值alpha，如下所示：

alpha = sum((yn / float(xn)) for xn, yn in zip(x, y)) / len(x)

然后：

y_threshold = int(alpha * x_threshold)

如果最小化abs(len(filtered_x) - len(filtered_y))是关键，那么可以在y_threshold周围执行局部搜索。你知道吗

Answer 2

你的x_threshold允许你知道它下面有多少个x（这里是400）。所以您只需要在y中找到排名第400位的元素，并将其用作y_threshold。你知道吗

您可以通过排序y（这是过度杀戮）或选择第n个（可以在O(N)中完成）。这种方法总是达到delta=0。你知道吗

对于更简单的近似解，估计alpha为两个列表和集合y_threshold = alpha . x_threshold之和的比率。（可以优选alpha、Sum(y.x)/Sum(x^2)或标准差比率的最小二乘估计值）