Efficient way of filtering arrays in javascript

Question

Below code takes long lots of minutes;

var table = new Array();
for(var i =0; i< dtObjects.Rows.length; i++)
        {
            for(var j=0; j< dtColumns.Rows.length; j++)
            {
                for(var k=0; k< dtTypes.Rows.length; k++)
                {
                  if((dtObjects.Rows[i].Id == dtColumns.Rows[j].Id) && (dtColumns.Rows[j].xtype == dtTypes.Rows[k].xtype))  

                      table.push({
                          TableName : dtObjects.Rows[i].Name,
                          Type:  dtObjects.Rows[i].type,
                          ColumName:  dtColumns.Rows[j].Name,
                          DataType: dtTypes.Rows[k].Name,
                          Length : dtColumns.Rows[j].Length
                      });
                }
            }
        }

dtObjects.Rows.length = 900

dtColumns.Rows.length = 1500

dtTypes.Rows.length = 30

Is there anyway to achieve (filter) this in seconds?

Answer 1

This is similar to Arun's answer (albeit maybe simpler).

What you can do if you are willing to trade a little more memory use for increased speed, is creating a hash of the objects that you will be checking against.

Checking existence in a hash is considerably faster that iterating through and comparing Ids for each column, row & type. To take advantage of that you can start by creating a hash of both of the types and the columns collections, then you only have to check for existence within the hash.

var table = new Array();
var columnsHash = {};
for(var j=0; j< dtColumns.Rows.length; j++) {
  columnsHash[dtColumns.Rows[j].Id] = dtColumns.Rows[j];
}
var typesHash = {};
for(var k=0; k< dtTypes.Rows.length; k++) {
  typesHash[dtTypes.Rows[k].xtype] = dtTypes.Rows[k];
}

for(var i =0; i< dtObjects.Rows.length; i++) {
  var typesObj, columnObj = columnsHash[dtObjects.Rows[i].Id];
  if (columnObj && (typesObj = typesHash[columnObj.xtype])) {
    table.push({
      TableName : dtObjects.Rows[i].Name,
      Type:  dtObjects.Rows[i].type,
      ColumName:  columnObj.Name,
      DataType: typesObj.Name,
      Length : columnObj.Length
    });
  }
}

Note: I haven't actually tested the code, obviously, but in theory this should work, unless I'm missing something.

Answer 2

You can do this by creating index object using Id.

var table = new Array(),
    orows = dtObjects.Rows,
    crows = dtColumns.Rows,
    crowsIndex = {},
    types = dtTypes.Rows,
    typesIndex = {};

for (var j = 0; j < crows.length; j++) {
    crowsIndex[crows[j].Id] = crows[j];
}

for (var k = 0; k < types.length; k++) {
    typesIndex[types[k].xtype] = types[k];
}

for (var i = 0; i < orows.length; i++) {
    var rID = orows[i].Id;
    if (crowsIndex[rID]) {
        var xType = crowsIndex[rID].xtype;
        if (typesIndex[xType]) {
            table.push({
                TableName: orows[i].Name,
                Type: orows[i].type,
                ColumName: crowsIndex[rID]].Name,
            DataType: typesIndex[xType].Name,
            Length: crowsIndex[rID].Length
            });
    }
}

This is NOT TESTED and may not be the final solution you need, but will help you to get started. Please provide sample data to test.

Answer 3

First you can sort both dtObjects and dtColums by id:

function sortById(a,b){
  return (a.id>b.id)?1:(a.id<b.id)?-1:0;
}
dtOjbects.Rows.sort(sortById);
dtColumns.Rows.sort(sortById);

var table = new Array(),
j=0,i=0,
colLen=dtColumns.Rows.length,
objLen=dtObjects.Rows.length,
typLen=dtTypes.Rows.length,
tmpMatch=[];
for(i =0; i< objLen; i++){
  while(j<colLen||dtObjects.Rows[i].id>dtColumns.Rows[j].id){
    if(dtObjects.Rows[i].id===dtColumns.Rows[j].id){
      tmpMatch.push([i,j]);
    }
    j++;
  }
}
for(i=0;i<tmpMatch.length;i++){
  for(j=0;j<typLen;j++){
    if(dtColumns.Rows[tmpMatch[i][1]].xtype == dtTypes.Rows[j].xtype){
      table.push({
        TableName : dtObjects.Rows[tmpMatch[i][0]].Name,
        Type:  dtObjects.Rows[tmpMatch[i][0]].type,
        ColumName:  dtColumns.Rows[tmpMatch[i][1]].Name,
        DataType: dtTypes.Rows[j].Name,
        Length : dtColumns.Rows[tmpMatch[i][1]].Length
    }
  }
}

Answer 4

This will give considerable speed. We need to know how many matching column possible for each row. If it is just one you can break the loop also once matched.

var table = new Array();

for(var i =0; i< dtObjects.Rows.length; i++)
    {
        for(var j=0; j< dtColumns.Rows.length; j++)
        {
            if(dtObjects.Rows[i].Id == dtColumns.Rows[j].Id)
            {
                for(var k=0; k< dtTypes.Rows.length; k++)
                {

                    if((dtColumns.Rows[j].xtype == dtTypes.Rows[k].xtype))  {
                          table.push({
                          TableName : dtObjects.Rows[i].Name,
                          Type:  dtObjects.Rows[i].type,
                          ColumName:  dtColumns.Rows[j].Name,
                          DataType: dtTypes.Rows[k].Name,
                          Length : dtColumns.Rows[j].Length
                      });
                        break;
                    }
                }
            }
        }
    }

Answer 5

With out any sample data we won't able to do much, but in an abstract this is how I might look at a solution

var table = new Array();

var dtObjectMap = {}, dtColumnMap = {};
for (var i = 0; i < dtObjects.Rows.length; i++) {
    dtObjectMap['id-' + dtObjects.Rows[i].Id] = dtObjects.Rows[i];
}

for (var j = 0; j < dtColumns.Rows.length; j++) {
    if (!dtColumnMap[dtColumns.Rows[j].xtype]) {
        dtColumnMap[dtColumns.Rows[j].xtype] = [];
    }
    dtColumnMap[dtColumns.Rows[j].xtype].push(dtColumns.Rows[j]);
}

var dtObject, dtColumn, dtType, dtCXtypes;
for (var k = 0; k < dtTypes.Rows.length; k++) {
    dtType = dtType.Rows[i], dtCXtypes = dtColumnXtypes[dtType.xtype];
    if (dtCXtypes && dtCXtypes.length) {
        for (var l = 0; l < dtCXtypes.length; l++) {
            dtColumn = dtCXtypes[l];
            dtObject = dtObjectMap['id-' + dtColumn.id];
            if (dtObject) {
                table.push({
                    TableName : dtObject.Name,
                    Type : dtObject.type,
                    ColumName : dtColumn.Name,
                    DataType : dtType.Name,
                    Length : dtColumn.Length
                });
            }
        }
    }
}

Answer 6

var table = new Array();
for(var i =0; i< dtObjects.Rows.length; i++)
        {
            for(var j=0; j< dtColumns.Rows.length; j++)
            {
                if(dtObjects.Rows[i].Id == dtColumns.Rows[j].Id){
                    for(var k=0; k< dtTypes.Rows.length; k++)
                {
                  if(dtColumns.Rows[j].xtype == dtTypes.Rows[k].xtype) 

                      table.push({
                          TableName : dtObjects.Rows[i].Name,
                          Type:  dtObjects.Rows[i].type,
                          ColumName:  dtColumns.Rows[j].Name,
                          DataType: dtTypes.Rows[k].Name,
                          Length : dtColumns.Rows[j].Length
                      });
                }

             }

            }
        }

I just conditioned your first condition before your last loop this will make it "little bit" faster

Answer 7

First of all you did not put a break when your condition matches. there is no need to go continue after matching condition.

You can do one thing. As per your condition (dtObjects.Rows[i].Id == dtColumns.Rows[j].Id) && (dtColumns.Rows[j].xtype == dtTypes.Rows[k].xtype) I am telling you this logic.

First loop dtObjects and dtColumns and check for condtion dtObjects.Rows[i].Id == dtColumns.Rows[j].Id. Whatever id's are matching put that "j value" new array (do not forget to put a break when Id match).

Once you done with this loop. Take one more loop for newArray and dtTypes. Check your condition in this manner "dtColumns[newArray[k]].xtype == dtTypes.Rows[l].xtype"

One more thing, keep the object as a outer loop who has more count.