我有一個類別物件串列，如下面的串列。這個串列的問題是我混合了類別和品牌，我只需要從這個串列中獲取品牌。
我知道哪些是品牌，因為如果我在 parentCategoryIds 中導航，我將獲得根父項（即 id:brands，parentCategoryId:None）
categories = [
#brands
{ "id": "brands", "parentCategoryId": None },
{ "id": "ls", "parentCategoryId": "brands" },
{ "id": "bleed", "parentCategoryId": "brands" },
{ "id": "shape", "parentCategoryId": "brands" },
{ "id": "graze", "parentCategoryId": "brands" },
{ "id": "item", "parentCategoryId": "brands" },
{ "id": "install", "parentCategoryId": "brands" },
{ "id": "horror", "parentCategoryId": "brands" },
{ "id": "thanks", "parentCategoryId": "brands" },
{ "id": "scrape", "parentCategoryId": "brands" },
{ "id": "shelter", "parentCategoryId": "brands" },
{ "id": "dynamic", "parentCategoryId": "brands" },
{ "id": "under", "parentCategoryId": "shape" },
{ "id": "right", "parentCategoryId": "shape" },
{ "id": "base", "parentCategoryId": "shape" },
{ "id": "scrap", "parentCategoryId": "shape" },
# categories
{ "id": "root", "parentCategoryId": None },
{ "id": "bark", "parentCategoryId": "rich" },
{ "id": "rich", "parentCategoryId": "sting" },
{ "id": "rich", "parentCategoryId": "sting" },
{ "id": "sting", "parentCategoryId": "root" },
]
為了解決這個問題，我寫了下面的函式。但是我認為它會很慢，因為這個串列只是一個例子，原始串列有數百條記錄。
在這個函式中，我在父母中導航，直到找到根（如果根 == 品牌，我知道我有一個品牌，所以我可以添加到一個單獨的串列中；如果沒有，我就忽略）。
我想知道我是否可以做得更好，所以如果我通過更大的串列，那將不是問題。
brands = []
def getParent(id):
for obj in categories:
if obj['id'] == id:
return obj
def is_brand(obj):
if obj['id'] == 'brands' and obj['parentCategoryId'] == None:
return True
if obj['id'] == 'root':
return False
if not obj['parentCategoryId'] == None:
return is_brand(getParent(obj['parentCategoryId']))
for obj in categories:
if is_brand(obj):
brands.append(obj)
print(brands)
uj5u.com熱心網友回復：
改善is_brand()的資源消耗看起來解決了一個XY 問題。
你呈現它的方式，它可能會像這樣簡單地避免
brands = [
{ "id": "brands", "parentCategoryId": None },
{ "id": "ls", "parentCategoryId": "brands" },
…
{ "id": "scrap", "parentCategoryId": "shape" },
]
non_brands = [
# categories
{ "id": "root", "parentCategoryId": None },
{ "id": "bark", "parentCategoryId": "rich" },
…
]
categories = brands non_brands
有品牌和類別，由屬性id和parentCategoryId描述。將品牌
建模為（Python）物件：如果對品牌和類別
有責任，則應該有一個共同的基類：
class node:
""" Each node has a unique non-None id and a parent. """
def __init__(self, node_id, parent=None):
if node_id is None:
raise hell # handling "unique" left as an exercise
self.id = node_id # note the syntax decoration
self.parent = parent
def is_brand(self):
return False # isinstance(self, brand)
class brand(node):
""" A brand is a node with root category "brands". """
def is_brand(self):
return True
class category(node):
""" A category is a node with root category "root". """
pass
uj5u.com熱心網友回復：
這具有更好的時間復雜度 O(n * m) 其中 m 是該圖的最大深度，如果我計算正確，您的時間復雜度是 O(n^2*m)。
def get_brands():
brands = []
lookup_categories = dict([(category['id'], category['parentCategoryId']) for category in categories])
for id, parent in lookup_categories.items():
if id == 'brands':
brands.append(id)
continue
while parent is not None and parent != 'brands':
parent = lookup_categories[parent]
if parent:
brands.append(id)
return brands
我正在考慮的另一種方法是使用不相交集，但我在 python 中找不到具有該資料結構的內置庫。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514854.html
標籤：Python算法递归