在视口中获取元素的最快方法

Question

我正在动态创建一个非常大的 HTML 文件，其中包含任何给定计算机上的浏览器可以生成的尽可能多的元素。

然后，当用户滚动时，我需要访问实际上在视口内的某种类型（比如说 div）的元素。

我知道如何获取视口中可见元素列表的唯一方法是遍历所有元素，然后查看它们的边界是否与当前视口重叠。这样做的问题是文档中的元素太多，这个过程无法快速完成，无法让浏览器滚动。

有没有更快的方法来获取视口中的所有元素？

Answer 1

分而治之

您可以将窗口区域划分为更小的区域（FNO 块）。如果网站主要是垂直的，则不需要多于一栏（块宽度等于文档宽度）。填充页面后，将每个节点及其后代添加到它们所在的块中（它们可以位于多个块中）。在滚动事件处理程序上，您只需要检查可见块中的节点。如果每个块的高度等于视口的高度，则您最多只需要检查两个块。而且无论页面有多大，您总会找到如下块：

var from = Math.trunc( viewport.y / blockHeight ) ;
var to = Math.trunc( viewport.y2 / blockHeight ) ;

在以下示例中，我动态创建了 10,500 个节点；之后，您可以滚动页面并列出可见的 div。如果您想以不同的方式过滤节点，您可以调整名为matches 的函数。我在我的平板电脑上用 Chrome 和 200,000 个节点测试了这个，页面加载后，滚动很流畅。当您添加的节点数量超过计算机/浏览器可以处理的数量时，性能可能会下降，该算法运行良好。使用相同的测试机器和 1,000,000 个节点，滚动不是实时发生的，但并没有那么慢。

页面加载需要时间，请耐心等待。

var blocks = [] ;
var blockHeight ;
var blocksNumber ;
function isVisible( element, vp )
{
    /* This checks if the element is in the viewport area, you could also
     * check the display and visibility of its style.
     */
    var rect = element.getBoundingClientRect( ) ;
    var x = rect.left ;
    var x2 = x + element.offsetWidth ;
    var y = rect.top ;
    var y2 = y + element.offsetHeight ;
    return !( x >= vp.w || y >= vp.h || x2 < 0 || y2 < 0 ) ;
}
function matches( element, vp )
{
    /* You can filter the elements even further */
    return element && element.id && element.tagName === "DIV" && isVisible( element, vp ) ;
}
function viewport( )
{
    this.x = window.pageXOffset ;
    this.w = window.innerWidth ;
    this.x2 = this.x + this.w - 1 ;
    this.y = window.pageYOffset ;
    this.h = window.innerHeight ;
    this.y2 = this.y + this.h - 1 ;
    return this ;
}
function addMatch( element, array )
{
    /* An element may be in more than one block, so you need
     * to check if it wasn't already added.
     */
    for( var i = 0 ; i < array.length ; ++i )
    {
        if( array[i] === element ) return ;
    }
    array.push( element ) ;
}
function onWindowScroll( )
{
    var msg = document.getElementById( "msg" ) ;
    var str = "" ;

    var vp = new viewport( ) ;
    var from = Math.trunc( vp.y / blockHeight ) ;
    var to = Math.trunc( vp.y2 / blockHeight ) ;
    str += "Nodes: " + document.body.childNodes.length
         + ", blocks: " + blocks.length
         + ", searching blocks " + from + "-" + to + "<br>"
         + "Founded: " ;
    var array = [] ;
    for( var b = from ; b <= to ; ++b )
    {
        var block = blocks[b] ;
        for( var i = 0 ; i < block.length ; ++i )
        {
            if( matches( block[i], vp ) )
            {
                addMatch( block[i], array ) ;
            }
        }
    }
    if( array.length )
    {
        for( var i = 0 ; i < array.length-1 ; ++i )
        {
            str += array[i].id + " " ;
        }
        str += array[array.length-1].id ;
    }
    else
    {
        str += "none" ;
    }
    msg.innerHTML = str ;
}
function onWindowLoad( )
{
    setTimeout( function( )
    {
        var i = 0 ;
        /* Lets populate the page */
        while( i < 10000 )
        {
            var element = document.createElement( "DIV" ) ;
            element.className = "first" ;
            element.innerHTML = i ;
            element.id = i++ ;
            document.body.appendChild( element ) ;
            element = document.createElement( "SECOND" ) ;
            element.className = "second" ;
            element.innerHTML = i ;
            element.id = i++ ;
            document.body.appendChild( element ) ;
        }
        /* Lets add random positioned elements */
        var i = 0 ;
        while( i < 500 )
        {
            var x = Math.floor( Math.random( ) * document.body.offsetWidth ) ;
            var y = Math.floor( Math.random( ) * document.body.offsetHeight ) ;
            if( Math.random( ) < 0.5 )
            {
                var element = document.createElement( "DIV" ) ;
                element.className = "absolute-first" ;
            }
            else
            {
                var element = document.createElement( "SECOND" ) ;
                element.className = "absolute-second" ;
            }
            element.style.left = x + "px" ;
            element.style.top = y + "px" ;
            element.id = "r" + i++ ;
            element.innerHTML = element.id ;
            document.body.appendChild( element ) ;
        }
        /* Now we create the blocks */
        var nodes = document.body.childNodes ;
        blockHeight = window.innerHeight ;
        blocksNumber = Math.ceil( document.body.offsetHeight / blockHeight ) ;
        for( var b = 0 ; b < blocksNumber ; ++b )
        {
            blocks[b] = new Array( ) ;
        }
        /* And we add all the nodes into they corresponding blocks */
        for( var i = 0 ; i < nodes.length ; ++i )
        {
            addElement( nodes[i] ) ;
        }
        addEventListener( "scroll", onWindowScroll, false ) ;
        onWindowScroll( ) ; // Initialize msg
    }, 20 ) ;
}
function addElement( element )
{
    /* This works fine if the rest of the nodes stayed in the
     * same position with the same size when element was added.
     */
    if( !element.getBoundingClientRect ) return ;
    var rect = element.getBoundingClientRect( ) ;
    var y = rect.top + window.pageYOffset ;
    var y2 = y + element.offsetHeight ;
    var from = Math.trunc( y / blockHeight ) ;
    var to = Math.trunc( y2 / blockHeight ) ;
    for( var b = from ; b <= to ; ++b )
    {
        blocks[b].push( element ) ;
    }
    var nodes = element.childNodes ;
    if( nodes )
    {
        for( var i = 0 ; i < nodes.length ; ++i )
        {
            addElement( nodes[i] ) ;
        }
    }
}
function removeElement( element )
{
    /* This works fine if the rest of the nodes stayed in the
     * same position with the same size when element was added.
     */
    if( !element.getBoundingClientRect ) return ;
    var rect = element.getBoundingClientRect( ) ;
    var y = rect.top + window.pageYOffset ;
    var y2 = y + element.offsetHeight ;
    var from = Math.trunc( y / blockHeight ) ;
    var to = Math.trunc( y2 / blockHeight ) ;
    for( var b = from ; b <= to ; ++b )
    {
        var i = blocks[b].indexOf( element ) ;
        if( i > -1 )
        {
            blocks[b].splice( i, 1 ) ;
        }
    }
}
addEventListener( "load", onWindowLoad, false ) ;

body
{
    margin: 0 auto ;
    text-align: center ;
    font-family: sans-serif ;
}
/* Filtered in elements are light green */
.first
{
    height: 50px ;
    line-height: 50px ;
    background-color: #cfc ;
}
/* Filtered out elements are light red */
.second
{
    display: block ;
    height: 30px ;
    line-height: 30px ;
    background-color: #fcc ;
    box-sizing: border-box ;
}
/* Filtered in elements are light green */
.absolute-first
{
    background-color: #cfc ;
}
/* Filtered out elements are light red */
.absolute-second
{
    background-color: #fcc ;
}
.absolute-first, .absolute-second
{
    position: absolute ;
    padding: 1pt 5pt 1pt 5pt ;
}
.first, .second, .absolute-first, .absolute-second
{
    border: 1px solid #444 ;
}
#msg
{
    position: fixed ;
    z-index: 1 ;
    top: 0 ;
    left: 0 ;
    width: 100% ;
    min-height: 24pt ;
    line-height: 24pt ;
    border: 1px solid #000 ;
    background-color: #ffd ;
    box-sizing: border-box ;
    font-size: 14pt ;
    vertical-align: middle ;
    text-align: left ;
    padding-left: 3pt ;
    opacity: 0.7 ;
}

<div id="a">
    <div id="a1">
        <div id="a11" class="first">a11</div>
        <div id="a12" class="first">a12</div>
    </div>
    <div id="a2" class="first">a2</div>
</div>
<msg id="msg">Loading page, please wait...</msg>

唯一的缺点是您必须将节点保留在相应的块中。当您添加新节点、删除现有节点或移动或调整节点大小时，应更新块。这应该不是问题，因为您说您首先填充页面。

不考虑固定定位的节点。添加对它们的支持很容易，但它不会为示例添加任何有价值的东西。