Javascript性能优化中基于WebSQL的非二进制无序树构造
Javascript性能优化中基于WebSQL的非二进制无序树构造
提问于 2014-03-13 13:29:51
这棵树在JS中能建得更快吗？
我有WebSQL DB表结构: ID、ParentId、MasterId和其他一些不相关的字段
前20条记录正在读取，并立即显示给客户。然后异步传递这些记录的it，以构造对页面是全局的对象(不是我的决定，请继续)，让它称为PageObj。此对象包含包含对象树结构的“数据源”。例如: PageObj.bcAccount42.Children.Children..。bcAccount42将是所有孩子的MasterId持有者。
为了避免逐层读取DB，所有记录都由WebSQL DB由MasterId选择如下：
SELECT * FROM TableName
WHERE TableName.MasterId IN ([list of ids])我在回调函数中获得了如下结构的记录：
results { rows : { item : function(i), length : 100 } } 要读取价值，你可以
results.rows.item(i)[DBColumnName];行具有length属性，因此我可以循环彻底的记录，但是只能通过调用results.rows.item(i)来访问项。
孩子可以属于一个以上的父母。目前，我对每个子层并发地调用ComposeRecordsToTreeStructure，因为要将它们绑定到子对象的PageObj父级，每个树层必须有一个并发调用。
我知道我可以简单地更改结构，方法是将所有的项都重复到列表中，然后再简单地将其作为$.grep子元素，但不要这样做。
问:是否有一种方法可以优化这种机制，使其不一层一层(或一层一层，但更快)导致更快的树构建？我不知道记录在树中的位置，只有Id、ParentId和MasterId。预计树深可达20层，宽度可达1000条记录。
目前使用的机制如下。
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 i = 0; i < 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 };
for (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 i = 0; i < 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});
}
}
}
}回答 2
Stack Overflow用户
回答已采纳
发布于 2014-03-14 14:44:07
因为没人在乎。
深度-一个分支的唱片链有多深，
记录计数-总共有多少个记录
时间以毫秒为单位。很明显，这些结果有很大的噪音。
例如:深度5记录计数500意味着每个记录的100个分支
[Element] --> [Child] --> [Child] --> [Child] --> [Child] --> [Child]
[Element] --> [Child] --> [Child] --> [Child] --> [Child] --> [Child]
...
[97 more]
...
[Element] --> [Child] --> [Child] --> [Child] --> [Child] --> [Child]性能：
+-------+--------------+------------------------------------------+------------------------------------------------+---------------------------------------+----------------------------+----------------------------+-----------------------+
| Depth | Record count | Chrome (Parent-child-orphan) shuffled ms | Chrome (Bulk read grep with clean) shuffled ms | Chrome (Bulk read grep with clean) ms | Chrome (Bulk read grep) ms | Chrome (Layer by 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 |
+-------+--------------+------------------------------------------+------------------------------------------------+---------------------------------------+----------------------------+----------------------------+-----------------------+‘亲子孤儿’™自己赢了
有人能不能打败这个算法。
我正在整理数据，然后再处理。
这是密码。
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)
{
for (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 i = 0; i < 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 i = 0; i < 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 i = 0; i < 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; i < 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 };
for (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 i = 0; i < 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 i = 0; i < 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 i = 0; i < 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});
}
}
}
}其次，最好的方法是将rows.item(i)结构更改为列表，然后可以对其进行JQuery‘打招呼’，然后逐层处理：
批量阅读grep与干净：
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 i = 0; i < 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 i = 0; i < 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; i < 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 };
for (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 i = 0; i < 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});
}
}
}
}Stack Overflow用户
发布于 2014-03-17 18:07:14
不使用MasterId的版本，并逐层读取ParentIds (Chrome (逐层) ms)
function getBulkChildrenForParentRecordList(options)
{
var listArray = options.listArray;
var parentTable = options.parentTable;
var parentIdColumn = options.parentIdColumn;
var knockoutContextName = options.knockoutContextName;
if (listArray == undefined || listArray.length == 0) {
return;
}
var parentIds = getParentIds(listArray);
var dbManager = new OnTheMoveDatabaseManager();
dbManager.queryDatabase({
statement: {
Tables: [
{ Alias: parentTable, JoinSpec: null, JoinType: "", Name: parentTable },
{ Alias: "Record", JoinSpec : "Record.Id = "+parentTable+".Id", JoinType: "INNER", Name: "Record"}
],
WhereClause: parentTable + "."+parentIdColumn+" IN ('" + parentIds.join("','") + "') AND Record.RecordType ='"+parentTable+"'",
SelectFields: [{ IsAggregate: false, Name: "*"}],
DisablePaging: true
},
knockoutContextName: knockoutContextName,
isObservable: false,
parentIdColumn : parentIdColumn,
parentTable : options.parentTable,
success: function (results, tableArray, columnArray, options) {
var childListArray = AttachChildRecords(results, tableArray, columnArray, options);
if (childListArray.length > 0){
getBulkChildrenForParentRecordList({listArray : childListArray, parentTable : options.parentTable, parentIdColumn : options.parentIdColumn, knockoutContextName : options.knockoutContextName});
}
}
});
}
function AttachChildRecords(results, tableArray, columnArray, options)
{
var childRecordArray = [];
if (results.rows.length > 0) {
for(i = 0; i < results.rows.length; i++){
var childTreeOptions = {id : results.rows.item(i)[options.parentIdColumn], knockoutContextName : options.knockoutContextName, results: []};
findObjectsInChildTreeById(childTreeOptions);
if (childTreeOptions.results.length > 0) {
for(var ii = 0; ii < childTreeOptions.results.length; ii++)
{
if(childTreeOptions.results[ii].Children == undefined)
{
childTreeOptions.results[ii].Children = ko.observableArray([]);
}
var recordObject = { Fields: {}, SetFields: [], Insert: false };
for (var field in results.rows.item(i)) {
recordObject.Fields[field] = field === "Id" && results.rows.item(i).PrimaryRowId ? results.rows.item(i).PrimaryRowId : results.rows.item(i)[field];
}
childTreeOptions.results[ii].Children.push(recordObject);
childRecordArray.push(recordObject);
}
}
}
}
return childRecordArray;
}
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});
}
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/22380179
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号