按有序索引对列表进行排序

Question

我们假设我有以下两个序列:

val index = Seq(2,5,1,4,7,6,3)
val unsorted = Seq(7,6,5,4,3,2,1)

第一个是应该对第二个进行排序的索引.我目前的解决方案是遍历索引并使用未排序序列中找到的元素构造一个新序列.

val sorted  = index.foldLeft(Seq[Int]()) { (s, num) => 
  s ++ Seq(unsorted.find(_ == num).get)
}

但是这个解决方案似乎非常低效且容易出错.在每次迭代时,它都会搜索完整的未排序序列.如果索引和未排序列表不同步,则会抛出错误或省略元素.在这两种情况下,不同步元素都应附加到有序序列中.

对于这个问题,是否有更有效和可靠的解决方案？还是有一种适合这种范式的排序算法？

---

注意:这是一个构造的例子.实际上,我想通过文档Id的有序列表对mongodb文档列表进行排序.

---

更新1

我选择了Marius Danila的答案,因为它似乎是解决我问题的最快速和最快速的解决方案.它没有非同步项解决方案,但这可以很容易地实现.

所以这是更新的解决方案:

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = {
  val positionMapping = HashMap(index.zipWithIndex: _*)
  val inSync = new Array[T](unsorted.size)
  val notInSync = new ArrayBuffer[T]()
  for (item <- unsorted) {
    if (positionMapping.contains(key(item))) {
      inSync(positionMapping(key(item))) = item
    } else {
      notInSync.append(item)
    }
  }

  inSync.filterNot(_ == null) ++ notInSync
}

---

更新2

Bask.cc建议的方法似乎是正确的答案.它也不考虑不同步问题,但这也可以很容易地实现.

val index: Seq[String]
val entities: Seq[Foo]
val idToEntityMap = entities.map(e => e.id -> e).toMap
val sorted = index.map(idToEntityMap)
val result = sorted ++ entities.filterNot(sorted.toSet)

Answer 1

当你已经有排序的索引集合时，为什么要对集合进行排序？你可以只使用地图

关于>实际上，我想通过文档 ID 的有序列表对 mongodb 文档列表进行排序。

val ids: Seq[String]
val entities: Seq[Foo]
val idToEntityMap = entities.map(e => e.id -> e).toMap

ids.map(idToEntityMap _)