获取Scala迭代器的前n个元素的最简单方法

一尘不染

获取Scala迭代器的前n个元素的最简单方法

algorithm

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

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

但是当只关注前2个元素时，不必对所有元素进行排序。理想情况下，我正在寻找类似的东西

iter.top(2, _.myAttr)

更新：

谢谢大家的解决方案。最后，我采用了 未知用户 的原始解决方案，并采用了它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))

阅读 1982

2020-07-28

共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 ：））
- 丢弃列表，并改用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 (_, _)) 
}

上面/下面的方法和用法。对于顶部/底部元素的小组，排序很少被调用，在开始时几次，然后随着时间的推移越来越少。例如，最高（10）为10000的70次，最高（10）为100000的90次。

2020-07-28