Effective Scala

目录

• Ordering
• TopN
• Cut

本文积累一些高效的scala写法。

Ordering

toSeq is not good idea because driver needs to put this in memory

.sortWith(_._2 >_._2) // short for [ (x,y) => x > y ]
// need 2x as much memory？
k.sortBy(x => (x._3,x._2,x._1))

但是通过函数传递ordering的方式比较慢，直接Ordering.by创建内置的Ordering，或者按照下面的自定义写法更好。

implicit def t3Ordering(implicit intOrdering: Ordering[Int]) = new Ordering[Tuple3[Int,Int,Int]] {
    def compare(x: (Int,Int),y: (Int,Int)): Int = {
        val compare3 = intOrdering.compare(x._3,y._3)
        if (compare3 != 0) return compare3
        val compare2 = intOrdering.compare(x._2,y._2)
        if (compare2 != 0) return compare2
        val compare1 = intOrdering.compare(x._1,y._1)
        if (compare1 != 0) return compare1
        0
    }
}

// 更标准的方式
implicit def t3Ordering[T1,T2,T3](implicit ord1: Ordering[T1],ord2: Ordering[T2],ord3: Ordering[T3]) = new Ordering[Tuple3[T1,T3]] {
  def compare(x: (T1,T3),y: (T1,T3)): Int = {
      val compare3 = ord3.compare(x._3,y._3)
      if (compare3 != 0) return compare3
      val compare2 = ord2.compare(x._2,y._2)
      if (compare2 != 0) return compare2
      val compare1 = ord1.compare(x._1,y._1)
      if (compare1 != 0) return compare1
      0
  }
}

参考：https://stackoverflow.com/questions/41918826/how-to-order-my-tuple-of-spark-results-descending-order-using-value
参考： https://stackoverflow.com/questions/27659589/how-to-order-a-list-of-tuples-of-integers-in-scala

TopN

// 方法1，静态数据
def firstK[A](xs: Seq[A],k: Int)(implicit ord: Ordering[A]) = {
val q = new scala.collection.mutable.PriorityQueue[A]()(ord.reverse)
// 初始化PriorityQueue
val (before,after) = xs.splitAt(k)
q ++= before
 
after.foreach(x => q += ord.max(x,q.dequeue))
q.dequeueAll
}

// 方法1，流数据
def firstK[A](iter: Iterator[A],k: Int)(implicit ord: Ordering[A]) = {
val q = new scala.collection.mutable.PriorityQueue[A]()(ord.reverse)
// 初始化PriorityQueue
var i = k
var flag = true
while (flag && iter.hasNext){
 q.enqueue(iter.next())
 i -=1
 if(i == 0){
   flag = false
 }
}

iter.foreach(x => q += ord.max(x,q.dequeue))
q.dequeueAll
}

// 方法2
java.util.Arrays.sort(a)
val resOfSort = a.takeRight(TopN).toList

// 方法3，最方便，但效率最低。
arr.sortWith(_>_).take(TopN)

测试环境基于 MBP 17 i5 下的 IDEA

方法1受到Top大小影响，当数组1亿数据，n=1：2s，n=10：5s，当n=1000以上，就不及方法2了。iter方面相似。

对于静态数据，selection algorithm可能是更好的选择，但没有现成的代码，需要自己码。有兴趣可参考leetcode215数组中的第K个最大元素。

对于流数据，方法2和3都需要把数据源进行转化，一定程度上降低了效率，而且必须把数据全部加载到内存。

方法1参考自 https://stackoverflow.com/questions/7792189/scala-what-is-the-most-appropriate-data-structure-for-sorted-subsets/7792837#7792837

Cut

截取数组时用take，不用slide