"明智地" 在 Python 列表中删除项目

Question

假设我有两个数组，分别表示校准曲线的x和y坐标。

X = [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,30,40,50]
Y = [2,4,6,8,10,12,14,16,18,20,24,28,32,36,40,60,80,100]

我的示例数组包含18个点。你会注意到x值并不是线性分布的，较低的x值处有更多的点。

假设我需要将我的校准曲线中点的数量减少到13个。显然，我可以只删除前五个或后五个点，但这将缩短我的整体x值范围。为了保持范围和最小化x值之间的空间，我会优先删除x= 2,4,6,8,10的值。删除这些x点及其相应的y值将留下所需的13个曲线上的点。

如何在Python中自动进行此点选择和删除？即，是否有一种算法可以从列表中选择最佳的x点，“最佳”被定义为使点尽可能靠近，同时保持总范围并遵守新的点数。

请注意，剩余的点必须在原始列表中，因此我不能将18个点插值到13个点网格上。

- Mark

---

抱歉 - 我编辑了我的原始问题以（希望！）澄清事情。基本上，我想减少值的数量，但保持总范围（即Min x和max x）。为了实现这一点，我想要移除接近的点。 - Mark

Answer 1

这将最大化所选点之间的平方根距离。在某种意义上，它尽可能地将点分散开。

import itertools
list(max(itertools.combinations(sorted(X), 13), i
         key=lambda l: sum((a - b) ** 2 for a, b in zip(l, l[1:]))))

请注意，这仅适用于小问题。选择k个点的时间复杂度为O(k * (len(X) choose k))，基本上是O(exp(len(X)))。因此，不要尝试在例如len(X) == 100和k == 10的情况下使用此方法。

- Elmar Peise

---

这是一个非常聪明的想法，具有直观的动机，所以要加一。对于给定的问题规模，它将表现良好，尽管如果18变得更大，它很快就会变得不可行。我不太确定在这种情况下如何计算。也许一些爬山算法会起作用，或者至少提供一个合理的启发式方法。 - John Coleman

当然，你是正确的。我已经在答案中添加了一条注释。 - Elmar Peise

即使是在100、10的情况下，这仍然是一个好的标准。你只需要找到一种非蛮力的方法来找到它，或者至少近似它。 - John Coleman

Answer 2

X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 30, 40, 50]
Y = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 28, 32, 36, 40, 60, 80, 100]

assert len(X) == len(set(X)), "Duplicate X values found"

points = list(zip(X, Y))
points.sort()  # sorts by X

while len(points) > 13:
    # Find index whose neighbouring X values are closest together
    i = min(range(1, len(points) - 1), key=lambda p: points[p + 1][0] - points[p - 1][0])
    points.pop(i)

print(points)

输出：

[(1, 2), (3, 6), (5, 10), (7, 14), (10, 20), (12, 24), (14, 28), (16, 32), (18, 36), (20, 40), (30, 60), (40, 80), (50, 100)]

如果你想要再次获得原始系列：

X, Y = zip(*points)

- Alex Hall

Answer 3

这里有一种递归方法，它反复删除将被最少错过的点：

def mostRedundantPoint(x):
    #returns the index, i, in the range 0 < i < len(x) - 1
    #that minimizes x[i+1] - x[i-1]
    #assumes len(x) > 2 and that x
    #is sorted in ascending order

    gaps = [x[i+1] - x[i-1] for i in range(1,len(x)-1)]
    i = gaps.index(min(gaps))
    return i+1

def reduceList(x,k):
    if len(x) <= k:
        return x
    else:
        i = mostRedundantPoint(x)
        return reduceList(x[:i]+x[i+1:],k)

X = [1,2,3,4,5,6,7,8,9,10,12,14,16,18,20,30,40,50]
print(reduceList(X,13))
#prints [1, 3, 5, 7, 10, 12, 14, 16, 18, 20, 30, 40, 50]

这个列表基本上与您的预期输出一致，因为7和8具有相同的净效果。从1000个元素中减少到100个元素几乎是瞬间完成的，因此在某种意义上它是相当快速的sorted([random.randint(1,10**6) for i in range(1000)])。由于它是递归的，如果您尝试删除的点比这多得多，它将会爆栈，但是对于您似乎想要解决的问题规模来说，这不应该是一个问题。如果需要，您当然可以用循环替换递归。

- John Coleman

Answer 4

一个可以实现这个的算法：

1. 将每个数字转换为其与左边和右边数字差的绝对值之和。如果一个数字不存在于左边或右边，例如在首位或末尾，则用 MAX_INT 代替。例如，1 将变为 MAX_INT; 2 将变为 2; 10 将变为 3。
2. 删除具有最低总和的第一个数字。
3. 如果需要删除更多数字，请返回步骤 1。

这个算法会移除 2、4、6、8、10、3 等数字...

- Javier