最简单的获得斯卡拉可迭代的前n个元素的方法 [英] Simplest way to get the top n elements of a Scala Iterable

问题描述

有一个简单而有效的解决方案，以确定斯卡拉可迭代的前n个元素呢？我的意思是这样

  iter.toList.sortBy（_。myAttr）。取（2）
 

但无需所有元素进行排序仅当顶部2是感兴趣。理想的情况是我在寻找类似

  iter.top（2，_.myAttr）
 

另见：解决方案使用订购的顶级元素：在Scala中，如何使用订货[T]与List.min或列表。 max和保持code可读

更新：

感谢大家的解决方案。最后，我注意到的用户未知的原始解决方案，并通过它来使用可迭代和皮条客，我的库的模式：

 隐高清iterExt [A]（ITER：可迭代[A]）=新{
  DEF顶部[B]（N：智力，F：A =＆GT; B）（隐含ORD：订货[B]）：名单[A] = {
    高清updateSofar（SOFAR：名单[A]报：A）：列表[A] = {
      //调用println（EL + - + SOFAR）

      如果（ord.compare（六（EL）中，f（sofar.head））大于0）
        （EL :: sofar.tail）.sortBy（F）
      其他SOFAR
    }

    VAL（SOFAR，休息）= iter.splitAt（N）
    （sofar.toList.sortBy（F）/：休息）（updateSofar（_，_））逆转。
  }
}

案例A级（S：字符串，我的：int）
VAL丽=列表（4，3，6，7，1，2，9,5）.MAP（ⅰ=＆gt;一种（i.toString（），i））的
的println（li.top（3，_.i））
 

解决方案

我的解决方案（绑定到中等，但应该很容易变为有序（几分钟，请）：

 高清顶部（N：智力，李：列表[INT]）：列表[INT] = {

  高清updateSofar（SOFAR：列表[INT]报：智力）：列表[INT] = {
    //调用println（EL + - + SOFAR）
    如果（EL＆LT; sofar.head）
      （EL :: sofar.tail）.sortWith（_＆GT; _）
    其他SOFAR
  }

  / *更好的可读性：
    VAL SOFAR = li.take（N）.sortWith（_＆GT; _）
    VAL休息= li.drop（N）
    （SOFAR /：休息）（updateSofar（_，_））* /
  （li.take（N）sortWith（_＆GT; _）/：li.drop（N））（updateSofar（_，_））
}
 

用法：

  VAL李=清单（4，3，6，7，1，2，9，5）
顶（2，李）
 

• 对于上面的列表中，取前2（4,3）为起始十佳电器（TopTwo）。
• 排序它们，使得第一元件是更大的一个（如果有的话）。
• 通过列表的其余部分（li.drop（n））的反复迭代，并比较所述当前元素具有最低的列表的最大;更换，如果neccessary，并再次求助于。
• 改进：
  • 扔掉诠释，并使用排序。
  • 扔掉（_> _），并使用用户订购，让BottomTen。 （哈德：挑中间的10 :)）
  • 扔掉列表，并使用可迭代，而不是

更新（抽象）：

 高清extremeN [T]（N：智力，李：列表[T]）
  （COMP1：（（T，T）=＆GT;布尔），COMP2：（（T，T）=＆GT;布尔））：
     列表[T] = {

  高清updateSofar（SOFAR：列表[T]报：T）：列表[T] =
    如果（COMP1（EL，sofar.head））
      （EL :: sofar.tail）.sortWith（COMP2（_，_））
    其他SOFAR

  （li.take（N）.sortWith（COMP2（_，_））/：li.drop（N））（updateSofar（_，_））
}

/ *仍然结合诠释：
高清顶部（N：智力，李：列表[INT]）：列表[INT] = {
  extremeN（N，李）（（_＆LT; _）（_＆GT; _））
}
高清底部（N：智力，李：列表[INT]）：列表[INT] = {
  extremeN（N，李）（（_＆GT; _）（_＆LT; _））
}
* /

DEF顶部[T]（N：智力，李：列表[T]）
  （隐ORD：订货[T]）：可迭代[T] = {
  extremeN（N，李）（ord.lt（_，_），ord.gt（_，_））
}
高清底部[T]（N：智力，李：列表[T]）
  （隐ORD：订货[T]）：可迭代[T] = {
  extremeN（N，李）（ord.gt（_，_），ord.lt（_，_））
}

顶（3，LI）
底部（3，LI）
VAL SL =列表（豪斯，花园，引导，Sumpf，X，Y，XKCD，X11）
底部（2，SL）
 

要替换名单与可迭代似乎有点困难。

由于丹尼尔C.索布拉尔指出，在评论中，高 N 的TOPN会导致很多分拣工作，所以它可能是有用的，做手工插入排序，而不是一再的排序前n个元素的整个列表：

 高清extremeN [T]（N：智力，李：列表[T]）
  （COMP1：（（T，T）=＆GT;布尔），COMP2：（（T，T）=＆GT;布尔））：
     列表[T] = {

  高清sortedIns（EL：T，列表：列出[T]）：列表[T] =
    如果（list.isEmpty）名单（EL）其他
    如果（COMP2（EL，list.head））EL ::列表其他
      list.head :: sortedIns（EL，list.tail）

  高清updateSofar（SOFAR：列表[T]报：T）：列表[T] =
    如果（COMP1（EL，sofar.head））
      sortedIns（EL，sofar.tail）
    其他SOFAR

  （li.take（N）.sortWith（COMP2（_，_））/：li.drop（N））（updateSofar（_，_））
}
 

顶部/底部的方法和用途同上。对于小群体的顶部/底部元件，排序是很少调用，几次在开始，然后越来越少经常随着时间的推移。例如，70次，10 000顶部（10），和90次的100 000顶部（10）

Is there a simple and efficient solution to determine the top n elements of a Scala Iterable? I mean something like

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

but without having to sort all elements when only the top 2 are of interest. Ideally I'm looking for something like

iter.top(2, _.myAttr)

see also: Solution for the top element using an Ordering: In Scala, how to use Ordering[T] with List.min or List.max and keep code readable

Update:

Thank you all for your solutions. Finally, I took the original solution of user unknown and adopted it to use Iterable and the pimp-my-library pattern:

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))

解决方案

My solution (bound to Int, but should be easily changed to Ordered (a few minutes please):

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 (_, _)) 
}

usage:

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

• For above list, take the first 2 (4, 3) as starting TopTen (TopTwo).
• Sort them, such that the first element is the bigger one (if any).
• repeatedly iterate through the rest of the list (li.drop(n)), and compare the current element with the maximum of the list of minimums; replace, if neccessary, and resort again.
• Improvements:
  • Throw away Int, and use ordered.
  • Throw away (_ > _) and use a user-Ordering to allow BottomTen. (Harder: pick the middle 10 :) )
  • Throw away List, and use Iterable instead

update (abstraction):

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)

To replace List with Iterable seems to be a bit harder.

As Daniel C. Sobral pointed out in the comments, a high n in topN can lead to much sorting work, so that it could be useful, to do a manual insertion sort instead of repeatedly sorting the whole list of top-n elements:

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 (_, _)) 
}

top/bottom method and usage as above. For small groups of top/bottom Elements, the sorting is rarely called, a few times in the beginning, and then less and less often over time. For example, 70 times with top (10) of 10 000, and 90 times with top (10) of 100 000.

这篇关于最简单的获得斯卡拉可迭代的前n个元素的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！