javascript - 如何更快地对 HTML 表格进行排序？

Question

我是 Javascript 新手。在尝试了许多 Javascript 和 Jquery 插件来对我的 HTML 表进行排序并最终感到失望之后，我决定实现自己的 Javascript 代码来对 HTML 表进行排序。我编写的代码是来自 W3Schools 的更新。

function sortFunctionNumeric(n) {
  var table, rows, switching, i, x, y, shouldSwitch, dir, switchcount = 0;
  table = document.getElementById("reportingTable");
  switching = true;
  //Set the sorting direction to ascending:
  dir = "asc";
  /*Make a loop that will continue until
  no switching has been done:*/
  while (switching) {
    //start by saying: no switching is done:
    switching = false;
    rows = table.rows;
    /*Loop through all table rows (except the
    first, which contains table headers):*/
    for (i = 1; i < (rows.length - 1); i++) {
      //start by saying there should be no switching:
      shouldSwitch = false;
      /*Get the two elements you want to compare,
      one from current row and one from the next:*/
      x = rows[i].getElementsByTagName("TD")[n];
      y = rows[i + 1].getElementsByTagName("TD")[n];
      /*check if the two rows should switch place,
      based on the direction, asc or desc:*/
      if (dir == "asc") {
        if (Number(x.innerHTML) > Number(y.innerHTML)) {
          //if so, mark as a switch and break the loop:
          shouldSwitch = true;
          break;
        }
      } else if (dir == "desc") {
        if (Number(x.innerHTML) < Number(y.innerHTML)) {
          //if so, mark as a switch and break the loop:
          shouldSwitch = true;
          break;
        }
      }
    }
    if (shouldSwitch) {
      /*If a switch has been marked, make the switch
      and mark that a switch has been done:*/
      rows[i].parentNode.insertBefore(rows[i + 1], rows[i]);
      switching = true;
      //Each time a switch is done, increase this count by 1:
      switchcount++;
    } else {
      /*If no switching has been done AND the direction is "asc",
      set the direction to "desc" and run the while loop again.*/
      if (switchcount == 0 && dir == "asc") {
        dir = "desc";
        switching = true;
      }
    }
  }
}

现在排序工作得很好。但是，它非常慢!

我处理了很多行数据(取决于项目，它可以达到 9000 行)。
有没有办法加快我的 Javascript 代码？

Answer 1

它有助于避免在浏览器 JavaScript 中实现排序算法，因为 JavaScript 的内置 Array.prototype.sort 即使您最终实现了相同的排序算法(IIRC 大多数 JS 引擎可能会使用 QuickSort)，该方法也会快得多。

这是我的做法:

获取所有 <tr> JavaScript 中的元素 Array .

您需要使用 querySelectorAll结合 Array.from因为querySelectorAll 不返回数组 ，它实际上返回一个 NodeListOf<T> - 但您可以将其传递给 Array.from将其转换为 Array .

一旦您拥有 Array , 你可以使用 Array.prototype.sort(comparison)使用自定义回调从 <td> 中提取数据两个 child <tr>正在比较的元素，然后比较数据(在比较数值时使用 x - y 技巧。对于 string 值，您需要使用 String.prototype.localeCompare，例如 return x.localeCompare( y )。

在 Array 之后已排序(即使是具有数万行的表也不应该超过几毫秒，as QuickSort is really quick !)重新添加每个 <tr>使用 appendChild parent 的<tbody> .

下面是我在 TypeScript 中的实现，以及位于下方的脚本运行器中具有有效 JavaScript 的工作示例:

// This code has TypeScript type annotations, but can be used directly as pure JavaScript by just removing the type annotations first.

function sortTableRowsByColumn( table: HTMLTableElement, columnIndex: number, ascending: boolean ): void {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

    rows.sort( ( x: HTMLtableRowElement, y: HTMLtableRowElement ) => {
        const xValue: string = x.cells[columnIndex].textContent;
        const yValue: string = y.cells[columnIndex].textContent;

        // Assuming values are numeric (use parseInt or parseFloat):
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum ); // <-- Neat comparison trick.
    } );

    // There is no need to remove the rows prior to adding them in-order because `.appendChild` will relocate existing nodes.
    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev: Event ): void {

    const th = ev.currentTarget as HTMLTableCellElement;
    const table = th.closest( 'table' );
    const thIndex: number = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = ( th.dataset as any ).sort != 'asc';

    sortTableRowsByColumn( table, thIndex, ascending );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }

    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

我的 sortTableRowsByColumn函数假设如下:

您的 <table>元素使用 <thead>并且有一个 <tbody>

您正在使用支持 => 的现代浏览器, Array.from , for( x of y ) , :scope , .closest() , 和 .remove() (即不是 Internet Explorer 11)。

您的数据以 #text 的形式存在( .textContent ) 的 <td>元素。

没有colspan或 rowspan表格中的单元格。

这是一个可运行的示例。只需单击列标题即可按升序或降序排序:

function sortTableRowsByColumn( table, columnIndex, ascending ) {

    const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );
    
    rows.sort( ( x, y ) => {
    
        const xValue = x.cells[columnIndex].textContent;
        const yValue = y.cells[columnIndex].textContent;
        
        const xNum = parseFloat( xValue );
        const yNum = parseFloat( yValue );

        return ascending ? ( xNum - yNum ) : ( yNum - xNum );
    } );

    for( let row of rows ) {
        table.tBodies[0].appendChild( row );
    }
}

function onColumnHeaderClicked( ev ) {
    
    const th = ev.currentTarget;
    const table = th.closest( 'table' );
    const thIndex = Array.from( th.parentElement.children ).indexOf( th );

    const ascending = !( 'sort' in th.dataset ) || th.dataset.sort != 'asc';
    
    const start = performance.now();

    sortTableRowsByColumn( table, thIndex, ascending );

    const end = performance.now();
    console.log( "Sorted table rows in %d ms.",  end - start );

    const allTh = table.querySelectorAll( ':scope > thead > tr > th' );
    for( let th2 of allTh ) {
        delete th2.dataset['sort'];
    }
 
    th.dataset['sort'] = ascending ? 'asc' : 'desc';
}

window.addEventListener( 'DOMContentLoaded', function() {
    
    const table = document.querySelector( 'table' );
    const tb = table.tBodies[0];

    const start = performance.now();

    for( let i = 0; i < 9000; i++ ) {
        
        let row = table.insertRow( -1 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
        row.insertCell( -1 ).textContent = Math.ceil( Math.random() * 1000 );
    }

    const end = performance.now();
    console.log( "IT'S OVER 9000 ROWS added in %d ms.", end - start );
    
} );

html { font-family: sans-serif; }

table {
    border-collapse: collapse;
    border: 1px solid #ccc;
}
    table > thead > tr > th {
        cursor: pointer;
    }
    table > thead > tr > th[data-sort=asc] {
        background-color: blue;
        color: white;
    }
    table > thead > tr > th[data-sort=desc] {
        background-color: red;
        color: white;
    }
    table th,
    table td {
        border: 1px solid #bbb;
        padding: 0.25em 0.5em;
    }

<table>
    <thead>
        <tr>
            <th onclick="onColumnHeaderClicked(event)">Foo</th>
            <th onclick="onColumnHeaderClicked(event)">Bar</th>
            <th onclick="onColumnHeaderClicked(event)">Baz</th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <td>1</td>
            <td>9</td>
            <td>a</td>
        </tr>
        <!-- 9,000 additional rows will be added by the DOMContentLoaded event-handler when this snippet is executed. -->
    </tbody>
</table>

关于性能的一句话:

根据 Chrome 78 的开发者工具的性能分析器，在我的电脑上，performance.now()调用表明行在大约 300 毫秒内排序，但是在 JavaScript 停止运行后发生的“重新计算样式”和“布局”操作分别花费了 240 毫秒和 450 毫秒(690 毫秒的总重新布局时间，加上 300 毫秒的排序时间意味着它需要一个完整的秒(1,000 毫秒)从点击到排序)。

当我更改脚本时，<tr>元素被添加到中间 DocumentFragment而不是 <tbody> (这样每个 .appendChild 调用都保证不会导致回流/布局，而不是仅仅假设 .appendChild 不会触发回流)并重新运行性能测试我的结果时序数字或多或少相同(在 5 次重复后，它们实际上稍微高出约 120 毫秒，平均时间为(1,120 毫秒) - 但我将把它归结为浏览器 JIT 播放。

这是 sortTableRowsByColumn 中更改后的代码:

    function sortTableRowsByColumn( table, columnIndex, ascending ) {

        const rows = Array.from( table.querySelectorAll( ':scope > tbody > tr' ) );

        rows.sort( ( x, y ) => {

            const xValue = x.cells[columnIndex].textContent;
            const yValue = y.cells[columnIndex].textContent;

            const xNum = parseFloat( xValue );
            const yNum = parseFloat( yValue );

            return ascending ? ( xNum - yNum ) : ( yNum - xNum );
        } );

        const fragment = new DocumentFragment();
        for( let row of rows ) {
            fragment.appendChild( row );
        }

        table.tBodies[0].appendChild( fragment );
    }

由于 Automatic Table Layout 算法，我认为性能相对较慢。我敢打赌，如果我将 CSS 更改为使用 table-layout: fixed;布局时间将缩短。 (更新:我用 table-layout: fixed; 对其进行了测试，令人惊讶的是，它根本没有提高性能 - 我似乎无法获得比 1,000 毫秒更好的时间 - 哦，好吧)。