The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

How to optimize this JavaScript?

Hello all,

I'm dealing with <table> and <tr>s here and I've a function that takes two arguments, one is the array of strings(containing <tr> ids e.g. if we have <tr id="hello"> then our string array might contain 'hello'---please hold on , let me explain a bit and I'm sure it will make some sense) and other argument is the table id, which in my case is "myTable". Now in this function I've to loop through all TRs (rows) in this table and find those TRs whose value matches with IDs contained in our other argument i.e. array of strings containing IDs). Here is how my function looks like
------------------------------------------------------------------------------------

function findRows(idStringArray, tableID)
{

  var rows=document.getElementById("myTable").getElementByTagsName("tr");
  var table=document.getElementById("myTable");

  for (var i=0; i<idStringArray.length; i++)
  {
    for (var j=0; j<rows.length;j++)

    {
        if ( rows[j].ID == idStringArray[i] )
/*Got the row, can now do anything with it. So we have to store all such rows whose ID matches with any of the ID given in idStringArray  ...  */
    }
  }


}


Now problem is that I've huge number rows in a table and the above code is taking too much time. My code above is taking some time and I need to optimize this. Any ideas on how should I optimize this code? Please enlighten me, I will appreciate your feedback.

Thanks,
Oltmans
Rolf Oltmans Send private email
Sunday, September 23, 2007
 
 
One quick-win solution would be to convert the algorithm from O(m * n) to O(m + n) by replacing the O(n) loop-based ID lookup with an O(1) hash lookup.

In other words, instead of

  for (var i = 0; i < ids.length; ++i) {
    for (var j = 0; j < rows.length; ++j) {
      if (ids[i] = rows[j]) {
        do_stuff(rows[j]);
      }
    }
  }

use something like

  var id_hash = {};
  for (var i = 0; i < ids.length; ++i) {
    id_hash[ids[i]] = 1;
  }
  for (var j = 0; j < rows.length; ++j) {
    if (id_hash[rows[j]]) {
      do_stuff(rows[j]);
    }
  }

Because this only loops over each array ONCE, it is much faster when either array is large.

If this is still too slow, index your table.
Iago
Sunday, September 23, 2007
 
 
(Yes, I just spotted the = for == typo.)
Iago
Sunday, September 23, 2007
 
 
"If this is still too slow, index your table."

How do you index an HTML table?
John Topley Send private email
Sunday, September 23, 2007
 
 
Using jQuery:

$('table#myTable > tr#hello').each( ... )

That said, same ID on multiple rows is not a good idea. If more than one row can be tagged "hello", use "class", not "id" attribute: <tr class="hello"> .
ping?
Sunday, September 23, 2007
 
 
Iago is right. I use such techniques myself in my library. I have a "Grid" built with it and it would be extremely expensive to keep looking it all up using DOM APIs. Thus, some "Hash" with the "ids" as keys and some other caching can be done this way.

As Joel Spolsky said in a recent article, JavaScript/Ajax is one place where caring for performance still pays off and is needed. So, some fine-tuning here and there can go a long way.

The technique is to always watch out for code in loops, of course. :-) In a Grid, a lot of code can be optimized, unless it's read-only and you don't care about it once it has been drawn.

My for loops can look like this:

var i, j, len, n_cols, col, row;

for (i = 0, len = my_array.length; i < len; i++){
  row = my_array[i];
  for (j = 0, n_cols = row.length; j < n_cols; j++){
    col = row[j];
    // use col, row...
  }
}

Now add your "Hash" to it and some caching for recurrent DOM lookups of elements. That could be abstracted in a Class and then in its objects. It can be better than to make everything global. :-)
Joao Pedrosa
Sunday, September 23, 2007
 
 
Here's a real sample from one of my files:

  find_column_by_id: function(id){
    var a = this.gut.rows;
    var r, cols, i, j, len, n_cols;
    r = null;
    for (i = 0, len = a.length; i < len; i++){
      cols = a[i].columns;
      for (j = 0, n_cols = cols.length; j < n_cols; j++){
        if (cols[j].id == id){
          r = {ir: i, ic: j, column: cols[j]};
          break;
        }
      }
    }
    return r;
  },
Joao Pedrosa
Sunday, September 23, 2007
 
 
BTW, this function could be replaced by an up-to-date lookup Hash, of course. :-) But as far as I am concerned, this function gets called only rarely. The perils of optimization, huh? :-)
Joao Pedrosa
Sunday, September 23, 2007
 
 
"How do you index an HTML table?"

What I had in mind was shifting the calculation server-side (I guess I phrased it pretty poorly).

But I'm intrigued by Joao's suggestion of duplicating its contents in a JavaScript object, which could obviously have arbitrary indexing.  How well does it perform in practice?
Iago
Sunday, September 23, 2007
 
 
could you not join() the string-array with |s and make a RegExp to match against the ID? Probably faster than the nested loop.
You could probably go faster yet in some browsers by using XPath (no IE though, so you'd need to still provide the alternative).
the selector-functionality of the popular JS libraries (Prototype, jquery etc.) is getting better and better with each release, so probably worth at least taking a look at some of the things they use
G Jones Send private email
Sunday, September 23, 2007
 
 
Very well. Table creation, striping (each row has an alternate color), editing, row selection, column selection, almost everything is done with "x, y" coordinates and I cache elements for reuse which makes the hitting of the DOM a little more straightforward.

Also, the table content comes in Ajax JSON calls which can be optimized as well by retrieving only the necessary data (metadata can be retrieved only once for the table and further optimized away), also the JSON file can be gzipped by the server.

I have mostly forgotten about Grid optimization now, even though I have been using Grids everywhere. One of the Grid classes is "Data Aware". The simplest Grid is mostly a Table wrapper which is reused in the other grids of course. And there's one I called InputTable as it has support for user input (events).

In the beginning I had to optimize things, though. It was fun, and I did it because I was testing different JavaScript libraries. Now I have settled on my own.
Joao Pedrosa
Sunday, September 23, 2007
 
 
Thank you everyone for your replies. Joao you replied said

>>and I cache elements for reuse which makes the hitting of >>the DOM a little more straightforward.

How do yo cache elements? Please enlighten me, I mean I really don't know how to do that and I guess by learning this trick I will add one more in my bag :)

Thanks in advance.
Rolf Oltmans Send private email
Monday, September 24, 2007
 
 
I have a two dimensional array for the rows. Each row is a hash comprised of things like (using a snippet of real code):

  create_table_from_items: function(){
    var rows, tc, a, i, len, content, columns, r, j, n_cols, st, column_cls, row_cls, rr, cc, conf;
    var row_id, column_id, thead_id, tbody_id, row2_cls, cls, children, column_conf, styles, st;
    conf = this.gut.conf || {};
    tbody_id = JR.id();
    rr = [];
    rows = [];
    st = JR.merge({}, this.gut.style, conf.style);
    children =  [{tag: JR.TBODY, id: tbody_id, children: rows}];
    tc = {tag: JR.TABLE, id: conf.id || JR.id(), cls: this.gut.cls, style: st, children: children};
    if (this.gut.columns_titles){
      thead_id = JR.id();
      children.splice(0, 0, {tag: JR.THEAD, id: thead_id, children: this.prepare_header_row()});
    }
    column_cls = this.gut.column_cls;
    row_cls = cls = this.gut.row_cls;
    row2_cls = this.gut.row2_cls;
    styles = this.gut.columns_styles;
    a = this.gut.items;
    for (i = 0, len = a.length; i < len; i++){
      r = a[i];
      columns = [];
      cc = [];
      row_id = JR.id();
      rr.push({id: row_id, columns: cc});
      if (row2_cls){
        cls = i % 2 === 0 ? row_cls : row2_cls;
      }
      rows.push({tag: JR.TR, cls: cls, id: row_id, children: columns});
      for (j = 0, n_cols = r.length; j < n_cols; j++){
        content = r[j];
        column_id = JR.id();
        cc.push({id: column_id, content: content});
        column_conf = {tag: JR.TD, cls: column_cls, id: column_id,
            html: this.prepare_column_data(content, j, i)};
        if (styles){
          st = styles[j];
          if (st){
            column_conf.style = st;
          }           
        }
        columns.push(column_conf);
      }
    }
    this.gut.rows = rr;
    this.replace_table(tc);
    if (thead_id){
      this.gut.thead = JR.get(thead_id);
    }
    this.gut.tbody = JR.get(tbody_id);
    this.prepare_for_table_events();
  },


As far as I recall, I save the "id" of the element and then when I first use the HTML element pointed by the id, if it was not cached yet, I cache it for further reuse in the row or column of the "rows" bi-dimensional array. E.g.:

  row_el: function(i){
    var e, rr, r
    rr = this.gut.rows;
    r = rr[i];
    e = null;
    if (r && r.el){
      e = r.el;
    } else if (i >= 0 && i < this.gut.rows.length){
      e = JR.get(this.gut.rows[i].id);
      r.el = e;
    }
    return e;
  },

  column_el: function(ir, ic){
    var rr, r, e, c;
    rr = this.gut.rows;
    r = rr[ir];
    if (r !== undefined && ic >= 0 && ic < this.number_of_columns()){
      c = r.columns[ic];
      e = c.el;
      if (!e){
        c.el = e = JR.get(c.id);
      }
    }
    return e;
  },


The implementation of JR.get is this one:

  get: function(s){
    var e = typeof s == 'string' ? document.getElementById(s) : s;
    return new JR.Element(e);
  },


The problem is that my JavaScript framework is big:

db_dialogs.js  db_widgets.js  grid.js  jr.js  locale.js  widget-core.js  widget.js

So there's a lot I don't know about my own framework anymore. :-)
Joao Pedrosa
Monday, September 24, 2007
 
 
Thanks again.
Rolf Oltmans Send private email
Monday, September 24, 2007
 
 
You're welcome.

BTW, I have taken the time to optimize some of the code I posted here. Sometimes all it takes is a second and clear look at an existing code to see room for improvements.

If pure JavaScript turns out to be slow, one could try to generate some of the JavaScript on the server together with the HTML and go from there, with the "ids" pre-generated and stored in a "rows" array and so on. Of course, it all depends on one's goals. And also on how well one can profile the code. :-)
Joao Pedrosa
Monday, September 24, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz