如何优化从混合分类列表提取品牌的递归函数？

现有一个混合品牌与分类的列表categories，示例如下：

categories = [
      # 品牌相关
      { "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" },
    
      # 分类相关
      { "id": "root", "parentCategoryId": None },
      { "id": "bark", "parentCategoryId": "rich" },
      { "id": "rich", "parentCategoryId": "sting" },
      { "id": "rich", "parentCategoryId": "sting" },
      { "id": "sting", "parentCategoryId": "root" },
    ]

需求是提取所有父节点链最终指向id为"brands"的根节点的对象。

原实现采用递归判断每个对象的父链，但每次查找父节点都需要遍历整个列表，当数据量达到数百条时，重复遍历导致性能低下，原代码如下：

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)

优化方案 #

方案一：预构建映射+从根节点遍历收集 #

核心思路是先把所有对象按ID存入字典实现O(1)查找，再从"brands"根节点出发，通过广度优先或深度优先遍历所有子节点，一次性收集所有品牌相关对象。

# 第一步：构建ID到对象的映射字典，O(n)时间
id_to_obj = {obj['id']: obj for obj in categories}

# 第二步：构建父ID到子对象列表的映射
parent_to_children = {}
for obj in categories:
    parent_id = obj['parentCategoryId']
    if parent_id not in parent_to_children:
        parent_to_children[parent_id] = []
    parent_to_children[parent_id].append(obj)

# 第三步：从brands根节点开始广度遍历所有子节点
brands = []
queue = [id_to_obj['brands']]

while queue:
    current = queue.pop(0)  # 广度优先用pop(0)，深度优先用pop()
    brands.append(current)
    # 把当前节点的所有子节点加入队列
    if current['id'] in parent_to_children:
        queue.extend(parent_to_children[current['id']])

print(brands)

方案二：带缓存的判断函数 #

如果需要保留逐个判断的逻辑，可以给is_brand函数添加缓存，避免重复判断同一个节点，同时用字典映射优化父节点查找。

# 构建ID到对象的映射
id_to_obj = {obj['id']: obj for obj in categories}
# 缓存已判断的节点结果
cache = {}

def is_brand(obj):
    obj_id = obj['id']
    # 先查缓存，避免重复计算
    if obj_id in cache:
        return cache[obj_id]
    
    if obj_id == 'brands' and obj['parentCategoryId'] is None:
        cache[obj_id] = True
        return True
    
    if obj_id == 'root':
        cache[obj_id] = False
        return False
    
    parent_id = obj['parentCategoryId']
    if parent_id is None:
        # 非brands/root的根节点，不属于品牌
        cache[obj_id] = False
        return False
    
    parent_obj = id_to_obj.get(parent_id)
    if not parent_obj:
        # 父节点不存在，标记为非品牌
        cache[obj_id] = False
        return False
    
    result = is_brand(parent_obj)
    cache[obj_id] = result
    return result

brands = [obj for obj in categories if is_brand(obj)]
print(brands)

优化说明 #

• 字典映射优化：将原O(n)的父节点查找降低为O(1)，大幅减少遍历次数
• 根节点遍历方案：仅遍历品牌相关的节点，无需处理所有分类节点，时间复杂度从O(n²)降到O(n)
• 缓存机制：避免重复判断同一个节点的父链，尤其适用于存在大量共享父节点的场景

内容的提问来源于stack exchange，提问作者Alex Pereira