我正在嘗試運行資料庫遷移，并且遇到了按時間順序排列的問題。我無法改變這種行為，所以我必須以某種方式處理它。
假設我有以下陣列，
const arr = [
{ model: 'modelE', associations: ['modelA'], order: 1 },
{ model: 'modelA', associations: [ 'modelB' ], order: 2 },
{ model: 'modelB', associations: [], order: 3 },
{ model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
{ model: 'modelD', associations: ['modelA'], order: 5 },
{ model: 'modelF', associations: [], order: 6 },
]
眾所周知，我們必須按順序創建這些表，否則無法創建外鍵，因此會拋出錯誤。
在這種情況下，我們有modelE,modelC并且modelD依賴于modelA, 但modelA依賴于modelB, 所以modelB必須是這個陣列中的第一個元素，因為它必須是要創建的第一個表。
結果陣列應如下所示：
const arr = [
{ model: 'modelB', associations: [], order: 1 },
{ model: 'modelF', associations: [], order: 2 },
{ model: 'modelA', associations: [ 'modelB' ], order: 3 },
{ model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
{ model: 'modelE', associations: ['modelC'], order: 5 },
{ model: 'modelD', associations: ['modelA'], order: 6 },
]
有沒有一種有效的方法來做到這一點？我能想到的就是運行一個里面sort有 s 的函式。arr.find不確定這是否太高效甚至可讀。
uj5u.com熱心網友回復：
您正在尋找拓撲排序。
您可以為此使用深度優先演算法：
function topoSort(arr) {
const visited = new Set;
const map = new Map(arr.map(({model, associations}) => [model, associations]));
function dfs(models) {
for (let model of models) {
if (visited.has(model)) continue;
dfs(map.get(model));
visited.add(model);
}
}
dfs([...map.keys()]);
return Array.from(visited, (model, i) =>
({model, associations: map.get(model), order: i 1})
);
}
const arr = [
{ model: 'modelE', associations: ['modelA'], order: 1 },
{ model: 'modelA', associations: [ 'modelB' ], order: 2 },
{ model: 'modelB', associations: [], order: 3 },
{ model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
{ model: 'modelD', associations: ['modelA'], order: 5 },
{ model: 'modelF', associations: [], order: 6 },
]
const result = topoSort(arr);
console.log(...result);uj5u.com熱心網友回復：
const sortArrayByDependency = (arr) => {
const sorted = [];
const foundSet = new Set();
const maxLoop = arr.length;
let loopCount = 0;
while(arr.length > 0 && loopCount < maxLoop) {
loopCount = 1;
const first = arr.shift();
if(first.associations.every(ele => foundSet.has(ele))){
sorted.push({...first, order: sorted.length 1 });
foundSet.add(first.model)
}
else {
arr.push(first)
}
}
return sorted;
}
const arr = [
{ model: 'modelB', associations: [], order: 1 },
{ model: 'modelF', associations: [], order: 2 },
{ model: 'modelA', associations: [ 'modelB' ], order: 3 },
{ model: 'modelC', associations: ['modelA', 'modelB'], order: 4 },
{ model: 'modelE', associations: ['modelC'], order: 5 },
{ model: 'modelD', associations: ['modelA'], order: 6 },
]
console.log(sortArrayByDependency(arr))轉載請註明出處，本文鏈接：https://www.uj5u.com/net/475937.html
標籤：javascript