Can I compare two sets of tuples based on the elements of the tuples without nested looping?

Question

I have the following code:

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], "<>", ChangedLink[1])
            ReplaceQueue.append(ReplaceStrings)
    LinkUpdateTokenID += 1

ChangedLinks is a set of tuples, and OldLinkData is a list of tuples.

There is a noticeable dip in the performance of the method this is in as the lengths of ChangedLinks and OldLinkData increase, because of course there is; that's just sheer math! It goes from effectively instantaneous from the user perspective to taking a noticeable amount of time (though less than a second, at least on my machine).

I need to add a new element to the ReplaceQueue list only when I can match the first element of a tuple in OldLinkData as the same object as the first element of a tuple in ChangedLinks. (These tuple elements are unique within their respective lists, as in, OldLinkData[0][0] is unique among all other members of OldLinkData, and the same for OldLinkData[1][0], and so on.) The only way I can think of to accomplish this is to loop through each set/list as in the code above and compare the tuple elements.

Is there a more efficient way to do this? Ideally I'd like some way to quickly construct a list of only the members of OldLinkData which share their first element with one of the members of ChangedLinks, in the same order as ChangedLinks, so that I can just compare the lists side-by-side. But I have no idea how to begin solving this issue.

Edit: Some examples of expected input and output:

OldLinkData:  [(, ']([0])'), (, ']([0, 0])'), (, ']([0, 0, 0])'), (, ']([0, 1])')]

NewLinkData:  [(, ']([0])'), (, ']([0, 0])'), (, ']([0, 1])'), (, ']([0, 1, 0])')]

ChangedLinks:  {(, ']([0, 1, 0])'), (, ']([0, 0])'), (, ']([0, 1])')}

ReplaceQueue:  [(']([0, 0, 0])', '<>', ']([0, 1, 0])'), (']([0, 1])', '<>', ']([0, 0])'), (']([0, 0])', '<>', ']([0, 1])')]

To be clear, this is actual input and output as printed from the console in the working code. I'm looking for a way to achieve this same result more efficiently than the current code.

The tuples in OldLinkData and NewLinkData are of the form:

(Page.Page object at X, String)

The purpose of the code is to produce ReplaceQueue, a list of old and new values for replacing substrings throughout a series of strings (the page contents in a hierarchical notebook). ReplaceQueue's content has to be narrowed to cases where the same Page.Page object in memory has two different associated "links" (string representations of integer index paths wrapped in some markdown syntax) across OldLinkData and NewLinkData.

The difference between OldLinkData and NewLinkData is obtained with ChangedLinks as set(NewLinkData) - set(OldLinkData), but then I need to associate the changed strings with each other in ReplaceQueue.

The LinkUpdateTokenID integer is just an intermediate step so that I can guarantee unique parameters for str.replace and not muck things up when two objects swap link strings.

Edit: Thanks to @ParitoshSingh, the following code is noticeably faster:

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], "<>", 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)

user_10618540 · Answer

EDIT: For users looking at a similar problem to this, please refer to a more generic solution below. This edit only addresses this specific scenario for the OP.
To the OP, The lookups can be sped up by using hashable values. For this specific use case, try the id() function
Warning: The caveats should be kept in mind. id function is guaranteed to produce unique values for objects that coexist at the same time, but is only guaranteed to be linked to memory address in CPython, other implementations may differ.

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],
                              "<>",
                              NewLink[1])
            ReplaceQueue.append(ReplaceStrings)
            LinkUpdateTokenID += 1
print(ReplaceQueue)
#[('b', '<>', 'x')]

If you're curious, this demonstration only works because python caches the int objects for small numbers. [-5 to 256]

Generalized Solution

You can see very good gains by changing your datatype of OldLinkData to a dictionary if your comparison objects are hashables. Link to Docs. Because dictionary keys are hashables, the dictonary lookups are a constant time operation O(1), and do not require iteration in the dictionary.

#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]],
                              "<>",
                              NewLink[1])
            ReplaceQueue.append(ReplaceStrings)
            LinkUpdateTokenID += 1
print(ReplaceQueue)
#[('b', '<>', 'x')]

Some comparison. Note that ideally you should only do the dictionary creation once, but i kept it included in the time comparison in case you can't get away with changing the datatype of OldLinkData permanently. In that case, you just would want to create the dictionary for comparison as needed.

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

BaseLine

%%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], "<>", ChangedLink[1])
            ReplaceQueue.append(ReplaceStrings)
    LinkUpdateTokenID += 1

NewCode

%%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]],
                              "<>",
                              NewLink[1])
            ReplaceQueue.append(ReplaceStrings)
            LinkUpdateTokenID += 1

BaseLine: 2.16 µs ± 52.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

NewCode: 1.62 µs ± 98.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Can I compare two sets of tuples based on the elements of the tuples without nested looping?

1 Answers