1

我正在用 Scala 解决荷兰国旗问题，并提出以下代码：

def dutchNationalFlag[T](a: Array[T])(implicit ordering: Ordering[T]) = {
  def sort(lo: Int, hi: Int): Unit = {
    Stream.iterate((lo, hi, lo + 1)) { acc =>
      val (lt, gt, i) = acc

      if (ordering.lt(a(i), a(lt))) {
        swap(lt, i, a)
        (lt + 1, gt, i + 1)
      } else if (ordering.gt(a(i), a(gt))) {
        swap(gt, i, a)
        (lt, gt - 1, i)
      } else {
        (lt, gt, i + 1)
      }
    }
      .takeWhile(acc => acc._2 >= acc._3)
      .lastOption
      .foreach { acc =>
        val (lt, gt, _) = acc

        sort(lo, lt - 1)
        sort(gt + 1, hi)
      }
  }

  sort(0, a.length - 1)
}

出于性能原因，我想修改现有数组，而不是创建一个新数组。swap上面的代码可以工作，但是在调用 from时有明显的副作用iterate，这在纯函数式代码中是有问题的。我考虑用swap稍后执行的方法引用替换foreach，类似于 Haskell IO，但正如您可以想象的那样，这样做会使代码有些复杂。

其他想法？

4

2 回答 2

0

以下是我倾向于解决问题的方法

def sort[T](low: T, high: T)(items: List[T])(implicit ordering: Ordering[T])=
{
  val groupedItems = items.groupBy
  {
    _ match
    {
      case item if ordering.lt(item,low) => 0
      case item if ordering.gt(item,high) => 2
      case _ => 1
    }
  }
  groupedItems(0) ++ groupedItems(1) ++ groupedItems(2)
}

这可能比编写 Java 或 C 风格的代码效率低。一般来说，这是可以的。Scala 编译器非常擅长优化事物，并且性能通常足够接近，以至于您不会真正注意到差异。如果您打算对大量数据执行此操作，Scala 版本的优势在于它已经是一种并行算法。如果你调用.par输入列表，你会得到一个并行集合，它将跨多个核心/线程运行操作。如果更改List[T]为org.apache.spark.rdd.RDD[T]，则代码已准备好在具有数十台机器的分布式集群上运行。

于 2018-07-23T14:10:56.493 回答
0

在将命令式算法转换为纯函数式算法时，“出于性能原因改变数组”是一个经典问题，但是如果您对数据结构更加聪明，那么有很多方法可以解决它。例如，如果你像这样表示你的数组怎么办：

class RearrangedArray[A](elements: Array[A], indexMap: Map[Int, Int] = Map.empty) {
  def apply(i: Int): A = elements(indexMap.getOrElse(i, i))
  def swap(i: Int, j: Int): RearrangedArray = {
    val newMap = indexMap + (i -> indexMap.getOrElse(j, j)) + (j -> indexMap.getOrElse(i, i))
    new RearrangedArray(elements, newMap)
  }
  def toArray: Array[A] = {
    (0 until elements.size).map(apply).toArray
  }
}

请注意，它是完全不可变的，使用 O(n) 内存，交换和查找在恒定时间内发生......所有相同的性能特征，但您可以在每次迭代中创建一个新的并将其与索引一起传递以使其完全参照透明。与其改变数组，不如让所有函数都将其中一个作为参数，并返回一个新的作为结果。

于 2018-07-20T22:36:10.293 回答