performance - 寻找最佳解决方案

Question

考虑这个由作为案例类实例的对象组成的列表：

A, B, Opt(A),C, Opt(D), F, Opt(C), G, Opt(H)

我想规范化这个列表以获得这个结果：

A, B, C, Opt(D), F, G, Opt(H)

如您所见，如果有元素A并且Opt(A)我用 just 或其他方式替换它们A，我必须删除OPT(A)元素。

我想：

• 性能均值的最优解
• 最短解

Answer 1

不是最有效的解决方案，但肯定是一个简单的解决方案。

scala> case class Opt[A](a: A)
defined class Opt

scala> val xs = List(1, 2, Opt(1), 3, Opt(4), 6, Opt(3), 7, Opt(8))
xs: List[Any] = List(1, 2, Opt(1), 3, Opt(4), 6, Opt(3), 7, Opt(8))

scala> xs flatMap {
     |   case o @ Opt(x) => if(xs contains x) None else Some(o)
     |   case x => Some(x)
     | }
res5: List[Any] = List(1, 2, 3, Opt(4), 6, 7, Opt(8))

Answer 2

这可能更简洁一些，因为过滤是您想要的;-)：

scala> List(1,2,3,Some(4),5,Some(5))
res0: List[Any] = List(1, 2, 3, Some(4), 5, Some(5))

scala> res0.filter {
     | case Some(x) => !res0.contains(x)
     | case _ => true
     | }
res1: List[Any] = List(1, 2, 3, Some(4), 5)

编辑：对于大型收藏，最好使用 atoSet或直接使用 a Set。

Answer 3

如果您不关心顺序，那么效率会导致您使用 Set：

xs.foldLeft(Set.empty[Any])({ case (set, x) => x match {
  case Some(y) => if (set contains y) set else set + x
  case y => if (set contains Some(y)) set - Some(y) + y else set + y
}}).toList

或者：

val (opts, ints) = xs.toSet.partition(_.isInstanceOf[Option[_]])
opts -- (ints map (Option(_))) ++ ints toList