Scala的第一步:这看起来像惯用的吗？

Question

我是Scala世界的新手，我想从更有经验的人那里得到一些建议，看看我正在写的东西是否朝着习惯代码的方向发展。

特别是，我必须编写一个简单的算法来完成以下工作。我们得到了一个整数，例如，要分发的糖果数，以及一个比例列表，这些比例也是整数。我们应该把糖果分成几组，这样就能尽可能准确地尊重糖果的比例，因为一颗糖果是分不开的。

例如，如果17糖果按(3, 2, 5)的比例分配，我们就应该获得(5, 4, 8)。

这是我的代码，包括一个快速的ScalaCheck测试。

import org.scalacheck.Prop._
import org.scalacheck.Gen

object Distribution {
    private class IntWithDivision(val self: Int) {
        def @/(other: Int): Float = self.toFloat / other
    }

    private implicit def divisibleInt(int: Int) = new IntWithDivision(int)

    def distribute(amount: Int, proportions: Seq[Int]): Seq[Int] = {
        val sum = proportions.sum
        val byDifect = proportions map { x => (amount * x @/ sum).toInt }
        val approximations = (byDifect, proportions).zipped map { (x, y) => x @/ y }
        val lowValuesIndices = (
            approximations.view.zipWithIndex
            sortBy { _._1 }
            take (amount - byDifect.sum)
            map { _._2 }
        ).force
        val remainders = (
            approximations.view.zipWithIndex
            map { x => if (lowValuesIndices contains x._2) 1 else 0 }
        ).force

        (byDifect, remainders).zipped map { _ + _ }
    }

    def main(args: Array[String]) {
        val pos = Gen.choose(1, 50000)
        val posList = Gen.containerOf[List, Int](pos)
        val propSum = forAll(pos, posList) { (amount: Int, proportions: List[Int]) =>
            (proportions.size > 0) ==> (amount == distribute(amount, proportions).sum)
        }
        propSum.check
    }
}

我特别想就以下各点提供意见：

• 该算法遍历比例列表并推导出几次列表。我想使用更多的惰性，但是在开始使用proportions.view，然后返回一个force会产生一个类型错误。
• 代码比我想的要复杂得多。我认为它可以简化，更好地了解集合API。

欢迎任何帮助或建议。

Answer 1

好吧，我现在改变答案了，因为我明白你在做什么。

这里的主要问题是@/ --虽然Scala的人一般不介意特殊的操作符，但是他们不会仅仅因为他们可以添加操作符而添加操作符。您可以将@/替换为现有的/，只需将.toFloat添加到任何一个术语中即可。

视图也不常被使用，如果你要使用视图的话，了解它们的工作原理也是很重要的，而且使用视图也不是那么容易，因为它们用来支持非严格性的机器很重，而且不是所有的东西都能利用它。例如，sortBy将在应用take和map之前创建一个新集合。

当您有许多映射/切片步骤，并且很少使用它的元素时，视图就可以获得。大多数情况下，迭代器将以迭代器所具有的易变性问题为代价，为您提供更高的性能。

如果您想减少迭代比例列表的次数，那么至少有一个地方可以简化：

    val remainders = (
        approximations.view.zipWithIndex
        map { x => if (lowValuesIndices contains x._2) 1 else 0 }
    ).force

    (byDifect, remainders).zipped map { _ + _ }

可以被还原为

    byDifect.zipWithIndex map {
      case (bd, i) => bd + (if (lowValuesIndices contains i) 1 else 0)
    }

我们还可以将byDifect保留为一个Float，然后在计算approximation时单独使用它(而不是压缩的东西)，或者跳过这一点，将计算放到sortBy上--计算O(nlogn)次数而不是O(n)次的成本。它将使代码更短，但它是否更快是我留给一个真正的应用程序的基准测试--我猜它将取决于proportions的实际大小。

那么，让我们来谈谈性能。在Scala2.10之前，如果您想要获得性能，您应该避免通过在关键路径上插入而添加的方法。您编写的代码可能会被JIT内联。您还可以通过预计算amount / sum减少计算次数，如果您制作了amount.toFloat / sum，那么您就不需要/@了。

更具体地说，视图不能保证速度，特别是在计算量很小的情况下，比如这里。我根本不会使用它们，除非我正在具体地优化代码。

在小数据结构上进行固定大小的多次传递通常不是问题。您不会改变复杂性，只会丢失内存局部性。如果数据更大，您可能会招致gc间接费用，这会更大。如果需要最大的性能，只需删除不可变并转到可变数组即可。

最后，contains在Set上的速度比Seq快--在这种情况下，BitSet要快得多。但是，称它为apply，因为contains是可遍历的通用方法，而set的应用是一种基本操作。如果其中一个没有经过优化，它将是contains。

这是我见过的最地道的初学者代码..。你来自另一种功能语言吗？