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

Question

我试图寻找一个回应，但找不到一个，即使我肯定它一定是问过。不能搜索正确的短语。你知道吗

我的问题是，我有两个大的dict列表，并且正在尝试将列表A中的dict与列表B中的dict进行匹配，列表B中的dict对于某个特定键具有最接近的值，在本例中是timestamp。dict中的时间戳可能完全相同，也可能不完全相同，我只想继续处理列表A中的dict，如果它与列表B中的匹配，并且时间戳值在其时间戳的15之内。此外，字典的结构也不完全相同，但它们总是包含一个时间戳键值对。你知道吗

首先我尝试了类似的方法：

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不是最好的。我想了一个更好的方法来写代码，但不知道如何用pythonic的方式来写。你知道吗

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

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

但我不知道怎么写。你知道吗

或者有一种完全不同的方法来解决这个问题（我发现在python中总是有）

任何帮助都将不胜感激

Answer 1

下面的代码呢？它使用了两个带有“timestamp”数字的列表，而不是dicts，但是使用dicts只会稍微有点麻烦 复杂的问题-算法将保持不变。你知道吗

这里的想法是将两个指针指向a和b（ia和ib），然后查看ia和ib处的值是否足够接近，以便匹配。如果不是，那么如果差值为正，就意味着a中的值比b中的值要远得多，ib必须追赶。如果差距是负的，那么情况就相反了，ia必须要跟上。你知道吗

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都可以与b列表中的3匹配，但是所给出的算法会在值与另一个列表中的伙伴匹配后将其从竞争中剔除。你可以通过改变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是list a的长度，m是list b的长度，您很容易看到这种情况，因为在while循环的每次迭代中，ia或ib都会提前1。你知道吗

我认为，如果您想为列表a中的每个时间戳找到最接近的匹配项，那么您不可能比O（n+m）做得更好