17
\$\begingroup\$

I have an simple algorithm which marks table rows with identical entries blue. The problem is that this solution takes a lot of time.

Has anyone an idea how to improve the speed of this?

$(document).ready(function(){
   var tableRows = $("#sortable tbody tr");
   tableRows.each(function(n){
      var id = $(this).attr('id'); 
      var example = $(this).children('#example').children('#content').html(); 

      tableRows.each(function(n){
         if($(this).attr('id') != id)
         {
            if ($(this).children('#example').children('#content').html() == example)
            {
               $(this).css('backgroundColor', 'azure');
            }
         }
      });
   });
});

My table looks like this:

<table align="center" id="sortable">
   <thead>
      <tr bgcolor="orange">
         <th>Digitcode</th>
      </tr>
   </thead>

   <tbody>
      <tr id="1">
         <th id="example" class="data"><div contenteditable id="content">test</div></th>
      </tr>
   </tbody>
</table>
\$\endgroup\$
  • 2
    \$\begingroup\$ can u please post some html of it....so we can give you ways... \$\endgroup\$ – Wazzzy Dec 2 '11 at 14:07
  • 3
    \$\begingroup\$ Does your markup really contain multiple elements with the same ID? \$\endgroup\$ – Matt Ball Dec 2 '11 at 14:08
  • \$\begingroup\$ Does the whole row need to match, or just specific columns? \$\endgroup\$ – Rory McCrossan Dec 2 '11 at 14:08
  • \$\begingroup\$ I added the table. The whole row needs to match. \$\endgroup\$ – Tobias Nawa Dec 2 '11 at 14:16
  • \$\begingroup\$ I'm confused. The table you show only has 2 rows, and one of those rows is a header. Are you really using all those loops to iterate over 2 table rows? \$\endgroup\$ – Matt Ball Dec 2 '11 at 14:24
6
\$\begingroup\$

Without making algorithmic changes, we can still make some performance improvements:

$(document).ready(function() {
    var $tableRows = $("#sortable tbody tr");
    var $rowsToMark = $();

    $tableRows.each(function(n) {
        var id = this.id;
        var example = $(this).find('.content').html();

        $tableRows.each(function(n) {
            var $this;
            if (this.id != id) {
                $this = $(this);
                if ($this.find('.content').html() == example) {
                    $rowsToMark.add($this);
                }
            }
        });
    });

    $rowsToMark.css('backgroundColor', 'azure');
});

If you really want to start optimizing (I seriously doubt it's worth it, though) you could take a dynamic programming approach and do some caching. For instance:

  • You really don't need to call .html() on any given row more than once. Start by getting the HTML of each row and store it, then you can compare by iterating over those HTML strings rather, than the DOM elements.
  • If you have already determined that rows A and B are equal, you only need to compare row C against either A or B.
  • (other things I haven't yet thought of)

General jQuery performance/optimization information:

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot to all of you! The "var $rowsToMark = $();" thing didn't work. Nothing was marked. Now I compare the whole rows and not all columns inside them. The loading time of my site is now 1,5 seconds. Before it was 5,5 seconds. \$\endgroup\$ – Tobias Nawa Dec 2 '11 at 14:55
5
\$\begingroup\$

The algorithm from the question will perform in a time of N^2 where N equals the number of rows. A better solution would be just in time N (i.e. only iterate over the rows once). This solution requires the sacrifice of a little bit of memory to store each row value once.

So, considering a table like:

<table id="sortable">
    <tbody>
        <tr>
            <td class="content">A</td>
        </tr>
        <tr>
            <td class="content">B</td>
        </tr>
        <tr>
            <td class="content">A</td>
        </tr>
    </tbody>
</table>

then javascript like the following would mark the appropriate rows with only one pass:

$(function() {
    var tableRows = $("#sortable tbody tr"); //find all the rows
    var rowValues = []; //to keep track of which values appear more than once
    tableRows.each(function() { 
        var rowValue = $(this).find(".content").html();
        if (!rowValues[rowValue]) {
            var rowComposite = new Object();
            rowComposite.count = 1;
            rowComposite.row = this;
            rowValues[rowValue] = rowComposite;
        } else {
            var rowComposite = rowValues[rowValue];
            if (rowComposite.count == 1) {
                $(rowComposite.row).css('backgroundColor', 'azure');
            }
            $(this).css('backgroundColor', 'azure');
            rowComposite.count++;
        }
    });
});
\$\endgroup\$
2
\$\begingroup\$

1.5 seconds for ~1000 rows still seems really high to me. Your algorithm is O(n^2).

We can do way better.

$(document).ready(function() {
    var tableRows = $("#sortable tbody tr"),
        // we know exactly how large to make it, so don't use []
        htmlStrings = new Array(tableRows.length),
        i, j, current, comparing;

    for (i = 0; i < tableRows.length; i++) {
        current = htmlStrings[i];
        // get each innerHTML just once
        if (!current) {
            current = {
                html: tableRows.get(i).innerHTML,
                isDup: false
            };
            htmlStrings[i] = current;
        }

        // if we already know it's a dup, so we're done
        if (current.isDup) continue;

        // start j at i+1 since we've already looked at the previous i rows
        for (j = i + 1; j < tableRows.length; j++) {
            // could stay DRY and put this into a function;
            // doing so may decrease performance (not benchmarked)
            comparing = htmlStrings[j];
            if (!comparing) {
                comparing = {
                    html: tableRows.get(j).innerHTML,
                    isDup: false
                };
                htmlStrings[j] = comparing;
            }

            if (comparing.isDup) continue;

            // It comes to this: we must actually compare now.
            if (current.html === comparing.html) {
                current.isDup = true;
                comparing.isDup = true;

                // mark it
                tableRows.eq(j).css('backgroundColor', 'red');
            }
        }

        if (current.isDup) {
            // mark it
            tableRows.eq(i).css('backgroundColor', 'red');
        }

    }
});​
  1. Don't call .html() on any one row more than once.
  2. If a row has already been marked as a duplicate, there is no reason to process it further, nor any of the rows it is a duplicate of.
  3. When looking at the nth row, we have already looked at all the previous n-1 rows, so there is no reason to look at those further, either.
  4. Use a regular for loop rather than a forEach that takes a function.
  5. Use .innerHTML rather than .html().
  6. Use === rather than ==.

For performance testing, I'm going to assume that the text content of each row is a random integer ∈ [0, 9999]. This makes it easy to generate a large number of random rows which have reasonable probability of collisions:

var arr = [];
for (var i=0; i<1000; i++)
{
    arr.push('<tr id="' + i + '"><th class="data"><div contenteditable>' + (~~(Math.random()*10000)) + '</div></th></tr>');
}
console.log(arr.join('\n'));

Original answer's code, O(n^2): jsFiddle

Optimized, O(n log n)I think: jsFiddle

jsPerf comparison: 1k rows | 10k rows

Look how much faster that is!

\$\endgroup\$
1
\$\begingroup\$

The var $rowsToMark = $(); thing didn't work. Nothing was marked.

Now I compare the whole rows and not all columns inside them.

The loading time of my site is now 1,5 seconds. Before it was 5,5 seconds.

$(document).ready(function() {
   var tableRows = $("#sortable tbody tr");

   tableRows.each(function(n){
      var id = this.id;
      var row = $(this).html();

      tableRows.each(function(n){
         var $this;

         if(this.id != id){
            $this = $(this);

            if ($this.html() == row){
               $this.css('backgroundColor', 'azure');
            }
          }
       });
   });
});
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.