如何在触发最少的回流的情况下对DOM元素进行排序？

Question

如何在触发最少的回流的情况下对DOM元素进行排序？

5

我有以下示例。

<div class="parent">
  <div data-id="5"></div>
  <div data-id="2"></div>
  <div data-id="3"></div>
  <div data-id="1"></div>
  <div data-id="4"></div>
</div>

如果我想按升序（1,2,3,4,5）对这些 div 进行排序，通常会使用循环并将 div 按顺序附加到父 div 中。但是这意味着我总是要对 DOM 进行 5 次更改（不管 div 的顺序如何），每个 div 都需要一次。

但是，您可以使用 .insertBefore() 方法仅进行两次更改即可正确排序 div！

5,2,3,1,4
Insert 1 before 2
5,1,2,3,4
Insert 5 behind 4 (using .insertBefore() and .nextSibling)
1,2,3,4,5

问题1 通过仅对DOM进行2次更改，我认为会发生更少的回流，使“2次更改”排序操作比“5次更改”排序操作更快。这个正确吗？

问题2 什么样的方法/算法能够找出只插入1 before 2和5 behind 4的方法？

问题3（奖励） 这个“优化”的算法是否仍然比增加项的数量更快？范围10-100-1,000-10,000-100,000

可能需要澄清：我不是在寻找一种以最优方式确定顺序（1,2,3,4,5）。在某个时刻，我知道顺序，但我想将顺序与div的顺序进行比较，然后再找出最少的操作。

- Dex

我建议进一步阅读不同的排序算法，这个主题非常广泛，有很多在简单的网络搜索中都有解释和测试性能的算法。你的问题有点合理，但可能会有许多不同的答案。 - Kaddath

我尝试找一些排序算法，但是森林里有太多的树了 :) 我不知道这种类型的算法叫什么名字。你知道吗？ - Dex

3个回答

3

从DOM中删除所有节点，并在您的代码中对它们进行排序后按正确顺序替换它们。

HTML：

<div id="wrapper">
  <div id="par" class="parent">
    <div id="5">5</div>
    <div id="2">2</div>
    <div id="3">3</div>
    <div id="1">1</div>
    <div id="4">4</div>
  </div>
</div>

Javascript：

var clone = document.getElementById("par")
  .cloneNode(true)
var childs = [].slice.call(clone.children);
var sorted = childs.sort(function(a, b) {
  return parseInt(a.id) - parseInt(b.id)
})
var frag = document.createDocumentFragment();
sorted.forEach(function(el) {
  frag.appendChild(el)
})

var wrapper = document.getElementById("wrapper");
wrapper.removeChild(document.getElementById("par"));
wrapper.appendChild(frag);

说明：单个DOM操作比您排序算法中的算法步骤要重得多。

如果数字变得很大，最聪明的排序算法需要O(n log n)倍于节点数的时间。这意味着n * log（n）个DOM操作。用人类语言来说，这只是节点数量的几倍操作。

但是，如果您仅删除所有节点，然后以正确的顺序将它们添加回去，那么最差情况下只需要n + 1次DOM操作。可能您可以将所有节点一起添加，这样您会得到更接近2/ O(1)的数字，但是我不太了解现代浏览器实际上有多快执行此操作，因此让我们保守地使用n + 1。

现在看看数字：

假设您有5个节点。在这种情况下，一切都很好，数字很小，但为了您自己和同事的未来和平，您希望编写一个清晰的算法。因此，请删除所有节点并以正确的顺序替换它们。

现在假设你有1000个节点。在这种情况下，排序将需要约10000次操作（n * log n = 1000 * 10）**。如果你单独将每个节点放入其中，则会进行10000次DOM操作。

相反，如果你只是从DOM中删除节点，将它们在JavaScript代码中排序，然后再放回去，你只需要进行1000次DOM操作。这是相当保守的估计，因为我感觉实际上只需要2次DOM操作：一次删除所有节点，一次按正确顺序添加所有节点***

** 我更愿意给出具体数字，以使所有事情都有些意义。基于1024的2进制，即10 *** 这可能是真正的区别所在。如果有人知道，请评论/编辑！

- Sventies

我不太明白。在我看来，完全删除节点并重新构建它的“成本”比仅为其提供新位置（顺序）更高。按正确顺序附加它们比什么更快呢？ - Dex

1

当我开始编程时，我也有同样的感觉。我会尝试添加更多内容来使答案更易理解。请稍等。 - Sventies

好的，如果我理解正确的话，我需要删除所有5个div。然后再重新创建它们，并将它们按顺序放在parent下面？这似乎比仅仅使用优化的insertBefore()方法将它们按顺序放在parent下面还要复杂（而只使用.append()方法）。 - Dex

2

你不需要重新创建它们，只需按照你想要的顺序将元素附加到父级即可。 - Bellian

好的，所以1,000个节点唱歌需要10,000次操作？元素的顺序是1,000、1、2、3、4、5、6等...现在要正确排序，我只需要将数字1,000放在我的div的末尾。这只需要一次操作而不是10,000次。 - Dex

显示剩余6条评论

-1

请看一下这段代码。

基本上它会从 DOM 中移除容器，进行排序，然后重新插入到 DOM 中。

通常这一切都可以在一个帧重绘中完成，因此不会影响页面长度/滚动问题。

+function() {
  /**
   * Finding thing wrapping class
   */
  var $con = $('#container');
  /**
   * getting the parent of the wrapping class so we can reinsert when we're done.
   */ 
  var $parent = $con.parent();
  /**
   * Removing container from dom so we can sort in speed
   */   
  $con.remove();
  
  /**
   * Getting the things we need from container that we need to sort
   */
  var $tosort = $con.find('.thing');
  
  /**
   * Apply sorting algorything, get a newly sorted list
   */
  var $neworder = $tosort.sort(function(a,b){
     return parseInt(a.innerText) > parseInt(b.innerText);
  });
  /**
   * Simply append the newly ordered list. They are the same objects, not clones so they'll fit into the right order.
   */
  $con.append($neworder);
  /**
   * Reinsert container into the dom.
   */
  $parent.append($con);
}()

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="wrap">
  <div id="container">
    <div class="thing">
      4
    </div>
    <div class="thing">
      3
    </div>
    <div class="thing">
      1
    </div>
    <div class="thing">
      5
    </div>
    <div class="thing">
      2
    </div>
  </div>
</div>

- Tschallacka

1

在那个排序函数中，你可以随意操作。a和b是原始的HTML元素，就像你使用document.getElementById('something')一样。你可以用jQuery包装它们并访问数据属性，比较它们的内容，任何操作都可以，这取决于你的实际实现。你可以在mdm文档中了解更多关于sort的信息。https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort - Tschallacka

1

好的，但我希望了解你所编写的特定函数，以便理解过程，因为对于我这样的新手来说，我不确定发生了什么。但是好的，我明白它的一般目的！附注：哦，我实际上还没有在MDN上阅读有关“compareFunction”的内容！啊哈，现在我明白了。 - DevMoutarde

1

@revo 我正在寻找这个方法。虽然我会用原生JavaScript编写解决方案，但在这里使用jQuery并不是真正的问题... - Dex

1

@mindplay.dk 你可能是对的。我来自Netscape和ie4时代，20年间最佳实践随着CPU、图形卡和代码的变化而不断改变。我可能需要更新自己。我会试着使用那个有趣的测试来“更新”自己。 - Tschallacka

1

@Tschallacka（我在这里还应该注意，从DOM中分离意味着失去一些状态，例如焦点和iframe内容-这就是为什么它不能作为一般优化的原因...只要您的表格没有输入，那可能没问题-它只是不是一个完全通用的方法。） - mindplay.dk

显示剩余7条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Watilin · Accepted Answer

对浏览器的能力更有信心。

当在一次单独的同步JavaScript序列执行中执行DOM操作时，浏览器会将它们批处理在一起。当您访问需要DOM处于最新状态的属性/方法（例如innerWidth、offsetTop或getBoundingClientRect）而请求重新排版时，可能会发生异常，有时是无意中请求的。更多详情请参见渲染：重绘、回流、重新布局、重新样式化。
不必删除DOM节点。将其添加到新创建的DocumentFragment中，它们将自动从DOM的当前位置中删除。
浏览器，更具体地说是JS引擎，已经知道并使用最智能的排序算法。除非是非常特殊的情况，否则您不需要了解排序操作的内部机制。只需使用Array.prototype.sort，如果需要，提供自定义函数，然后看魔法发生。