복붙노트

[SCALA] 스칼라의 Iterable의 상위 N 요소를 얻을 수있는 간단한 방법

SCALA

스칼라의 Iterable의 상위 N 요소를 얻을 수있는 간단한 방법

스칼라의 Iterable의 상위 N 요소를 결정하는 간단하고 효율적인 솔루션이 있습니까? 내가 좋아하는 뭔가를 의미

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

그러나 상위 2가 관심이있는 경우에만 모든 요소를 ​​정렬 할 필요없이. 이상적으로 내가 좋아하는 뭔가를 찾고 있어요

iter.top(2, _.myAttr)

또한 참조 : 상위 요소에 대한 솔루션을 순서화를 사용 : 스칼라에서 어떻게 List.min 또는 List.max으로 주문 [T]를 사용하고 읽을 수있는 코드를 유지하기 위해

솔루션에 대한 여러분 모두 감사합니다. 마지막으로, 나는 알 수없는 사용자의 원래 솔루션을 가져다의 Iterable을 사용하도록 채택 포주 - 내 라이브러리 패턴 :

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

해결법

  1. ==============================

    1.내 솔루션은 () int로 결합하지만, 쉽게하십시오 순서가 (몇 분으로 변경해야합니다 :

    내 솔루션은 () int로 결합하지만, 쉽게하십시오 순서가 (몇 분으로 변경해야합니다 :

    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)

    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로 목록을 대체하는 것은 조금 어려울 것 같다.

    다니엘 C. 소브랄이 코멘트에 지적한 바와 같이,을 TopN에서 높은 N은 도움이 될 수 있도록, 수동 삽입을 일종의 대신 반복적으로 상위 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, 000 및 100의 상부 (10)와 함께 90 시간.

  2. ==============================

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

    고유 한 값을 가지고 목록을 강제로 설정을 사용 :

    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
      }
    }
  3. ==============================

    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 로그 N), K <= N이다. 그래서 성능이 작은 k에 대한 최악의 N 로그 N에서 선형이다.

    이 솔루션은 성능 (N K 로그) 메모리하지만 O에 대한 O (k)를 최적화 할 수있다. 아이디어는 항상 상단에만 K 항목을 추적 할 MinHeap을 사용하는 것입니다. 여기에 솔루션입니다.

    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
}
  4. ==============================

    4.당신은 최고 N 요소를 결정하기 위해 전체 컬렉션을 정렬 할 필요가 없습니다. 그러나,이 기능은 원시 라이브러리가 제공되는 것을 믿지 않는다, 그래서 당신은 당신이 가능하게 포주 - 내 - 라이브러리 패턴을 사용하여, 자신의 롤해야합니다.

    당신은 최고 N 요소를 결정하기 위해 전체 컬렉션을 정렬 할 필요가 없습니다. 그러나,이 기능은 원시 라이브러리가 제공되는 것을 믿지 않는다, 그래서 당신은 당신이 가능하게 포주 - 내 - 라이브러리 패턴을 사용하여, 자신의 롤해야합니다.

    예를 들어, 다음과 같이 모음의 n 번째 요소를 얻을 수 있습니다 :

      class Pimp[A, Repr <% TraversableLike[A, Repr]](self : Repr) {

    def nth(n : Int)(implicit ord : Ordering[A]) : A = {
      val trav : TraversableLike[A, Repr] = self
      var ltp : List[A] = Nil
      var etp : List[A] = Nil
      var mtp : List[A] = Nil
      trav.headOption match {
        case None      => error("Cannot get " + n + " element of empty collection")
        case Some(piv) =>
          trav.foreach { a =>
            val cf = ord.compare(piv, a)
            if (cf == 0) etp ::= a
            else if (cf > 0) ltp ::= a
            else mtp ::= a
          }
          if (n < ltp.length)
            new Pimp[A, List[A]](ltp.reverse).nth(n)(ord)
          else if (n < (ltp.length + etp.length))
            piv
          else
            new Pimp[A, List[A]](mtp.reverse).nth(n - ltp.length - etp.length)(ord)
      }
    }
  }

    (이것은 매우 작동하지 않습니다, 죄송합니다)

    그것은 상위 n 개의 요소를 얻기 위해 다음 사소한 :

    def topN(n : Int)(implicit ord : Ordering[A], bf : CanBuildFrom[Repr, A, Repr]) ={
  val b = bf()
  val elem = new Pimp[A, Repr](self).nth(n)(ord)
  import util.control.Breaks._
  breakable {
    var soFar = 0
    self.foreach { tt =>
      if (ord.compare(tt, elem) < 0) {
         b += tt
         soFar += 1
      }
    }
    assert (soFar <= n)
    if (soFar < n) {
      self.foreach { tt =>
        if (ord.compare(tt, elem) == 0) {
          b += tt
          soFar += 1
        }
        if (soFar == n) break
      }
    }

  }
  b.result()
}

    불행하게도 나는 문제가이 포주를 얻는 데이 암시를 통해 발견 할 :

    implicit def t2n[A, Repr <% TraversableLike[A, Repr]](t : Repr) : Pimp[A, Repr] 
  = new Pimp[A, Repr](t)

    나는이 얻을 :

    scala> List(4, 3, 6, 7, 1, 2, 8, 5).topN(4)
<console>:9: error: could not find implicit value for evidence parameter of type (List[Int]) => scala.collection.TraversableLike[A,List[Int]]
   List(4, 3, 6, 7, 1, 2, 8, 5).topN(4)
       ^

    그러나 코드는 실제로 작동 확인 :

    scala> new Pimp(List(4, 3, 6, 7, 1, 2, 8, 5)).topN(4)
res3: List[Int] = List(3, 1, 2, 4)

    과

    scala> new Pimp("ioanusdhpisjdmpsdsvfgewqw").topN(6)
res2: java.lang.String = adddfe
  5. ==============================

    5.목표는 전체 목록을 정렬하지 않는 것입니다 경우에 당신이 뭔가를 (물론 수는 분명이 안 될 때 우리는 목록을 변경하지 않도록이 조금을 최적화 할 수있다) 할 수있는 :

    목표는 전체 목록을 정렬하지 않는 것입니다 경우에 당신이 뭔가를 (물론 수는 분명이 안 될 때 우리는 목록을 변경하지 않도록이 조금을 최적화 할 수있다) 할 수있는 :

    List(1,6,3,7,3,2).foldLeft(List[Int]()){(l, n) => (n :: l).sorted.take(2)}
  6. ==============================

    6.나는 (비록 자바) 아파치 잭 래빗의 순위 클래스에서 최근 이러한 순위 알고리즘을 구현했습니다. 그것의 요점을위한 테이크 방법을 참조하십시오. 기본적인 아이디어는 퀵하지만 상위 N 요소가 발견되는 즉시 조기에 종료하는 것입니다.

    나는 (비록 자바) 아파치 잭 래빗의 순위 클래스에서 최근 이러한 순위 알고리즘을 구현했습니다. 그것의 요점을위한 테이크 방법을 참조하십시오. 기본적인 아이디어는 퀵하지만 상위 N 요소가 발견되는 즉시 조기에 종료하는 것입니다.

  7. ==============================

    7.여기서 점근 O (n)의 용액이다.

    여기서 점근 O (n)의 용액이다.

    def top[T](data: List[T], n: Int)(implicit ord: Ordering[T]): List[T] = {
    require( n < data.size)

    def partition_inner(shuffledData: List[T], pivot: T): List[T] = 
      shuffledData.partition( e => ord.compare(e, pivot) > 0 ) match {
          case (left, right) if left.size == n => left
          case (left, x :: rest) if left.size < n => 
            partition_inner(util.Random.shuffle(data), x)
          case (left @ y :: rest, right) if left.size > n => 
            partition_inner(util.Random.shuffle(data), y)
      }

     val shuffled = util.Random.shuffle(data)
     partition_inner(shuffled, shuffled.head)
}

scala> top(List.range(1,10000000), 5)

    때문에 재귀로,이 솔루션은 위의 몇 가지 비선형 솔루션보다 오래 걸릴 것이며, java.lang.OutOfMemoryError와가 발생할 수 있습니다 GC 오버 헤드 제한을 초과했습니다. 약간 더 읽을 이럴 및 기능적인 스타일하지만. 그냥 면접에 대한).

    무엇이이 솔루션은 쉽게 병렬화 될 수 있다는 더 중요하다.

    def top[T](data: List[T], n: Int)(implicit ord: Ordering[T]): List[T] = {
    require( n < data.size)

    @tailrec
    def partition_inner(shuffledData: List[T], pivot: T): List[T] = 
      shuffledData.par.partition( e => ord.compare(e, pivot) > 0 ) match {
          case (left, right) if left.size == n => left.toList
          case (left, right) if left.size < n => 
            partition_inner(util.Random.shuffle(data), right.head)
          case (left, right) if left.size > n => 
            partition_inner(util.Random.shuffle(data), left.head)
      }

     val shuffled = util.Random.shuffle(data)
     partition_inner(shuffled, shuffled.head)
}
  8. ==============================

    8.상위 n 개의 요소를 받고 N의 작은 값과 큰 목록의 경우, 최대 요소 n 번을 선택하여 구현 될 수있다 :

    상위 n 개의 요소를 받고 N의 작은 값과 큰 목록의 경우, 최대 요소 n 번을 선택하여 구현 될 수있다 :

    def top[T](n:Int, iter:Iterable[T])(implicit ord: Ordering[T]): Iterable[T] = {
  def partitionMax(acc: Iterable[T], it: Iterable[T]): Iterable[T]  = {
    val max = it.max(ord)
    val (nextElems, rest) = it.partition(ord.gteq(_, max))
    val maxElems = acc ++ nextElems
    if (maxElems.size >= n || rest.isEmpty) maxElems.take(n)
    else partitionMax(maxElems, rest)
  }
  if (iter.isEmpty) iter.take(0)
  else partitionMax(iter.take(0), iter)
}

    이것은 전체 목록을 정렬하고 주문을 소요하지 않습니다. 나는 partitionMax에 전화를 모든 방법은 O (목록 크기)이라고 생각하고 나는 단지 작은 N에 대한 전반적인 효율이 반복자의 크기에 비례한다, 그래서 대부분의 그것을 n 번 전화를 기대합니다.

    scala> top(5, List.range(1,1000000))
res13: Iterable[Int] = List(999999, 999998, 999997, 999996, 999995)

scala> top(5, List.range(1,1000000))(Ordering[Int].on(- _))
res14: Iterable[Int] = List(1, 2, 3, 4, 5)

    당신은 또한 (_. myAttr) n은 반복 가능한 크기에 근접하는 경우에 지점을 추가하고 iter.toList.sortBy로 전환 할 수 .take (N)를.

    이 콜렉션의 유형이 제공 반환하지 않습니다,하지만 난이 풍부하게 - 내 라이브러리 스칼라 컬렉션에 패턴을 적용하려면 어떻게에서 당신이 볼 수? 경우이 요구 사항입니다.

  9. ==============================

    9.시간 복잡도 O (nlogk)와 PriorityQueue 인을 사용하는 최적의 솔루션. 업데이트에 주어진 방법, 당신은이 PriorityQueue 인을 사용하여 최적화 아래에 필요한되지 않고마다 SOFAR 목록을 정렬된다.

    시간 복잡도 O (nlogk)와 PriorityQueue 인을 사용하는 최적의 솔루션. 업데이트에 주어진 방법, 당신은이 PriorityQueue 인을 사용하여 최적화 아래에 필요한되지 않고마다 SOFAR 목록을 정렬된다.

    import scala.language.implicitConversions
import scala.language.reflectiveCalls
import collection.mutable.PriorityQueue
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: PriorityQueue[A], el: A): PriorityQueue[A] = {
            if (ord.compare(f(el), f(sofar.head)) < 0){
                sofar.dequeue
                sofar.enqueue(el)
            }
            sofar
        }

        val (sofar, rest) = iter.splitAt(n)
        (PriorityQueue(sofar.toSeq:_*)( Ordering.by( (x :A) => f(x) ) ) /: rest) (updateSofar (_, _)).dequeueAll.toList.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))

    10. from https://stackoverflow.com/questions/5674741/simplest-way-to-get-the-top-n-elements-of-a-scala-iterable by cc-by-sa and MIT license

'SCALA' 카테고리의 다른 글

[SCALA] 어떤 종류의 스칼라에서 메모리 가변 데이터 테이블을 저장하기 위해 사용하는 방법?  (0) 2019.11.05
[SCALA] 대신 필터 withFilter  (0) 2019.11.05
[SCALA] 구문 설탕 : _ * 방법 매개 변수로 서열을 치료  (0) 2019.11.05
[SCALA] 고정 용량 및 사용자 정의 비교 사용해, PriorityQueue 구현이 있습니까?  (0) 2019.11.05
[SCALA] 어떻게 GROUPBY 후 수집에 값을 집계하는?  (0) 2019.11.05
,

티스토리툴바