python - 我可以在没有嵌套循环的情况下根据元组的元素比较两组元组吗？

Question

我有以下代码:

ChangedLinks = set(NewLinkData) - set(OldLinkData)
ReplaceQueue = []
LinkUpdateTokenID = 0
for ChangedLink in ChangedLinks:
    for OldLink in OldLinkData:
        if ChangedLink[0] is OldLink[0]:
            ReplaceStrings = (OldLink[1], "<<LINK UPDATE TOKEN " + str(LinkUpdateTokenID) + ">>", ChangedLink[1])
            ReplaceQueue.append(ReplaceStrings)
    LinkUpdateTokenID += 1

ChangedLinks 是一组元组，OldLinkData 是一个元组列表。

随着 ChangedLinks 和 OldLinkData 的长度增加，该方法的性能明显下降，因为当然有；那只是纯粹的数学!从用户的角度来看，它实际上是瞬时的，但要花费大量的时间(尽管不到一秒，至少在我的机器上是这样)。

仅当我可以将 OldLinkData 中的元组的第一个元素作为与ChangedLinks 中的元组。 (这些元组元素在它们各自的列表中是唯一的，例如，OldLinkData[0][0] 在 OldLinkData 的所有其他成员中是唯一的，对于 OldLinkData[1][0]，等等。)我能想到的唯一方法是像上面的代码一样遍历每个集合/列表并比较元组元素。

有没有更有效的方法来做到这一点？理想情况下，我想要一些方法来快速构建一个仅包含 OldLinkData 成员的列表，这些成员与 ChangedLinks 的成员之一共享其第一个元素，顺序与ChangedLinks，这样我就可以并排比较列表。但我不知道如何开始解决这个问题。

编辑:预期输入和输出的一些示例:

OldLinkData:  [(<Page.Page object at 0x035AF070>, ']([0])'), (<Page.Page object at 0x043FE4F0>, ']([0, 0])'), (<Page.Page object at 0x043FE590>, ']([0, 0, 0])'), (<Page.Page object at 0x043FE5B0>, ']([0, 1])')]

NewLinkData:  [(<Page.Page object at 0x035AF070>, ']([0])'), (<Page.Page object at 0x043FE5B0>, ']([0, 0])'), (<Page.Page object at 0x043FE4F0>, ']([0, 1])'), (<Page.Page object at 0x043FE590>, ']([0, 1, 0])')]

ChangedLinks:  {(<Page.Page object at 0x043FE590>, ']([0, 1, 0])'), (<Page.Page object at 0x043FE5B0>, ']([0, 0])'), (<Page.Page object at 0x043FE4F0>, ']([0, 1])')}

ReplaceQueue:  [(']([0, 0, 0])', '<<LINK UPDATE TOKEN 0>>', ']([0, 1, 0])'), (']([0, 1])', '<<LINK UPDATE TOKEN 1>>', ']([0, 0])'), (']([0, 0])', '<<LINK UPDATE TOKEN 2>>', ']([0, 1])')]

要清楚，这是在工作代码中从控制台打印的实际输入和输出。我正在寻找一种比当前代码更有效地实现相同结果的方法。

OldLinkData 和 NewLinkData 中的元组具有以下形式:

(Page.Page object at X, String)

该代码的目的是生成 ReplaceQueue，这是一个包含旧值和新值的列表，用于替换一系列字符串(分层笔记本中的页面内容)中的子字符串。 ReplaceQueue 的内容必须缩小到内存中相同的 Page.Page 对象有两个不同的关联“链接”(整数索引路径的字符串表示，包裹在一些markdown 语法)跨越 OldLinkData 和 NewLinkData。

OldLinkData 和NewLinkData 的区别是通过ChangedLinks 获取的set(NewLinkData) - set(OldLinkData)，但随后我需要在 ReplaceQueue 中将更改后的字符串相互关联。

LinkUpdateTokenID 整数只是一个中间步骤，因此我可以保证 str.replace 的参数是唯一的，并且不会在两个对象交换链接字符串时搞砸。

编辑:感谢@ParitoshSingh，以下代码明显更快:

def GetLinkData(self):
    LinkData = {}
    LinkData[id(self.RootPage)] = "](" + self.JSONSerializer.SerializeDataToJSONString(self.RootPage.GetFullIndexPath(), Indent=None) + ")"
    self.AddSubPageLinkData(self.RootPage, LinkData)
    return LinkData

def AddSubPageLinkData(self, CurrentPage, LinkData):
    for SubPage in CurrentPage.SubPages:
        LinkData[id(SubPage)] = "](" + self.JSONSerializer.SerializeDataToJSONString(SubPage.GetFullIndexPath(), Indent=None) + ")"
        self.AddSubPageLinkData(SubPage, LinkData)

def UpdateLinks(self, OldLinkData, NewLinkData):
    ReplaceQueue = []
    for PageID in NewLinkData:
        if PageID in OldLinkData:
            if NewLinkData[PageID] != OldLinkData[PageID]:
                ReplaceStrings = (OldLinkData[PageID], "<<LINK UPDATE TOKEN" + str(PageID) + ">>", NewLinkData[PageID])
                ReplaceQueue.append(ReplaceStrings)
    for ReplaceStrings in ReplaceQueue:
        self.SearchWidgetInst.ReplaceAllInNotebook(SearchText=ReplaceStrings[0], ReplaceText=ReplaceStrings[1], MatchCase=True, DelayTextUpdate=True)
    for ReplaceStrings in ReplaceQueue:
        self.SearchWidgetInst.ReplaceAllInNotebook(SearchText=ReplaceStrings[1], ReplaceText=ReplaceStrings[2], MatchCase=True, DelayTextUpdate=True)

Answer 1

编辑:对于遇到与此类似问题的用户，请引用下面更通用的解决方案。此编辑仅解决 OP 的这个特定场景。
对于 OP，可以通过使用可散列值来加快查找速度。对于此特定用例，请尝试 id() function
警告:应牢记注意事项。 id 函数保证为同时存在的对象生成唯一值，但仅保证链接到 CPython 中的内存地址，其他实现可能不同。

OldLinkData = list(zip("123","abc"))
print(OldLinkData)
#[('1', 'a'), ('2', 'b'), ('3', 'c')]

NewLinkData = list(zip('1245','axyz'))
print(NewLinkData)
#[('1', 'a'), ('2', 'x'), ('4', 'y'), ('5', 'z')]


#code:

#Create a key value mapping based on the id of objects. 
OldLinkDataDict = {id(OldLink[0]): OldLink for OldLink in OldLinkData}
#{244392672200: ('1', 'a'), 244392672368: ('2', 'b'), 244420136496: ('3', 'c')}

ReplaceQueue = []
LinkUpdateTokenID = 0
for NewLink in NewLinkData:
    new_id = id(NewLink[0])
    if new_id in OldLinkDataDict: #only consider cases where NewLink exists in OldLinkData 
        if NewLink[1] != OldLinkDataDict[new_id][1]: #only when the value changes (similar to ChangedLinks)
            ReplaceStrings = (OldLinkDataDict[new_id][1],
                              "<<LINK UPDATE TOKEN " + str(LinkUpdateTokenID) + ">>",
                              NewLink[1])
            ReplaceQueue.append(ReplaceStrings)
            LinkUpdateTokenID += 1
print(ReplaceQueue)
#[('b', '<<LINK UPDATE TOKEN 0>>', 'x')]

如果您好奇的话，这个演示之所以有效，是因为 python 缓存了小数字的 int 对象。 [-5 to 256]

---

通用解决方案

如果您的比较对象是可散列的，您可以通过将 OldLinkData 的数据类型更改为字典来获得很好的 yield 。 Link to Docs .因为字典键是可哈希的，所以字典查找是一个常数时间操作 O(1)，不需要在字典中迭代。

#Dummy data
OldLinkData = list(zip("123","abc"))
print(OldLinkData)
#[('1', 'a'), ('2', 'b'), ('3', 'c')]

NewLinkData = list(zip('1245','axyz'))
print(NewLinkData)
#[('1', 'a'), ('2', 'x'), ('4', 'y'), ('5', 'z')]


#code:
#ChangedLinks = set(NewLinkData) - set(OldLinkData) #Remove this, set creation requires an iteration anyways   
OldLinkDataDict = dict(OldLinkData)
print(OldLinkDataDict)
#{'1': 'a', '2': 'b', '3': 'c'}

ReplaceQueue = []
LinkUpdateTokenID = 0
for NewLink in NewLinkData:
    if NewLink[0] in OldLinkDataDict: #only consider cases where NewLink exists in OldLinkData 
        if NewLink[1] != OldLinkDataDict[NewLink[0]]: #only when the value changes (similar to ChangedLinks)
            ReplaceStrings = (OldLinkDataDict[NewLink[0]],
                              "<<LINK UPDATE TOKEN " + str(LinkUpdateTokenID) + ">>",
                              NewLink[1])
            ReplaceQueue.append(ReplaceStrings)
            LinkUpdateTokenID += 1
print(ReplaceQueue)
#[('b', '<<LINK UPDATE TOKEN 0>>', 'x')]

一些比较。请注意，理想情况下，您应该只创建一次字典，但我将其包含在时间比较中，以防您无法永久更改 OldLinkData 的数据类型。在这种情况下，您只需根据需要创建用于比较的字典。

OldLinkData = list(zip("123","abc"))
NewLinkData = list(zip('1245','axyz'))

基线

%%timeit
ChangedLinks = set(NewLinkData) - set(OldLinkData)
ReplaceQueue = []
LinkUpdateTokenID = 0
for ChangedLink in ChangedLinks:
    for OldLink in OldLinkData:
        if ChangedLink[0] is OldLink[0]:
            ReplaceStrings = (OldLink[1], "<<LINK UPDATE TOKEN " + str(LinkUpdateTokenID) + ">>", ChangedLink[1])
            ReplaceQueue.append(ReplaceStrings)
    LinkUpdateTokenID += 1

新代码

%%timeit
OldLinkDataDict = dict(OldLinkData)
ReplaceQueue = []
LinkUpdateTokenID = 0
for NewLink in NewLinkData:
    if NewLink[0] in OldLinkDataDict: #only consider cases where NewLink exists in OldLinkData 
        if NewLink[1] != OldLinkDataDict[NewLink[0]]: #only when the value changes (similar to ChangedLinks)
            ReplaceStrings = (OldLinkDataDict[NewLink[0]],
                              "<<LINK UPDATE TOKEN " + str(LinkUpdateTokenID) + ">>",
                              NewLink[1])
            ReplaceQueue.append(ReplaceStrings)
            LinkUpdateTokenID += 1

基线:每个循环 2.16 µs ± 52.6 ns(7 次运行的平均值 ± 标准偏差，每次 100000 次循环)

NewCode:每个循环 1.62 µs ± 98.4 ns(7 次运行的平均值 ± 标准偏差，每次 1000000 次循环)