list - 基于另一个列表的顺序的列表的插入顺序

Question

我在 Scala 中有一个排序问题，我当然可以用蛮力解决这个问题，但我希望有一个更聪明/更优雅的解决方案。假设我有一个没有特定顺序的字符串列表:

val keys = List("john", "jill", "ganesh", "wei", "bruce", "123", "Pantera")

然后随机地，我随机收到这些键的值(完全公开，我在 akka Actor 中遇到了这个问题，所以事件没有顺序):

def receive:Receive = {
  case Value(key, otherStuff) => // key is an element in keys ...

我想将这些结果存储在 List 中哪里 Value对象的出现顺序与其 key 的顺序相同 keys 中的字段列表。比如我收到前两个 Value后可能会有这个列表消息:

List(Value("ganesh", stuff1), Value("bruce", stuff2))

ganesh出现在 bruce 之前仅仅因为他在 keys中出现得更早列表。收到第三条消息后，我应该按照 keys 建立的顺序将其插入此列表中的正确位置。 .例如，收到 wei我应该将他插入中间:

List(Value("ganesh", stuff1), Value("wei", stuff3), Value("bruce", stuff2))

在此过程中的任何时候，我的列表可能不完整，但按预期顺序排列。由于 key 对我的 Value 来说是多余的数据，一旦值列表完成，我就把它们扔掉。

给我看看你有什么!

Answer 1

我想你想要的不会比 O(n log n) 差表现。所以:

val order = keys.zipWithIndex.toMap
var part = collection.immutable.TreeSet.empty[Value](
  math.Ordering.by(v => order(v.key))
)

然后你只需添加你的项目。

scala> part = part + Value("ganesh", 0.1)
part: scala.collection.immutable.TreeSet[Value] = 
  TreeSet(Value(ganesh,0.1))

scala> part = part + Value("bruce", 0.2)
part: scala.collection.immutable.TreeSet[Value] =
  TreeSet(Value(ganesh,0.1), Value(bruce,0.2))

scala> part = part + Value("wei", 0.3)
part: scala.collection.immutable.TreeSet[Value] = 
  TreeSet(Value(ganesh,0.1), Value(wei,0.3), Value(bruce,0.2))

完成后，您可以 .toList它。在构建它时，您可能不想这样做，因为以随机顺序更新列表以使其处于所需的排序顺序是强制性的 O(n^2)成本。

编辑:以您的七个项目为例，我的解决方案大约需要让-菲利普的时间的 1/3。对于 25 个项目，它是时间的 1/10。 200 的 1/30(这是我机器上 6 毫秒和 0.2 毫秒之间的差异)。