python - 以更快/更好的方式从列表中查找具有最接近值的字典

Question

我尝试寻找对此的回应，但找不到回应，尽管我确信以前肯定有人问过这个问题。不得搜索正确的短语。

我的问题是我有两个大的字典列表，并且正在尝试将列表 A 中的字典与列表 B 中具有特定键最接近值的字典进行匹配，在本例中为 timestamp 。字典中的时间戳可能完全相同，也可能不完全相同，并且我只想在列表 A 中的字典与列表 B 中的时间戳值在其时间戳的 15 以内的匹配项时继续对列表 A 中的字典进行操作。此外，字典的结构并不相同，但都始终包含时间戳键值对。

首先我尝试了类似的东西:

for itemA in ListA:
    closestItemB = min(ListB, key=lambda x :abs(x["timestamp"])-int(itemA["timestamp"))
    if(abs(itemA['timestamp'] - closestItemB['timestamp']) < 15:
        #write info from both dicts to a csv file

对于大型列表来说，这极其慢。然后我意识到列表都是按时间戳排序的，因此应该可以显着加快速度

我的思维过程是在第一次循环中搜索整个列表 B 中最接近的，然后下一次仅搜索最后一个匹配的 listB 索引之外的一小部分。在 99% 的情况下，列表 A 中的下一个项目与列表 B 中接下来的几个项目之一相匹配。但有时它们不会，在这种情况下，我再次搜索到列表 B 的末尾，寻找最接近的匹配项，然后转到再次返回搜索小切片，直到下一次错过。

for itemA in listA:
    closestItemB = min(listB[lastFoundIndex:lastFoundIndex+3, key=lambda x :abs(x["timestamp"])-int(itemA["timestamp"))
    if(abs(itemA['timestamp'] - closestItemB['timestamp']) < 15:
        lastFoundIndex = listB.index(closestItemB)
        #write info from both dicts to a csv file
    else:
        closestItemB = min(listB[lastFoundIndex:len(listB)-1, key=lambda x :abs(x["timestamp"])-int(itemA["timestamp"))
        if(abs(itemA['timestamp'] - closestItemB['timestamp']) < 15:
            lastFoundIndex = listB.index(closestItemB)
            #write info from both dicts to a csv file

这比第一次迭代要快，但没有我预期的那么快。有趣的是，它在运行时寻找匹配的速度变得越来越慢。我猜测这可能与列表切片的工作方式有关，因为我不完全确定幕后发生了什么。

你可能会说我的 python 不是最好的。我想到了一种更好的方法来编写代码，但不知道如何以Python方式编写。

我想要做的是搜索列表 B，直到列表 A 和列表 B 的时间戳差异的符号翻转，此时最后检查的两项之一必须最接近列表 a。然后，对于 listA 中的下一项，我可以做同样的事情，但是从列表 B 中我刚刚找到匹配项的索引开始。此代码将替换以下行:

closestItemB = min(listB[lastFoundIndex:lastFoundIndex+3, key=lambda x :abs(x["timestamp"])-int(itemA["timestamp"))

但是我不知道怎么写。

或者可能有一种完全其他的方法来解决这个问题(我发现当涉及到Python时总是有这种方法)

任何帮助将不胜感激

Answer 1

下面的代码怎么样？它使用两个带有“时间戳”数字的列表而不是字典，但使用字典只会稍微 让事情变得复杂 - 算法将保持不变。

这里的想法是让两个指针指向 a 和 b(ia 和 ib)，并查看 ia 和 ib 处的值是否足够接近以进行匹配。如果不是，那么如果差异为正，则意味着 a 中的值比 b 中的值领先得多，并且 ib 必须追赶。如果差异为负，则相反，ia 必须迎头 catch 。

a = [1, 4, 35, 40, 56, 70, 90, 110 ]
b = [3, 20, 39, 57, 62, 84, 100, 150]

ia = 0
ib = 0
while ia < len(a) and ib < len(b):
    delta = a[ia] - b[ib]
    if abs(delta) <= 15:
        print("Found match at ia={} ({}) and ib={} ({})".format(ia, a[ia], ib, b[ib]))
        # Both items are matched, continue with the next ones 
        ia += 1
        ib += 1
    elif delta > 15:
        # we're too far behind in the b list, try to catch up
        ib += 1
    elif delta < -15:
        # too far behind in the a list, try to catch up 
        ia += 1

请注意，我不确定如何处理一个列表中的两个值可能与第二个列表中的一个匹配的情况 - 例如，a 列表中的 1 和 4 都可以与列表中的 3 匹配b 列表，但是一旦与另一个列表中的合作伙伴匹配，所提供的算法就会从比赛中取出一个值。您可以通过更改找到匹配项后 ia 和 ib 发生的情况来更改此情况。

以下代码找到所有可能的匹配项(我认为)，仍然只需要一次迭代(但不会将匹配项添加到候选列表中以找到最佳匹配项:

a = [1, 4, 35, 40, 56, 70, 90, 110 ]
b = [3, 20, 39, 57, 62, 84, 100, 150]

ia = 0
ib = 0
while ia < len(a) and ib < len(b):
    delta = a[ia] - b[ib]
    if abs(delta) <= 15:
        print("Found match at ia={} ({}) and ib={} ({})".format(ia, a[ia], ib, b[ib]))
        if delta < 0:
           # there might be a better match yet for the timestamp at ib
           ia += 1
        elif delta > 0:
           # there might be a better match yet for the timestamp in ia
           ib += 1
        else:
           # perfect match, it won't get any better. Move along in both lists
           ia += 1
           ib += 1
    elif delta > 15:
        # we're too far behind in the b list, try to catch up
        ib += 1
    elif delta < -15:
        # too far behind in the a list, try to catch up 
        ia += 1

现在，如果您确实需要找到最佳(最接近)匹配，您的代码可能如下所示:

a = [1, 4, 35, 40, 56, 70, 90, 110 ]
b = [3, 20, 39, 57, 62, 84, 100, 150]

ia = 0
ib = 0
best_at = -1
best_diff = 10000
while ia < len(a) and ib < len(b):
    delta = a[ia] - b[ib]
    if abs(delta) <= 15:        
        print("Found match at ia={} ({}) and ib={} ({})".format(ia,  a[ia], ib, b[ib]))
        if abs(delta) < best_diff:
            best_at = ib
            best_diff = abs(delta)                   
        if delta < 0:
            if best_diff < 10000:
                print("Best match for {} is {} at ib={}".format(a[ia], b[best_at], best_at))
                best_diff = 10000
            ia += 1            
        elif delta > 0:
            ib += 1
        else:
            # perfect match
            print("Best match for {} is {} at ib={}".format(a[ia], b[best_at], best_at))
            best_diff = 10000
            ia += 1
            ib += 1

    elif delta > 15:
        ib += 1
    elif delta < -15:
        if best_diff < 10000:
            print("Best match for {} is {} at ib={}".format(a[ia], b[best_at], best_at))
            best_diff = 10000
        ia += 1

这仍然以线性时间运行。时间复杂度大致为 O(n+m)，其中 n 是列表 a 的长度，m 是列表 b 的长度，你可以很容易地看到这就是这种情况是因为在 while 循环的每次迭代中，ia 或 ib 都会提前 1。

如果你想为列表 a 中的每个时间戳找到最接近的匹配，我认为你不能做得比 O(n+m) 更好。