8

让我们假设我有以下两个序列：

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)
4

7 回答 7

4

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

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

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

ids.map(idToEntityMap _)
于 2013-09-03T11:30:03.257 回答
3

这可能与您的用例不完全对应，但 Google 员工可能会发现这很有用：

scala> val ids = List(3, 1, 0, 2)
ids: List[Int] = List(3, 1, 0, 2)

scala> val unsorted = List("third", "second", "fourth", "first")
unsorted: List[String] = List(third, second, fourth, first)

scala> val sorted = ids map unsorted
sorted: List[String] = List(first, second, third, fourth)
于 2015-05-13T23:36:21.153 回答
1

我能做的最好的事情是Map从未排序的数据中创建一个，并使用地图查找（基本上是以前的海报建议的哈希表）。代码如下所示：

val unsortedAsMap = unsorted.map(x => x -> x).toMap
index.map(unsortedAsMap)

或者，如果有哈希未命中的可能性：

val unsortedAsMap = unsorted.map(x => x -> x).toMap
index.flatMap(unsortedAsMap.get)

它是O(n)及时的*，但你正在用时间交换空间，因为它使用O(n)空间。

对于处理缺失值的稍微复杂的版本，请尝试：

import scala.collection.JavaConversions._
import scala.collection.mutable.ListBuffer

val unsortedAsMap = new java.util.LinkedHashMap[Int, Int]
for (i <- unsorted) unsortedAsMap.add(i, i)

val newBuffer = ListBuffer.empty[Int]
for (i <- index) {
  val r = unsortedAsMap.remove(i)
  if (r != null) newBuffer += i
  // Not sure what to do for "else"
}

for ((k, v) <- unsortedAsMap) newBuffer += v

newBuffer.result()

如果它首先是一个 MongoDB 数据库，那么您可能会更好地通过索引直接从数据库中检索文档，例如：

index.map(lookupInDB)

*从技术上讲，它O(n log n)是 Scala 的标准不可变映射O(log n)，但您始终可以使用可变映射，即O(1)

于 2013-09-02T16:07:17.880 回答
1

在这种情况下，您可以使用 zip-sort-unzip：

(unsorted zip index).sortWith(_._2 < _._2).unzip._1

顺便说一句，如果可以的话，更好的解决方案是使用$orderBy在数据库端对列表进行排序。

于 2013-09-02T16:09:17.733 回答
1

我不知道您使用的语言。但无论语言如何，这都是我解决问题的方式。

从第一个列表（此处为“索引”）创建一个哈希表，其中键作为文档 ID，值作为文档在排序顺序中的位置。

现在，当遍历文档列表时，我将使用文档 ID 查找哈希表，然后获取它应该按排序顺序排列的位置。然后我会使用这个获得的顺序在预分配的内存中进行排序。

注意：如果文档数量很少，那么您可以使用预先分配的表并使用文档 ID 直接对其进行索引，而不是使用哈希表。

于 2013-09-02T15:58:43.103 回答
1

将索引映射到未排序的列表似乎是一个更安全的版本（如果找不到索引，它会因为find返回 a而被删除None）：

index.flatMap(i => unsorted.find(_ == i))

它仍然必须每次都遍历未排序的列表（最坏的情况是 O(n^2)）。以您为例，我不确定是否有更有效的解决方案。

于 2013-09-02T15:58:59.283 回答
1

好的。

让我们从头开始。除了您unsorted每次都重新扫描列表这一事实之外Seq，默认情况下，该对象将创建一个List集合。因此，foldLeft您每次都在列表末尾附加一个元素，这是一个O(N^2)操作。

一个改进将是

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

但这仍然是一种O(N^2)算法。我们可以做得更好。

以下排序功能应该可以工作：

def sort[T: ClassTag, Key](index: Seq[Key], unsorted: Seq[T], key: T => Key): Seq[T] = {
  val positionMapping = HashMap(index.zipWithIndex: _*) //1
  val arr = new Array[T](unsorted.size) //2
  for (item <- unsorted) { //3
    val position = positionMapping(key(item))
    arr(position) = item
  }
  arr //6
}

该函数unsorted通过一系列索引对项目列表进行排序index，该key函数将用于从您尝试排序的对象中提取 id。

第 1 行创建一个反向索引 - 将每个对象 id 映射到其最终位置。

第 2 行分配将保存已排序序列的数组。我们使用数组是因为我们需要恒定时间的随机位置集性能。

从第 3 行开始的循环将遍历未排序项目的序列，并使用positionMapping反向索引将每个项目放置在它的预期位置

第 6 行将返回Seq使用WrappedArray包装器隐式转换为 a 的数组。

由于我们的反向索引是不可变的HashMap，因此对于常规情况，查找应该花费恒定时间。构建实际的反向索引需要O(N_Index)时间，其中N_Index索引序列的大小是多少。遍历未排序的序列需要O(N_Unsorted)时间，其中未排序序列N_Unsorted的大小是多少。

所以复杂性是O(max(N_Index, N_Unsorted))，我想这是在这种情况下你能做的最好的事情。

对于您的特定示例，您可以像这样调用该函数：

val sorted = sort(index, unsorted, identity[Int])

对于实际情况，它可能是这样的：

val sorted = sort(idList, unsorted, obj => obj.id)
于 2013-09-02T16:20:03.180 回答