在 Python 中使用二进制搜索比较列表列表

Question

我有 2 个列表列表 x（100 万个元素）和 y（100 万个元素）并且想要得到 z=x-y。每个列表由每个 4 个元素的子列表组成，其中每个子列表的第一个元素已排序。第一个元素严格递增，不存在重复项。现在，我使用列表推导来完成此操作，运行大约需要 6.5 小时。我想知道执行此操作最省时的方法是什么，请记住我的最终结果也应该是列表列表。

其次，由于我所有的第一个元素都已排序，所以我认为进行二分查找是一个更好的主意。二分查找的思想—— 例如考虑我有 2 个大小为 x=30 和 y=10 的列表我正在遍历 y 的元素并使用二进制搜索将每个子列表的第一个元素与 x 中的元素进行比较，当我找到一个匹配项时，该子列表已从 x 列表中删除。所以预期的输出列表应该包含 20 elements.But 我写的代码给了我 23（它不会删除最后三个匹配项）而且我不知道它有什么问题。代码如下：

def intersection(x,y):
    temp=x[:]
    for i in range(len(y)):
        l=0
        h=len(x)-1
        while l<h:
            mid=l+((h-l)/2)
            if y[i][0]==temp[mid][0]:
                a=y[i]
                x.remove(a)
                break
            elif y[i][0]>temp[mid][0]:
                if l==mid:
                    break
                l=mid
            elif y[i][0]<temp[mid][0]:
                h=mid
    return(x)






X-List input of 30 elements
[[1.0, 25.0, 0.0, 0.0]
[2.0, 0.0, 25.0, 0.0]
[3.0, 0.0, 50.0, 0.0]
[4.0, 50.0, 50.0, 0.0]
[5.0, 50.0, 0.0, 0.0]
[6.0, 0.0, 25.0, 10.0]
[7.0, 25.0, 0.0, 10.0]
[8.0, 50.0, 0.0, 10.0]
[9.0, 50.0, 50.0, 10.0]
[10.0, 0.0, 50.0, 10.0]
[11.0, 0.0, 0.0, 0.0]
[12.0, 0.0, 0.0, 10.0]
[13.0, 17.6776695, 17.6776695, 0.0]
[14.0, 0.0, 34.3113632, 0.0]
[15.0, 25.9780293, 50.0, 0.0]
[16.0, 50.0, 25.9780293, 0.0]
[17.0, 34.3113632, 0.0, 0.0]
[18.0, 17.6776695, 17.6776695, 10.0]
[19.0, 34.3113632, 0.0, 10.0]
[20.0, 50.0, 25.9780293, 10.0]
[21.0, 25.9780293, 50.0, 10.0]
[22.0, 0.0, 34.3113632, 10.0]
[23.0, 11.6599302, 0.0, 0.0]
[24.0, 0.0, 11.6599302, 0.0]
[25.0, 0.0, 11.6599302, 10.0]
[26.0, 11.6599302, 0.0, 10.0]
[27.0, 27.9121876, 27.9121876, 0.0]
[28.0, 27.9121876, 27.9121876, 10.0]
[29.0, 9.77920055, 9.77920055, 0.0]
[30.0, 9.77920055, 9.77920055, 10.0]]
Y -List of 10 elements
[1.0, 25.0, 0.0, 0.0]
[2.0, 0.0, 25.0, 0.0]
[11.0, 0.0, 0.0, 0.0]
[13.0, 17.6776695, 17.6776695, 0.0]
[14.0, 0.0, 34.3113632, 0.0]
[17.0, 34.3113632, 0.0, 0.0]
[23.0, 11.6599302, 0.0, 0.0]
[24.0, 0.0, 11.6599302, 0.0]
[27.0, 27.9121876, 27.9121876, 0.0]
[29.0, 9.77920055, 9.77920055, 0.0]
------------------------------------------------------------------------------------------------------------------------------------------Z list (X-Y) the result should be 20 elements but its gives length as 23 elements. it does not remove the remaining 3 elements from the list.




[[3.0, 0.0, 50.0, 0.0],
 [4.0, 50.0, 50.0, 0.0],
 [5.0, 50.0, 0.0, 0.0],
 [6.0, 0.0, 25.0, 10.0],
 [7.0, 25.0, 0.0, 10.0],
 [8.0, 50.0, 0.0, 10.0],
 [9.0, 50.0, 50.0, 10.0],
 [10.0, 0.0, 50.0, 10.0],
 [12.0, 0.0, 0.0, 10.0],
 [15.0, 25.9780293, 50.0, 0.0],
 [16.0, 50.0, 25.9780293, 0.0],
 [18.0, 17.6776695, 17.6776695, 10.0],
 [19.0, 34.3113632, 0.0, 10.0],
 [20.0, 50.0, 25.9780293, 10.0],
 [21.0, 25.9780293, 50.0, 10.0],
 [22.0, 0.0, 34.3113632, 10.0],
 [24.0, 0.0, 11.6599302, 0.0],
 [25.0, 0.0, 11.6599302, 10.0],
 [26.0, 11.6599302, 0.0, 10.0],
 [27.0, 27.9121876, 27.9121876, 0.0],
 [28.0, 27.9121876, 27.9121876, 10.0],
 [29.0, 9.77920055, 9.77920055, 0.0],
 [30.0, 9.77920055, 9.77920055, 10.0]]

Answer 1

如果我理解正确，请使用 bisect.bisect_left 查找匹配项并删除：

from bisect import bisect_left

for ele in y:
    ind = bisect_left(x, ele)
    if ind < len(x) -1 and x[ind][0] == ele[0]:
        del x[ind]

如果您查看 source，您可以看到用于 bisect_left 的代码：

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

您可以将其改编成您自己的代码：

def intersection(x, y):
    for ele in y:
        lo = 0
        hi = len(x)
        while lo < hi:
            mid = (lo+hi)//2
            if x[mid] < ele:
                lo = mid+1
            else:
                hi = mid
        if lo < len(x) - 1 and x[ind][0] == ele[0]:
            del x[lo]
    return x

print(len(intersection(x,y)))
20

如果你有欺骗，那么你将需要使用删除。检查第一个元素是否完全匹配是 if lo < len(x) - 1 and x[ind][0] == ele[0]: 但是如果你使用 remove 我不明白它是如何工作的，只是因为第一个元素匹配并不意味着 y[i] 在 x 所以 x.remove 会失败。因此，如果您只匹配第一个元素，那么您可以更改逻辑并迭代 x 将每个子列表中的所有第一个元素放入一个集合中，并使用生成器表达式更新 x.

st = {sub[0] for sub in y}

x[:] = (sub for sub in x if sub[0] not in st)

Answer 2

二分法可行，但另一个简单的解决方案是使用 set:

y_set = set(tuple(v) for v in y)

请注意 list 必须变成不可变的东西。

现在简单地生成结果：

z = [v for v in x if tuple(v) not in y_set]

这可能看起来与您的初始解决方案非常相似，但此处的查找速度要快得多。

@StefanPochmann 有一个很好的观点，您可能希望将查找基于比整个向量更具体的内容，例如第一个元素。这个问题不是很清楚（只说明那些是排序的）。

Answer 3

如果可以使用第一个元素进行过滤：

ykeys = set(zip(*y)[0])
z = [s for s in x if s[0] not in ykeys]

Python 3个版本：

ykeys = set(list(zip(*y))[0])
ykeys = {s[0] for s in y}

如果仅仅通过第一个元素判断是不够的：

yset = set(map(tuple, y))
return [s for s in x if tuple(s) not in yset]

在我较弱的笔记本电脑上，通过测试您的尺寸，第一个解决方案大约需要 0.4 秒，第二个解决方案大约需要 1 秒。不足为奇，因为 set lookups average O(1)).

这是第三个版本，这个可能是最有趣的，因为它不仅让 Python 完成工作，而且它更接近您的预期，甚至更好：

yi, last = 0, len(y) - 1
z = []
for s in x:
    while s > y[yi] and yi < last:
        yi += 1
    if s != y[yi]:
        z.append(s)

这个走过x，"in parallel"走过y。类似于merge-sort的合并步骤。使用 yi 我们指向 y，并根据需要增加它。因此我们有总体线性时间，因为我们只从开始到结束走过 x，也从开始到结束走过 y。我的笔记本电脑为此花费了大约 0.6 秒，这比我的第二个解决方案更快！（将它与我的第一个解决方案进行比较是不公平的，因为那个解决方案只查看第一个元素）。

在 Python 中使用二进制搜索比较列表列表

Comparison of list of lists using Binary search in Python

python

list

binary-search