Vanilla JavaScript下高效获取指定父元素下符合要求的最接近后代.layout元素的优化方案咨询

[EDIT] 抱歉之前的表述不够清晰，希望更新后的问题更明确了！

我写了一个JS方法，用来从任意给定的DOM元素（可以是body、div或者任何带.layout类的元素）开始，按层级从高到低获取所有在DOM层级中最先找到的.layout元素。

需求的核心是：遍历给定父元素（下文称parent）的整个DOM树，列出每个分支里层级最高的.layout元素。返回的.layout元素必须满足：在parent的范围内，它没有任何带.layout类的祖先（但在parent范围之外，它可以有.layout的父元素或祖先）。

原实现代码 #

JavaScript

// Here’s my implementation:  
const getClosestDescendants = (parent) => {
  return [...parent.querySelectorAll('.layout')].filter(layout => {
    let closest = layout.parentNode?.closest('.layout');
    return closest == null || closest === parent || !parent.contains(closest);
  });
};

// Example 1 : root element without .layout class
let example1 = document.querySelector(".example-1");
console.log("Example 1", getClosestDescendants(example1));

// Example 2 : child element without .layout class
let example2 = document.querySelector(".example-2");
console.log("Example 2", getClosestDescendants(example2));

// Example 3 : .layout parent with direct and indirect children
let example3 = document.querySelector(".example-3");
console.log("Example 3", getClosestDescendants(example3));

// Example 4 : .layout parent without direct .layout child
let example4 = document.querySelector(".example-4");
console.log("Example 4", getClosestDescendants(example4));

CSS

.app {
  position: fixed;
  top: 0;
  left: 0;
  right: 0;
  bottom: 150px;
  padding: 30px;
  overflow: auto;
  display: flex;
  flex-direction: column;
}

.app div {
  padding: 10px;
  display: flex;
  flex-direction: column;
  gap: 10px;
  color: black;
  border-style: dashed;
  border-width: 3px;
  flex-shrink: 0;
}

.app .layout {
  border-style: solid;
  border-width: 3px;
  padding-top: 35px;
  position: relative;
}

.app .layout::after {
  content: "#" attr(id);
  position: absolute;
  top: 0;
  left: 0;
  color: white;
  background-color: black;
  padding: 5px;
}

.app .example-1 {
  border-color: red;
  color: red;
}

.app .example-2 {
  border-color: #cf0082;
  color: #cf0082;
}

.app .example-3 {
  border-color: #5900ff;
  color: #5900ff;
}

.app .example-3:after {
  background-color: #5900ff;
}

.app .example-4 {
  border-color: #208800;
  color: #208800;
}

.app .example-4:after {
  background-color: #208800;
}

HTML

<div class="app">
  Dashed border: Div element without .layout class <br>
  Solid border: Div element with .layout class <br>
  Colored border: Parent element given as example <br>
  <br>
  <div class="example-1">
    (Example 1 : root element without .layout class)
    <div class="layout" id="layout-1">
      Layout 1
      <div class="example-2">
        (Example 2 : child element without .layout class)
        <div>
          <div class="layout" id="layout-2"></div>
        </div>
      </div>
    </div>
    <div>
      <div class="layout example-3" id="layout-3">
        (Example 3 : .layout parent with direct and indirect children)
        <div class="layout" id="layout-4"></div>
        <div>
          <div class="layout example-4" id="layout-5">
            (Example 4 : .layout parent without direct .layout child)
            <div>
              <div class="layout" id="layout-6"></div>
            </div>
          </div>
          <div class="layout" id="layout-7"></div>
        </div>
      </div>
    </div>
    <div class="layout" id="layout-8"></div>
  </div>
</div>

原实现的性能小问题 #

咱们先聊聊原实现的短板：它先用querySelectorAll把parent底下所有.layout元素全捞出来，之后再逐个过滤。但如果DOM里有很多嵌套的.layout（比如layout-3下面套了layout-4、layout-5），querySelectorAll会把这些深层元素也都抓出来，然后每个元素还要往上查closest和contains，等于做了好多重复的DOM查询，在大DOM树里这就有点费性能了。

优化方案：遍历到目标就停，跳过子树 #

既然我们要找的是每个分支里最上层的.layout，那咱们遍历的时候，一旦碰到一个.layout元素，直接把它加入结果，然后跳过它的所有子树不就行了？因为子树里的.layout肯定都在它的范围内，不符合“最高层级”的要求呀。这样不用遍历所有后代，也不用每个元素都向上查，效率直接拉满！

优化后的代码实现：

const getClosestDescendantsOptimized = (parent) => {
  const result = [];
  const stack = [...parent.children];

  while (stack.length > 0) {
    const current = stack.pop();
    
    // 找到目标元素，加入结果后跳过子树
    if (current.classList.contains('layout')) {
      result.push(current);
      continue;
    }
    
    // 不是目标元素，倒序加入子节点（保证遍历顺序和原方法一致）
    if (current.children.length > 0) {
      stack.push(...Array.from(current.children).reverse());
    }
  }

  return result;
};

// 和原实现对比测试
let example1 = document.querySelector(".example-1");
console.log("Example 1 (Optimized)", getClosestDescendantsOptimized(example1)); // 返回 layout-1, layout-3, layout-8

let example2 = document.querySelector(".example-2");
console.log("Example 2 (Optimized)", getClosestDescendantsOptimized(example2)); // 返回 layout-2

let example3 = document.querySelector(".example-3");
console.log("Example 3 (Optimized)", getClosestDescendantsOptimized(example3)); // 返回 layout-4, layout-5, layout-7

let example4 = document.querySelector(".example-4");
console.log("Example 4 (Optimized)", getClosestDescendantsOptimized(example4)); // 返回 layout-6

优化思路说明 #

1. 用栈实现深度优先遍历，保证遍历顺序和原querySelectorAll的顺序一致
2. 遍历到.layout元素时，直接加入结果集，然后跳过它的子树（不用再遍历子节点）
3. 非.layout元素则将其子节点倒序加入栈，确保从左到右的遍历顺序和原方法匹配

性能对比 #

• 原方法：时间复杂度是O(N + M*K)，其中N是parent下所有.layout的数量，M是过滤的元素数，K是每个元素向上查询的层级数
• 优化方法：时间复杂度是O(P)，P是遍历到所有目标元素的路径节点数，在嵌套多的场景下，P远小于N，性能提升非常明显

备注：内容来源于stack exchange，提问作者Quentin