Generating a mosaic

Question

I have been playing around with tables and random colors to generate some mosaic.

As I find it rather slow, tell me how it can be improved in terms of speed.

function generate_mosaic(cols, rows) {
    var i, ncol, trans, colspan, style, html;
    html += "<table>";

    for (i = 0; i < rows; i += 1) {
        html += "<tr>";
        ncol = 0;
        while (ncol < cols) {
            trans = ncol / cols * 0.5 + i / rows * 0.5;
            colspan = Math.floor(Math.random() * 2) + 1;

            if (ncol === cols - 1) {
                colspan = 1;
            }

            ncol += colspan;

            style = "background-color: rgba(" + Math.floor(Math.random() * 255) + ", " + Math.floor(Math.random() * 255) + ", " + Math.floor(Math.random() * 255) + ", " + trans + ");";
            html += "<td colspan=" + colspan + " style='" + style + " line-height: 5px'>&nbsp;<\/td>";
        }
        html += "<\/tr>";
    }
    html += "<\/table>";
    return html;
}

document.write(generate_mosaic(250, 250));

Code is also available as a jsfiddle

Answer 1

I suggest using document.body.innerHTML instead of document.write()

document.body.innerHTML = generateMosaic();

also put Math.random in a variable so it doesn't have to go back to the math object each time:

var random = Math.random;
random() * 255;

Also Math.Floor is apparently quite slow try >> 0 instead

((random() * 255) >>0);

(an example using HTML5 canvas):

http://jsfiddle.net/yHxxT/1/

function generate_mosaic2(cols, rows, canvasElement) {
    var colUnitSize = canvasElement.width / cols;
    var rowUnitSize = canvasElement.height/ rows;
    var nrows = rows;
    var rows2 = rows * 2;
    var cols2 = cols * 2;
    var trans = 0;
    var random = Math.random;
    var floor = function (number){ return (number >> 0); };
    var context = canvasElement.getContext("2d");
    var colspan = 0;
    context.fillStyle = "#000";
    context.fillRect(0,0, 1000, 1250); //Black background
    do
    {
        var ncols= cols;
        do
        {
            trans = ncols / cols2 + nrows / rows2;

            if(ncols === 1)
            {
                colspan = 1;
            }
            else
            {
                colspan = floor(random() * 2);
            }
            context.fillStyle = "rgba(" + floor(random() * 255) + ", " + floor(random() * 255) + ", " + floor(random() * 255) + ", " + trans + ")";
            context.fillRect(ncols * colUnitSize , nrows * rowUnitSize , colspan * colUnitSize  , rowUnitSize);
            ncols -= colspan;
        }while(ncols)
    }while(--nrows)

}

http://jsperf.com/mosaic jsperf would suggest that the canvas solution is more than 2 times faster for a 250x250 or 150x150

Answer 2

Since you are looking for performance issues, you might consider this:

html += "<tr>";

Continually appending to a string is often O(n) where n is the length of the string. Using an array and push()ing the string snips onto it, then using .join() at the end can often be faster.

Different javascript engines will optimize the two methods differently -- test cross browser to see if it's fast enough.

Answer 3

I'm with Sean: string concatenation is slow. Replace your function by:

function generate_mosaic(cols, rows) { 
    var i, ncol, trans, colspan, style;
    var  html = [], j=0; 
    html[j++] = "<div><table>"; 

    for (i = 0; i < rows; i += 1) { 
        html[j++] = "<tr>"; 
        ncol = 0; 
        while (ncol < cols) { 
            trans = ncol / cols * 0.5 + i / rows * 0.5; 
            colspan = Math.floor(Math.random() * 2) + 1; 

            if (ncol === cols - 1) { 
                colspan = 1; 
            } 

            ncol += colspan; 

            html[j++] = '<td colspan="';
            html[j++] = colspan;
            html[j++] = '" style="background-color: rgba(';
            html[j++] = Math.floor(Math.random() * 255);
            html[j++] = ',';
            html[j++] = Math.floor(Math.random() * 255);
            html[j++] = ',';
            html[j++] = Math.floor(Math.random() * 255);
            html[j++] = ',';
            html[j++] = trans;
            html[j++] = '); line-height: 5px">&nbsp;<\/td>';
        } 
        html[j++] = '<\/tr>'; 
    } 
    html[j++] = '<\/table></div>'; 
    return html.join(''); 
}

you should find it much faster. For more information see my answer to a similar query posted here:

https://stackoverflow.com/questions/4864294/dynamic-creation-of-large-html-table-in-javascript-performance/4865247#4865247

Testing with IE9 shows this method to take only about half the time to execute than the "canvas" solution.

Testing with CHROME shows the 125x125 case to be slower, but the 250x250 case faster.

Testing with FIREFOX shows both methods to be about the same.

See: http://jsperf.com/mosaic/2

Regards Neil

Answer 4

Did you try document.body.appendElement / document.createElement("tr") etc instead of modifying innerHTML.

Note though that you should append everything to a non-visible (actually not even add it to the DOM) element while in the loop and after that append that base-element to the actual dome.

something like:

var myCanvas = document.createElement("div");
for(blabla)
{
  var myTd = document.createElement("td");
  myTd.style.backgroundColor = ...;
  ...
  myCanvas.appendChild(myTd);
}
document.body.appendChild(myCanvas);

btw, is it the generation that is slow or the whole page after the generation is done? This is a terrible way to create such a dense and large mosaic, use html5-canvas or a server-side generated image instead.