代码之家 › 专栏 › 技术社区 › Smokey Dawson

根据独立数组的顺序对数组集合排序的最有效方法

javascript

Smokey Dawson · 技术社区 · 6 年前

是的,我知道类似的问题,但这里并没有完全涵盖我的用例。

我很难找到一种方法来降低这件事的时间复杂性

我有两样东西

const people = [
  {
    name: 'Steve',
    id: 1,
    fruitInBasket: 6
  },
  {
    name: 'James',
    id: 2,
    fruitInBasket: 4
  }
]

const homes = [
  {
    id: 1,
    familyMembers: [
      {
        name: 'James',
        id: 2
      },
      {
        name: 'Steve',
        id: 1
      }
    ]
  },
  {
    id: 2,
    familyMembers: [
      {
        name: 'James',
        id: 2
      },
      {
        name: 'Steve',
        id: 1
      }
    ]
  }
]

其中一个是 people 一个篮子里有一堆水果,另一个是 homes 在每个家庭中都有相同的用户收藏。

现在我想根据 fruitInBasket 所以我做到了

// create an empty table to store the order of the people
let orderTable = {};

// order the people based off the count in fruitInBasket using lodash orderBy
people = orderBy(people, ['fruitInBasket'], ['desc']);

// create the table 
orderTable = people.reduce((acc, item, index) => {
  return {
    ...acc,
    [item.id]: index
  }
}, {});

// order the people in each home based on the order in the `orderTable`
homes.forEach((home) => {
  let members = [];
  home.familyMembers.forEach((member) => {
    let i = orderTable[member.id];
    members[i] = member;
  });
  home.familyMembers = members;
})

因此,您可以立即看到一个嵌套的for循环,这是不理想的。。但我想不出办法。这种方法必须对大量数据进行排序,我注意到了巨大的性能问题。

2 回复 | 直到 6 年前

djcaesar9114 6 年前

您可以筛选和排序:

const people = [
  {
    name: 'Steve',
    id: 1,
    fruitInBasket: 6
  },
  {
    name: 'James',
    id: 2,
    fruitInBasket: 4
  },
  {
    name: 'Cesar',
    id: 3,
    fruitInBasket: 14
  }
]

const homes = [
  {
    id: 1,
    familyMembers: [
      {
        name: 'James',
        id: 2
      },
      {
        name: 'Cesar',
        id: 3
      },
      {
        name: 'Steve',
        id: 1
      }
      
    ]
  },
  {
    id: 2,
    familyMembers: [
      {
        name: 'James',
        id: 2
      },
      {
        name: 'Steve',
        id: 1
      }
    ]
  }
]

homes.forEach(function(home){
  home.familyMembers.sort((a,b)=>people.find(x=>x.id == a.id).fruitInBasket - people.find(x=>x.id == b.id).fruitInBasket)
})

console.log(homes)

说明:

您将遍历homes:

homes.forEach(function(home){

.familyMembers.sort((a,b)

要排序,您必须获取成员的结果,以便找到正确的ID,然后使用正确的属性:

people.find(x=>x.id == a.id).fruitInBasket

然后比较:

(a,b)=>people.find(x=>x.id == a.id).fruitInBasket - people.find(x=>x.id == b.id).fruitInBasket

people 结构:

const people = {
  1:  {
    name: 'Steve',
    fruitInBasket: 6
  },
  2: {
    name: 'James',
    fruitInBasket: 4
  }
}

people[id].fruits

另外,如果你的“id”是在某个地方定义的,不要在另一个地方定义它。你的 homes 应该是这样的:

const homes = {
  1:  {
    familyMembers: [1, 2, 3]  
  },
  2: {
    familyMembers: [1,2]
  }
}

const people = {
  1:  {
    name: 'Steve',
    fruitInBasket: 6
  },
  3: {
    name: 'James',
    fruitInBasket: 4
  },
  2: {
    name: 'Cesar',
    fruitInBasket: 9114
  }
}

const homes = {
  1:  {
    familyMembers: [1, 2, 3]  
  },
  2: {
    familyMembers: [1,2]
  }
}

Object.keys(homes).forEach(function(k){
  homes[k].familyMembers.sort((a,b)=>people[a].fruitInBasket - people[b].fruitInBasket)
})

console.log(homes)

user120242 6 年前

这应该是O(N logn)。其性能瓶颈是一次性排序。其他一切都只是O(N)迭代。一些微优化仍然是可能的。

只需根据映射移动数组。

每个home的额外优化可以是将上述表转换为索引到索引映射,以便本机级别的数组索引将用于后续排序。

const orderMap = Object.fromEntries(people.sort((x,y)=>x.fruitInBasket-y.fruitInBasket).map(({id},i)=>[id,i]))
// O(N)+O(NlogN)

homes.forEach(home=>{
const {familyMembers:fms} = home
const arr = new Array(fms.length)
//may want to prefill to maintain PACKED array: https://v8.dev/blog/elements-kinds#avoid-creating-holes
for(const fm of fms) arr[ orderMap[fm.id] ] = fm
home.familyMembers = arr
})
// map lookup O(N)

console.log(homes)

<script>
const people = [
  {
    name: 'Steve',
    id: 1,
    fruitInBasket: 6
  },
  {
    name: 'James',
    id: 2,
    fruitInBasket: 9
  }
]
const homes = [
  {
    id: 1,
    familyMembers: [
      {
        name: 'James',
        id: 2
      },
      {
        name: 'Steve',
        id: 1
      }
    ]
  },
  {
    id: 2,
    familyMembers: [
      {
        name: 'James',
        id: 2
      },
      {
        name: 'Steve',
        id: 1
      }
    ]
  }
]
</script>