python - 有效地搜索一对有噪声的有序列表

Question

假设两个数据集是有序的，并且它们包含成对匹配，什么是发现对的有效方法？任何一个列表中都可能有噪音。

从集合 A、B 到集合 C 将由对 (A[X¹),B[Y¹]),(A[X ²],B[Y²]),...,(A[Xⁿ],B[Yⁿ ]) 这样 X¹ < X² < ... < Xⁿ 和 Y¹ < Y< sup>2 < ... < Yⁿ.

这个问题可以用简化的 Python block 来演示，其中如何验证成功对的具体细节是无关紧要的。 因为验证条件无关紧要，条件 return_pairs(A, B, validate) == return_pairs(B, A, validate) 不需要成立，因为 A、B 中的数据不需要相同，只是必须存在 (A[x],B[y]) 的验证函数

A = [0,0,0,1,2,0,3,4,0,5,6,0,7,0,0,8,0,0,9]
B = [1,2,0,0,0,0,0,3,0,0,4,0,5,6,0,0,7,0,0,8,0,9]
B1 = [1,2,0,0,0,0,0,3,0,0,4,0,5,6,0,0,7,7,7,0,0,8,0,9]

def validate(a,b):
  return a and b and a==b

def return_pairs(A,B, validation):
  ret = []    
  x,y = 0,0    
  # Do loops and index changes...
    if validation(A[x], B[y]):
        ret.append((A[x], B[y]))
  return ret

assert zip(range(1,10), range(1,10)) == return_pairs(A,B,validate)
assert zip(range(1,10), range(1,10)) == return_pairs(A,B1,validate)

Answer 1

不是在两个嵌套循环中迭代每个列表，您可以首先根据自己的标准去除噪音，然后创建包含过滤元素的第三个列表，并根据您的验证运行列表中的每个项目(作为新形成的元组) .这是假设我正确理解了这个问题，但我认为我并没有真正理解:

Demo

A = [0,0,0,1,2,0,3,4,0,5,6,0,7,0,0,8,0,0,9]
B = [1,2,0,0,0,0,0,3,0,0,4,0,5,6,0,0,7,0,0,8,0,9]

def clean(oldList):
    newList = []
    for item in oldList:
        if 0<item and (not newList or item>newList[-1]):
            newList.append(item)
    return newList
    
def validate(C):
    for item in C:
        if item[0] != item[1]:
            return False
    return True

C = zip(clean(A),clean(B))

#clean(A):[1, 2, 3, 4, 5, 6, 7, 8, 9]
#clean(B):[1, 2, 3, 4, 5, 6, 7, 8, 9]
#list(C):[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)]
#validate(C): True