table [使用 python 列表/词典] 中两列之间的递归关系搜索

Question

我正在尝试优化我创建的解决方案，以查找 table 中两列之间的递归关系。我需要找到一个 bssID 的所有 accID，并递归地找到这些 accID 的所有 bssID，依此类推，直到找到所有相关的 bssID。

bssIDs	accIDs
ABC	4424
ABC	56424
ABC	2383
A100BC	2383
A100BC	4943
A100BC	4880
A100BC	6325
A100BC	4424
XYZ	123

以下解决方案适用于 10 万行的初始 table，但对于 2000 万行的数据集，以下解决方案运行时间超过 16 小时。我正在尝试使用字典而不是列表，但我无法在迭代时更改字典，就像我使用列表一样。

import time

accIds = {4880: ['A100BC'], 6325: ['A100BC'], 2383: ['A100BC','ABC'],4424: ['A100BC','ABC'], 4943: ['A100BC'], 56424: ['ABC'],123: ['XYZ']}

bssIds = {'ABC': [4424,56424,2383], 'A100BC': [2383,4943,4880,6325,4424], 'XYZ':[123]}

def findBIDs(aID):
    return accIds[aID]
def findAIDs(bID):
    return bssIds[bID]
def getList(Ids):
    return Ids.keys()
def checkList(inputList, value):
    return (value in inputList)
def addToList(inputList, value):
    return inputList.append(value)
def removeFromList(inputList, value):
    return inputList.remove(value)
    
aIDlist = list(getList(accIds))
bIDlist = list(getList(bssIds))
bRelations = {}
runningList = list()
for x in bIDlist:
    if not checkList(runningList,x):
        aList = list()
        bList = list()
        addToList(bList, x)
        for y in bList:
            for c in findAIDs(y):
                if not checkList(aList, c):
                    addToList(aList, c)
            for z in aList:
                for a in findBIDs(z):
                    if not checkList(bList, a):
                        addToList(bList, a)
        bRelations.update({time.time_ns(): bList}) 
        runningList.extend(bList)
print(bRelations)

Output : {1652374114032173632: ['ABC', 'A100BC'], 1652374114032180888: ['XYZ']}

请建议是否有一种方法可以在迭代时更新字典，或者我们是否可以对其应用递归解决方案。

Answer 1

这是我能想到的最快的速度：

accIds = {4880: frozenset(['A100BC']), 6325: frozenset(['A100BC']), 2383: frozenset(['A100BC','ABC']),4424: frozenset(['A100BC','ABC']), 4943: frozenset(['A100BC']), 56424: frozenset(['ABC']),123: frozenset(['XYZ'])}
bssIds = {'ABC': frozenset([4424,56424,2383]), 'A100BC': frozenset([2383,4943,4880,6325,4424]), 'XYZ':frozenset([123])}

def search_bssid(bssId):
    traversed_accIds = set()
    traversed_bssIds = {bssId}
    accIds_to_check = []
    bssIds_to_check = [bssId]
    while bssIds_to_check:
        bssId = bssIds_to_check.pop()
        new_accids = bssIds[bssId] - traversed_accIds
        traversed_accIds.update(new_accids)
        accIds_to_check.extend(new_accids)
        while accIds_to_check:
            accId = accIds_to_check.pop()
            new_bssids = accIds[accId] - traversed_bssIds
            traversed_bssIds.update(new_bssids)
            bssIds_to_check.extend(new_bssids)
    return traversed_bssIds

print(search_bssid("ABC"))

table [使用 python 列表/词典] 中两列之间的递归关系搜索

Recursive relations search between 2 columns in a table [Using python list / Dict]

python

optimization