non-binary non-ordered tree construction from WebSQL in Javascript performance optimization -
can tree constructed faster in js?
i have websql db table structure: id, parentid, masterid, [some other fields not relevant]
first 20 records being read , shown client immediately. ids of these records asynchronously passed construct object global page (not decision, go along) lets call pageobj. object contains 'datasources' contain tree structure of objects. example: pageobj.bcaccount[42].children[0].children[0]... bcaccount[42] holder of masterid children.
to avoid reading db layer layer records being selected websql db masterid like:
select * tablename tablename.masterid in ([list of ids]) i records in callback function structure this:
results { rows : { item : function(i), length : 100 } } to read value 1
results.rows.item(i)[dbcolumnname]; rows have length property can loop thorough records, item can accessed calling results.rows.item(i).
children can belong more 1 parent. @ moment call composerecordstotreestructure concurrently each layer of children because bolt them pageobj parents of child objects have present, 1 concurrent call per tree layer.
i know can change structure reiterating items list , $.grep children, lets not that.
question: there way of optimising mechanism not go layer layer, (or layer layer faster) result in faster tree construction? have no knowledge of position of records in tree id, parentid , masterid. expected tree depth can go 20 levels, width can 1000 records.
currently used mechanism below.
function composerecordstotreestructure(results, tablearray, columnarray, options) { if (results.rows.length > 0) { if (options.parentlayeridlist == undefined){ options.parentlayeridlist = options.masteridlist; } var childrecordidarray = []; var istherenextlayer = false; for(var = 0; < options.parentlayeridlist.length; i++) { for(var ii = 0; ii < results.rows.length; ii++) { if(options.parentlayeridlist[i] == results.rows.item(ii)[options.parentidcolumn]) { var childrecord = attachchildrecordstoparents(results.rows.item(ii), options.parentlayeridlist[i], options.knockoutcontextname) childrecordidarray.push(childrecord.fields['id']); if (istherenextlayer == false){ for(var iii = 0; iii < results.rows.length; iii++){ if (childrecord.fields['id'] == results.rows.item(iii)[options.parentidcolumn]) { istherenextlayer = true; break; } } } } } } } if (istherenextlayer) { options.parentlayeridlist = childrecordidarray; composerecordstotreestructure(results, tablearray, columnarray, options); } } function attachchildrecordstoparents(recordrow, id, knockoutcontextname) { var childtreeoptions = {id : id, knockoutcontextname : knockoutcontextname, results: []}; findobjectsinchildtreebyid(childtreeoptions); if (childtreeoptions.results.length > 0) { var childrecord = attachchildrecord(recordrow, childtreeoptions.results); } return childrecord; } function composechildobject(recordrow) { var recordobject = { fields: {}, setfields: [], insert: false }; (var field in recordrow) { recordobject.fields[field] = field === "id" && recordrow.primaryrowid ? recordrow.primaryrowid : recordrow[field]; } return recordobject; } function attachchildrecord(recordrow, pageobjparentresults) { var recordobject = composechildobject(recordrow); for(var = 0; < pageobjparentresults.length; i++){ if(pageobjparentresults[i].children == undefined) { pageobjparentresults[i].children = ko.observablearray([]); } if ($.grep(pageobjparentresults[i].children, function(children){ return children['id'] == recordobject['id'];}).length == 0) pageobjparentresults[i].children.push(recordobject); } return recordobject; } function findobjectsinchildtreebyid(options) { if (options.item == undefined) { for(var item in pageobj[options.knockoutcontextname]()) { findobjectsinchildtreebyid({item : pageobj[options.knockoutcontextname]()[item], id : options.id, results: options.results}); } } else { if (typeof options.item.fields['id'] == 'function') { if (options.item.fields['id']() == options.id) options.results.push(options.item); } else { if (options.item.fields['id'] == options.id) options.results.push(options.item); } if (options.item.children!=undefined) { for(var item in options.item.children()) { findobjectsinchildtreebyid({item : options.item.children()[item], id : options.id, results: options.results}); } } } }
since no 1 cares.
depth - how deep record chain goes in 1 branch,
record count - how many records in total
time in milliseconds. there's lot of noise in these results.
example: depth 5 record count 500 means 100 branches of 5 records each
[element] --> [child] --> [child] --> [child] --> [child] --> [child] [element] --> [child] --> [child] --> [child] --> [child] --> [child] ... [97 more] ... [element] --> [child] --> [child] --> [child] --> [child] --> [child] performance:
+-------+--------------+------------------------------------------+------------------------------------------------+---------------------------------------+----------------------------+----------------------------+-----------------------+ | depth | record count | chrome (parent-child-orphan) shuffled ms | chrome (bulk read grep clean) shuffled ms | chrome (bulk read grep clean) ms | chrome (bulk read grep) ms | chrome (layer layer) ms | chrome (bulk read) ms | +-------+--------------+------------------------------------------+------------------------------------------------+---------------------------------------+----------------------------+----------------------------+-----------------------+ | 1 | 25 | 650 | 659 | 464 | 0 | 0 | 0 | | 1 | 50 | 614 | 707 | 417 | 0 | 0 | 0 | | 1 | 75 | 577 | 683 | 448 | 0 | 0 | 0 | | 1 | 100 | 659 | 679 | 442 | 0 | 0 | 0 | | 1 | 200 | 604 | 819 | 514 | 0 | 0 | 0 | | 1 | 500 | 759 | 1217 | 766 | 0 | 0 | 0 | | 1 | 1000 | 1696 | 2310 | 1421 | 0 | 0 | 0 | | 5 | 25 | 373 | 669 | 502 | 651 | 806 | 865 | | 5 | 50 | 464 | 661 | 534 | 893 | 932 | 1097 | | 5 | 75 | 462 | 676 | 588 | 641 | 939 | 1348 | | 5 | 100 | 581 | 679 | 599 | 677 | 1025 | 1764 | | 5 | 200 | 562 | 772 | 629 | 761 | 1234 | 2942 | | 5 | 500 | 712 | 1359 | 1007 | 1339 | 1908 | 13299 | | 5 | 1000 | 1274 | 2792 | 2072 | 2900 | 3733 | 32602 | | 10 | 20 | 428 | 647 | 429 | 601 | 948 | 790 | | 10 | 50 | 386 | 670 | 435 | 576 | 975 | 930 | | 10 | 70 | 597 | 710 | 440 | 631 | 1023 | 1284 | | 10 | 100 | 432 | 695 | 463 | 653 | 1001 | 1321 | | 10 | 200 | 654 | 809 | 501 | 684 | 1357 | 3130 | | 10 | 500 | 758 | 1356 | 826 | 1208 | 2116 | 11246 | | 10 | 1000 | 1243 | 2765 | 1661 | 2524 | 3687 | 33714 | | 20 | 20 | 531 | 634 | 435 | 612 | 1198 | 848 | | 20 | 40 | 574 | 668 | 425 | 687 | 1176 | 1003 | | 20 | 60 | 545 | 690 | 478 | 620 | 1245 | 1093 | | 20 | 100 | 552 | 735 | 448 | 671 | 1343 | 1693 | | 20 | 200 | 711 | 837 | 486 | 785 | 1584 | 3134 | | 20 | 500 | 965 | 1417 | 914 | 1125 | 2478 | 12825 | | 20 | 1000 | 1510 | 2985 | 1763 | 2621 | 3956 | 35619 | | 50 | 50 | 513 | 679 | 411 | 571 | 1854 | 1129 | | 50 | 100 | 529 | 747 | 435 | 684 | 1984 | 1523 | | 50 | 200 | 677 | 860 | 458 | 704 | 1928 | 3107 | | 50 | 500 | 1065 | 1254 | 781 | 1428 | 3081 | 12592 | | 50 | 1000 | 1868 | 2768 | 1595 | 2765 | 4908 | 35515 | | 100 | 100 | 468 | 676 | 467 | 729 | 3071 | 1835 | | 100 | 200 | 477 | 812 | 556 | 776 | 3232 | 3894 | | 100 | 500 | 848 | 1379 | 855 | 1330 | 4215 | 13687 | | 100 | 1000 | 2054 | 2670 | 1998 | 2577 | 6415 | 37376 | | 200 | 200 | 0 | 0 | 0 | 823 | 5336 | 3771 | | 200 | 400 | 0 | 0 | 0 | 1197 | 6243 | 10169 | | 200 | 1000 | 0 | 0 | 0 | 3080 | 9392 | 36198 | +-------+--------------+------------------------------------------+------------------------------------------------+---------------------------------------+----------------------------+----------------------------+-----------------------+ 'parent-child-orphan'™ myself wins
please beat algorithm.
shuffling data before processing.
here's code.
function composerecordstotreestructure(results, tablearray, columnarray, options) { if (results.rows.length > 0) { if (options.parentlayeridlist == undefined){ options.parentlayeridlist = options.masteridlist; } if (options.orphans == undefined){ options.orphans = []; } var childrecordidarray = []; if (options.runningonorphans) { if (options.orphans.length > 0) { (var j = 0; j < options.orphans.length; j++) { var rowrecord = options.orphans[j]; var parentposition = $.inarray(rowrecord.fields[options.parentidcolumn], options.parentlayeridlist); if (parentposition != -1) { attachpassedchildrecordstoparents(rowrecord, options.parentlayeridlist[parentposition], options.knockoutcontextname); childrecordidarray.push(rowrecord.fields['id']); childrecordidarray = addchildrecordstonextparentlist(rowrecord, childrecordidarray); } else { var recentparentposition = $.inarray(rowrecord.fields[options.parentidcolumn], childrecordidarray); if (recentparentposition != -1) { attachpassedchildrecordstoparents(rowrecord, childrecordidarray[recentparentposition], options.knockoutcontextname); childrecordidarray.push(rowrecord.fields['id']); childrecordidarray = addchildrecordstonextparentlist(rowrecord, childrecordidarray); } else { var matchingorphans = $.grep(options.orphans, function(item){ return item.fields['id'] == rowrecord.fields[options.parentidcolumn]; }); if (matchingorphans.length > 0) { attachtoorphans(rowrecord, matchingorphans); } } } } options.orphans = $.grep(options.orphans, function(item){ return $.inarray(item.fields['id'], childrecordidarray) == -1; }); } } else { for(var = 0; < results.rows.length; i++) { var rowrecord = results.rows.item(i); if (rowrecord[options.parentidcolumn] == '' || rowrecord[options.masteridcolumn] == '' || rowrecord[options.masteridcolumn] == rowrecord['id']) { rowrecord.isinvalid = true; } if (rowrecord.isinvalid == true) { var parentposition = $.inarray(rowrecord[options.masteridcolumn], options.parentlayeridlist); if (parentposition != -1) { var childrecord = attachchildrecordstoparents(rowrecord, options.parentlayeridlist[parentposition], options.knockoutcontextname); childrecordidarray.push(childrecord.fields['id']); } } else { var parentposition = $.inarray(rowrecord[options.parentidcolumn], options.parentlayeridlist); if (parentposition != -1) { var childrecord = attachchildrecordstoparents(rowrecord, options.parentlayeridlist[parentposition], options.knockoutcontextname); childrecordidarray.push(childrecord.fields['id']); } else { var recentparentposition = $.inarray(rowrecord[options.parentidcolumn], childrecordidarray); if (recentparentposition != -1) { var childrecord = attachchildrecordstoparents(rowrecord, childrecordidarray[recentparentposition], options.knockoutcontextname); childrecordidarray.push(childrecord.fields['id']); } else { var matchingorphans = $.grep(options.orphans,function(item){ return item.fields['id'] == rowrecord[options.parentidcolumn]; }); var composedobject = composechildobject(rowrecord); if (matchingorphans.length > 0) { attachtoorphans(composedobject, matchingorphans); } else { options.orphans.push(composedobject); options.runningonorphans = true; } } } } } } if (options.orphans.length > 0) { options.parentlayeridlist = childrecordidarray; composerecordstotreestructure(results, tablearray, columnarray, options); } } } function addchildrecordstonextparentlist(childrecord, childrecordidarray) { if (childrecord.children != undefined) { for(var = 0; < childrecord.children().length; i++) { childrecordidarray.push(childrecord.children()[i].fields['id']); if (childrecord.children()[i].children != undefined) { addchildrecordstonextparentlist(childrecord.children()[i], childrecordidarray); } } } return childrecordidarray; } function rowstolistdatastructure(results) { var array = []; for(var = 0; < results.rows.length; i++) { array.push(results.rows.item(i)); } return array; } function attachlayerofchildrecords(results, tablearray, columnarray, options) { var childrecordarray = []; if (results.rows.length > 0) { for(i = 0; < results.rows.length; i++){ var childrecord = attachchildrecordstoparents(results.rows.item(i), results.rows.item(i)[options.parentidcolumn], options.knockoutcontextname); childrecordarray.push(childrecord); } } return childrecordarray; } function attachchildrecordstoparents(recordrow, id, knockoutcontextname) { var childtreeoptions = {id : id, knockoutcontextname : knockoutcontextname, results: []}; findobjectsinchildtreebyid(childtreeoptions); if (childtreeoptions.results.length > 0) { var childrecord = attachchildrecord(recordrow, childtreeoptions.results); } return childrecord; } function composechildobject(recordrow) { var recordobject = { fields: {}, setfields: [], insert: false }; (var field in recordrow) { recordobject.fields[field] = field === "id" && recordrow.primaryrowid ? recordrow.primaryrowid : recordrow[field]; } return recordobject; } function attachchildrecord(recordrow, pageobjparentresults) { var recordobject = composechildobject(recordrow); for(var = 0; < pageobjparentresults.length; i++){ if(pageobjparentresults[i].children == undefined) { pageobjparentresults[i].children = ko.observablearray([]); } if ($.grep(pageobjparentresults[i].children, function(children){ return children['id'] == recordobject['id'];}).length == 0) pageobjparentresults[i].children.push(recordobject); } return recordobject; } function attachpassedchildrecordstoparents(recordobject, id, knockoutcontextname) { var childtreeoptions = {id : id, knockoutcontextname : knockoutcontextname, results: []}; findobjectsinchildtreebyid(childtreeoptions); if (childtreeoptions.results.length > 0) { var childrecord = attachpassedchildrecord(recordobject, childtreeoptions.results); } return childrecord; } function attachpassedchildrecord(recordobject, pageobjparentresults) { for(var = 0; < pageobjparentresults.length; i++){ if(pageobjparentresults[i].children == undefined) { pageobjparentresults[i].children = ko.observablearray([]); } if ($.grep(pageobjparentresults[i].children, function(children){ return children['id'] == recordobject['id'];}).length == 0) pageobjparentresults[i].children.push(recordobject); } return recordobject; } function attachtoorphans(recordobject, orphanparents) { for(var = 0; < orphanparents.length; i++){ if (orphanparents[i].children == undefined) { orphanparents[i].children = ko.observablearray([]); orphanparents[i].children.push(recordobject); } } } function findobjectsinchildtreebyid(options) { if (options.item == undefined) { for(var item in pageobj[options.knockoutcontextname]()) { findobjectsinchildtreebyid({item : pageobj[options.knockoutcontextname]()[item], id : options.id, results: options.results}); } } else { if (typeof options.item.fields['id'] == 'function') { if (options.item.fields['id']() == options.id) options.results.push(options.item); } else { if (options.item.fields['id'] == options.id) options.results.push(options.item); } if (options.item.children!=undefined) { for(var item in options.item.children()) { findobjectsinchildtreebyid({item : options.item.children()[item], id : options.id, results: options.results}); } } } } the next best thing changing rows.item(i) structure list, can jquery 'grepped' , processing layer layer:
bulk read grep clean:
function composerecordstotreestructure(results, tablearray, columnarray, options) { if (results.rows.length > 0) { if (options.parentlayeridlist == undefined){ options.parentlayeridlist = options.masteridlist; } var childrecordidarray = []; var istherenextlayer = false; if (options.listresult == undefined){ options.listresult = rowstolistdatastructure(results); } for(var = 0; < options.parentlayeridlist.length; i++) { var children = $.grep(options.listresult, function(item){ return item[options.parentidcolumn] == options.parentlayeridlist[i]}); for(var ii = 0; ii < children.length; ii++) { attachchildrecordstoparents(children[ii], options.parentlayeridlist[i], options.knockoutcontextname) childrecordidarray.push(children[ii]['id']); if (istherenextlayer == false){ istherenextlayer = ($.grep(options.listresult, function(item){ return children[ii]['id'] == item[options.parentidcolumn];}).length > 0) } } } if (istherenextlayer) { options.parentlayeridlist = childrecordidarray; composerecordstotreestructure(results, tablearray, columnarray, options); } } } function rowstolistdatastructure(results) { var array = []; for(var = 0; < results.rows.length; i++) { array.push(results.rows.item(i)); } return array; } function attachlayerofchildrecords(results, tablearray, columnarray, options) { var childrecordarray = []; if (results.rows.length > 0) { for(i = 0; < results.rows.length; i++){ var childrecord = attachchildrecordstoparents(results.rows.item(i), results.rows.item(i)[options.parentidcolumn], options.knockoutcontextname); childrecordarray.push(childrecord); } } return childrecordarray; } function attachchildrecordstoparents(recordrow, id, knockoutcontextname) { var childtreeoptions = {id : id, knockoutcontextname : knockoutcontextname, results: []}; findobjectsinchildtreebyid(childtreeoptions); if (childtreeoptions.results.length > 0) { var childrecord = attachchildrecord(recordrow, childtreeoptions.results); } return childrecord; } function composechildobject(recordrow) { var recordobject = { fields: {}, setfields: [], insert: false }; (var field in recordrow) { recordobject.fields[field] = field === "id" && recordrow.primaryrowid ? recordrow.primaryrowid : recordrow[field]; } return recordobject; } function attachchildrecord(recordrow, pageobjparentresults) { var recordobject = composechildobject(recordrow); for(var = 0; < pageobjparentresults.length; i++){ if(pageobjparentresults[i].children == undefined) { pageobjparentresults[i].children = ko.observablearray([]); } if ($.grep(pageobjparentresults[i].children, function(children){ return children['id'] == recordobject['id'];}).length == 0) pageobjparentresults[i].children.push(recordobject); } return recordobject; } function findobjectsinchildtreebyid(options) { if (options.item == undefined) { for(var item in pageobj[options.knockoutcontextname]()) { findobjectsinchildtreebyid({item : pageobj[options.knockoutcontextname]()[item], id : options.id, results: options.results}); } } else { if (typeof options.item.fields['id'] == 'function') { if (options.item.fields['id']() == options.id) options.results.push(options.item); } else { if (options.item.fields['id'] == options.id) options.results.push(options.item); } if (options.item.children!=undefined) { for(var item in options.item.children()) { findobjectsinchildtreebyid({item : options.item.children()[item], id : options.id, results: options.results}); } } } } 
Comments
Post a Comment