我有由父代码构成的树状数据,其中包含子代码,这些子代码本身可以充当父代码,具体取决于它们是否被标记为“ SA”。此数据显示在Excel工作表中,如下所示:
| Tree Level (A) | Code (B) | Spec (C) | Comm. Code (D) | Parent Code (J) |
|----------------|----------|----------|----------------|-----------------|
| 1 | A12 | 1 | SA | Mach |
| 2 | B41 | 2 | SA | A12 |
| 3 | A523 | 1 | BP | B41 |
| 2 | G32 | 4 | BP | A12 |
| 2 | D3F5 | 1 | SA | A12 |
| 3 | A12 | 4 | SA | D3F5 |
| 3 | A12 | 1 | SA | D3F5 |
这里有一个问题:在最高树级别(1)的A12包含一个子项(D3F5),该子项本身包含另一个父项,该父项与D3F5自己的父项相同。您可能可以想象,这(尽管在传递给我时未在数据中表示)创建了一个无限循环,其中树级别3的A12一次又一次地展开整个结构。
请注意,两个'A12'子级之一没有问题,因为对于树级别1的A12父级有不同的规范。
我有一个检查这种情况的函数,但是它非常慢,因为它使用嵌套循环遍历行,并且总行数可能是几千个:
def nested_parent(sht):
"""
Checks if a parent SA contains itself as a child.
:return: nested_parents: Dictionary of found 'nested parents'. None if none found
"""
nested_parents = {}
found = False
lrow = sht.Cells(sht.Rows.Count, 1).End(3).Row
parent_treelevel = 1
# Get deepest tree level, as this no longer contains children
last_treelevel = int(max([i[0] for i in sht.Range(sht.Cells(2, 1), sht.Cells(lrow, 1)).Value]))
# Loop through parent rows
print('Checking for nested parents...')
for i in range(2, lrow):
if sht.Cells(i, "D").Value == "SA":
parent_code, parent_treelevel = f'{sht.Cells(i, "B").Value}_{sht.Cells(i, "C")}', sht.Cells(i, "A").Value
# Add new key with list containing parent's tree level for parent code
if parent_code not in nested_parents:
nested_parents[parent_code] = [int(parent_treelevel)]
# Loop child rows
for j in range(i + 1, lrow + 1):
child_code, child_treelevel = f'{sht.Cells(j, "B").Value}_{sht.Cells(j, "C")}', sht.Cells(i, "A").Value
if child_code == parent_code and child_treelevel > parent_treelevel:
found = True
nested_parents[parent_code].append(int(child_treelevel))
if parent_treelevel == last_treelevel:
# End function if deepst tree level is reached
print("done")
if found:
# Delete keys that contain no information
delkeys = []
for key in reversed(nested_parents):
if len(nested_parents[key]) == 1:
delkeys.append(key)
for key in delkeys:
del nested_parents[key]
return nested_parents
else:
return
此函数可以如下调用,其中wb_name
是包含数据的工作簿的名称:
from win32com.client import GetObject
wb_name = "NAME"
sht = GetObject(None, "Excel.Application").Workbooks(wb_name).Worksheets(1)
def err(msg):
"""
stops the code from executing after printing an error message
"""
print("Unexpected error occured:", msg)
exit()
infloop = nested_parent(sht)
if infloop is not None:
dict_str = ''.join([f'Code: {key}, Tree levels: {infloop[key]}\n' for key in infloop])
err(f"Warning: one or more parent codes contain their own code as a child:\n{dict_str}")
我希望加快这段代码的速度,因为我的脚本的其余部分相当快,并且此功能严重阻碍了它的速度。
如@ a'r所述,您的“树状数据”可以看作是有向图,即与箭头(有向边)相连的点(节点)。有一个非常强大的库networkx
,可以很好地处理图形。在不深入图论的情况下,请考虑以下代码示例:
import networkx as nx
edges = [ ('A12', 'Mach'),
('B41', 'A12'),
('A523','B41'),
('G32', 'A12'),
('D3F5','A12'),
('A12', 'D3F5'),
('A12', 'D3F5') ]
G = nx.DiGraph(edges)
cycles_list = list(nx.simple_cycles(G))
print(cycles_list)
输出:
[['A12', 'D3F5']]
这里,节点名称是您阅读时的代码本身,边缘是子代与父代之间的连接。您只需采用Excel文件的相应列即可轻松创建边列表。在这种情况下,确切的方向(父母对孩子或反之亦然)不是很重要,只需保持一致即可。
simple_cycles
返回一个生成器。在这里可以找到documentation。
我希望此响应将有助于证明分层数据结构的强大功能。我要做的是将数据重写为json字符串,然后编写代码遍历层次结构并生成报告。您仍然需要将excel转换为json的任务。要点是json的每个级别都具有相同的键,并且子级中的每个子级都与其父词典具有相同的键,因此使递归函数能够遍历该结构。我按代码或级别汇总了示例。
import json
json_data = """
{
"level": 0,
"code": "Mach",
"children": [
{
"level": 1,
"code": "A12",
"children": [
{
"level": 2,
"code": "B41",
"children": [
{
"level": 3,
"code": "A523",
"children": []
}
]
},
{
"level": 2,
"code": "G32",
"children": []
},
{
"level": 2,
"code": "D3F5",
"children": [
{
"level": 3,
"code": "A12",
"children": []
},
{
"level": 3,
"code": "A12",
"children": []
}
]
}
]
}
]
}
"""
data = json.loads(json_data)
def crawl_levels(mydict, result={}):
try:
result[mydict["level"]].append(mydict["code"])
except:
result[mydict["level"]] = [mydict["code"],]
for i in mydict["children"]:
result = crawl_levels(i, result=result)
return result
crawl_levels(data)
>>>{0: ['Mach'], 1: ['A12'], 2: ['B41', 'G32', 'D3F5'], 3: ['A523', 'A12', 'A12']}
def crawl_codes(mydict, result={}):
try:
result[mydict["code"]].append(mydict["level"])
except:
result[mydict["code"]] = [mydict["level"],]
for i in mydict["children"]:
result = crawl_codes(i, result=result)
return result
crawl_codes(data)
>>>{'Mach': [0],
'A12': [1, 3, 3],
'B41': [2],
'A523': [3],
'G32': [2],
'D3F5': [2]}