获取Scala Iterable的前n个元素的最简单方法

Question

是否有一个简单而有效的解决方案来确定Scala Iterable的前n个元素？我的意思是

iter.toList.sortBy(_.myAttr).take(2)

但是当只有前2名感兴趣时,无需对所有元素进行排序.理想情况下,我正在寻找类似的东西

iter.top(2, _.myAttr)

另请参阅:使用Ordering的顶部元素的解决方案:在Scala中,如何使用List.min或List.max订购[T]并保持代码可读

更新:

谢谢大家的解决方案.最后,我采用了用户未知的原始解决方案并使用它Iterable和pimp-my-library模式:

implicit def iterExt[A](iter: Iterable[A]) = new {
  def top[B](n: Int, f: A => B)(implicit ord: Ordering[B]): List[A] = {
    def updateSofar (sofar: List [A], el: A): List [A] = {
      //println (el + " - " + sofar)

      if (ord.compare(f(el), f(sofar.head)) > 0)
        (el :: sofar.tail).sortBy (f)
      else sofar
    }

    val (sofar, rest) = iter.splitAt(n)
    (sofar.toList.sortBy (f) /: rest) (updateSofar (_, _)).reverse
  }
}

case class A(s: String, i: Int)
val li = List (4, 3, 6, 7, 1, 2, 9, 5).map(i => A(i.toString(), i))
println(li.top(3, _.i))

Answer 1

我的解决方案(绑定到Int,但应该很容易更改为Ordered(请几分钟):

def top (n: Int, li: List [Int]) : List[Int] = {

  def updateSofar (sofar: List [Int], el: Int) : List [Int] = {
    // println (el + " - " + sofar)
    if (el < sofar.head) 
      (el :: sofar.tail).sortWith (_ > _) 
    else sofar
  }

  /* better readable:
    val sofar = li.take (n).sortWith (_ > _)
    val rest = li.drop (n)
    (sofar /: rest) (updateSofar (_, _)) */    
  (li.take (n). sortWith (_ > _) /: li.drop (n)) (updateSofar (_, _)) 
}

用法:

val li = List (4, 3, 6, 7, 1, 2, 9, 5)    
top (2, li)

• 对于上面的列表,将前2(4,3)作为起始TopTen(TopTwo).
• 对它们进行排序,使得第一个元素是较大的元素(如果有的话).
• 重复遍历列表的其余部分(li.drop(n)),并将当前元素与最小值列表的最大值进行比较; 如有必要,请更换,并再次使用.
• 改进:
  • 丢掉Int,并使用有序.
  • 扔掉(_> _)并使用用户排序以允许BottomTen.(更难:挑中间10 :))
  • 扔掉List,然后使用Iterable

更新(抽象):

def extremeN [T](n: Int, li: List [T])
  (comp1: ((T, T) => Boolean), comp2: ((T, T) => Boolean)):
     List[T] = {

  def updateSofar (sofar: List [T], el: T) : List [T] =
    if (comp1 (el, sofar.head)) 
      (el :: sofar.tail).sortWith (comp2 (_, _)) 
    else sofar

  (li.take (n) .sortWith (comp2 (_, _)) /: li.drop (n)) (updateSofar (_, _)) 
}

/*  still bound to Int:  
def top (n: Int, li: List [Int]) : List[Int] = {
  extremeN (n, li) ((_ < _), (_ > _))
}
def bottom (n: Int, li: List [Int]) : List[Int] = {
  extremeN (n, li) ((_ > _), (_ < _))
}
*/

def top [T] (n: Int, li: List [T]) 
  (implicit ord: Ordering[T]): Iterable[T] = {
  extremeN (n, li) (ord.lt (_, _), ord.gt (_, _))
}
def bottom [T] (n: Int, li: List [T])
  (implicit ord: Ordering[T]): Iterable[T] = {
  extremeN (n, li) (ord.gt (_, _), ord.lt (_, _))
}

top (3, li)
bottom (3, li)
val sl = List ("Haus", "Garten", "Boot", "Sumpf", "X", "y", "xkcd", "x11")
bottom (2, sl)

用Iterable替换List似乎有点困难.

正如Daniel C. Sobral在评论中指出的那样,ntopN中的高位可以导致很多排序工作,因此可以使用手动插入排序而不是重复排序top-n元素的整个列表:

def extremeN [T](n: Int, li: List [T])
  (comp1: ((T, T) => Boolean), comp2: ((T, T) => Boolean)):
     List[T] = {

  def sortedIns (el: T, list: List[T]): List[T] = 
    if (list.isEmpty) List (el) else 
    if (comp2 (el, list.head)) el :: list else 
      list.head :: sortedIns (el, list.tail)

  def updateSofar (sofar: List [T], el: T) : List [T] =
    if (comp1 (el, sofar.head)) 
      sortedIns (el, sofar.tail)
    else sofar

  (li.take (n) .sortWith (comp2 (_, _)) /: li.drop (n)) (updateSofar (_, _)) 
}

上/下方法和用法如上.对于小组的顶部/底部元素,很少调用排序,在开始时几次,然后随着时间的推移越来越少.例如,70次顶部(10)的10 000次,90次顶部(10次)10万次.

Answer 2

又一个版本:

val big = (1 to 100000)

def maxes[A](n:Int)(l:Traversable[A])(implicit o:Ordering[A]) =
    l.foldLeft(collection.immutable.SortedSet.empty[A]) { (xs,y) =>
      if (xs.size < n) xs + y
      else {
        import o._
        val first = xs.firstKey
        if (first < y) xs - first + y
        else xs
      }
    }

println(maxes(4)(big))
println(maxes(2)(List("a","ab","c","z")))

使用Set强制列表具有唯一值:

def maxes2[A](n:Int)(l:Traversable[A])(implicit o:Ordering[A]) =
    l.foldLeft(List.empty[A]) { (xs,y) =>
      import o._
      if (xs.size < n) (y::xs).sort(lt _)
      else {
        val first = xs.head
        if (first < y) (y::(xs - first)).sort(lt _)
        else xs
      }
    }

Answer 3

这是另一种简单且性能相当不错的解决方案.

def pickTopN[T](k: Int, iterable: Iterable[T])(implicit ord: Ordering[T]): Seq[T] {
  val q = collection.mutable.PriorityQueue[T](iterable.toSeq:_*)
  val end = Math.min(k, q.size)
  (1 to end).map(_ => q.dequeue())
}

大O是O(n + k log n),在哪里k <= n.因此,对于小的k和最坏的情况,性能是线性的n log n.

该解决方案还可以针对O(k)内存而非O(n log k)性能进行优化.我们的想法是使用MinHeap始终只跟踪顶级k项目.这是解决方案.

def pickTopN[A, B](n: Int, iterable: Iterable[A], f: A => B)(implicit ord: Ordering[B]): Seq[A] = {
  val seq = iterable.toSeq
  val q = collection.mutable.PriorityQueue[A](seq.take(n):_*)(ord.on(f).reverse) // initialize with first n

  // invariant: keep the top k scanned so far
  seq.drop(n).foreach(v => {
    q += v
    q.dequeue()
  })

  q.dequeueAll.reverse
}