Scala Group, сохраняя порядок ввода? - PullRequest
Новая
       36

Scala Group, сохраняя порядок ввода?

27 голосов
/ 07 марта 2012

Метод groupBy в списках, картах и ​​т. Д. Создает функцию после функции.

Есть ли способ использовать groupBy для создания карты, которая сохраняет порядок вставки (например, LinkedHashMap)?

Я использую циклы для вставки вручную, но я хотел знать, может ли мне помочь одна из полезных уже определенных функций.

Заранее спасибо.

Ответы [ 4 ]

21 голосов
/ 07 марта 2012

groupBy, как определено в TraversableLike, создает immutable.Map, поэтому вы не можете заставить этот метод производить что-то еще.

Порядок элементов в каждой записи уже сохранен, но не порядок ключей. Клавиши являются результатом поставленной функции, поэтому у них нет порядка.

Если вы хотите сделать заказ на основе первого вхождения определенного ключа, вот набросок того, как вы можете это сделать. Скажем, мы хотим сгруппировать целые числа по их значению / 2: 

val m = List(4, 0, 5, 1, 2, 6, 3).zipWithIndex groupBy (_._1 / 2)
val lhm = LinkedHashMap(m.toSeq sortBy (_._2.head._2): _*)
lhm mapValues (_ map (_._1))
// Map(2 -> List(4, 5), 0 -> List(0, 1), 1 -> List(2, 3), 3 -> List(6))
// Note order of keys is same as first occurrence in original list
19 голосов
/ 08 марта 2012

Следующий метод даст вам groupByOrdered метод, который ведет себя так, как вы искали. 

import collection.mutable.{LinkedHashMap, LinkedHashSet, Map => MutableMap}

object GroupByOrderedImplicit {
  implicit class GroupByOrderedImplicitImpl[A](val t: Traversable[A]) extends AnyVal {
    def groupByOrdered[K](f: A => K): MutableMap[K, LinkedHashSet[A]] = {
      val map = LinkedHashMap[K,LinkedHashSet[A]]().withDefault(_ => LinkedHashSet[A]())
      for (i <- t) {
        val key = f(i)
        map(key) = map(key) + i
      }
      map
    }
  }
}

Когда я использую этот код как: 

import GroupByOrderedImplicit._
0.to(100).groupByOrdered(_ % 10).foreach(println)

Я получаю следующий вывод: 

(0,Set(0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100))
(1,Set(1, 11, 21, 31, 41, 51, 61, 71, 81, 91))
(2,Set(2, 12, 22, 32, 42, 52, 62, 72, 82, 92))
(3,Set(3, 13, 23, 33, 43, 53, 63, 73, 83, 93))
(4,Set(4, 14, 24, 34, 44, 54, 64, 74, 84, 94))
(5,Set(5, 15, 25, 35, 45, 55, 65, 75, 85, 95))
(6,Set(6, 16, 26, 36, 46, 56, 66, 76, 86, 96))
(7,Set(7, 17, 27, 37, 47, 57, 67, 77, 87, 97))
(8,Set(8, 18, 28, 38, 48, 58, 68, 78, 88, 98))
(9,Set(9, 19, 29, 39, 49, 59, 69, 79, 89, 99))
5 голосов
/ 26 марта 2015

Вот один без карт: 

def orderedGroupBy[T, P](seq: Traversable[T])(f: T => P): Seq[(P, Traversable[T])] = {
   @tailrec
   def accumulator(seq: Traversable[T], f: T => P, res: List[(P, Traversable[T])]): Seq[(P, Traversable[T])] = seq.headOption match {
     case None => res.reverse
     case Some(h) => {
       val key = f(h)
       val subseq = seq.takeWhile(f(_) == key)
       accumulator(seq.drop(subseq.size), f, (key -> subseq) :: res)
     }
   }
   accumulator(seq, f, Nil)
 }

Это может быть полезно, если вам нужен только последовательный доступ к результатам (без произвольного доступа) и вы хотите избежать накладных расходов на создание и использование объектов Map.Примечание: я не сравнивал производительность с другими вариантами, на самом деле это могло быть хуже.

РЕДАКТИРОВАТЬ: Просто чтобы быть ясно;это предполагает, что ваш ввод уже упорядочен групповым ключом.Мой вариант использования SELECT ... ORDER BY.

0 голосов
/ 20 августа 2017 
    This yields better results on ScalaMeter though the solution is very similar to the actual scala groupBy
    ::Benchmark Range.GroupBy::
    cores: 8
    hostname: xxxxx-MacBook-Pro.local
    name: Java HotSpot(TM) 64-Bit Server VM
    osArch: x86_64
    osName: Mac OS X
    vendor: Oracle Corporation
    version: 25.131-b11
    Parameters(size -> 300000): 6.500884
    Parameters(size -> 600000): 13.019679
    Parameters(size -> 900000): 22.756615
    Parameters(size -> 1200000): 25.481007
    Parameters(size -> 1500000): 33.129888
    compared to the one that zipWithIndex approach which yields
    :Benchmark Range.GroupBy::
    cores: 8
    hostname: xxxxx-MacBook-Pro.local
    name: Java HotSpot(TM) 64-Bit Server VM
    osArch: x86_64
    osName: Mac OS X
    vendor: Oracle Corporation
    version: 25.131-b11
    Parameters(size -> 300000): 9.57414
    Parameters(size -> 600000): 18.569085
    Parameters(size -> 900000): 28.233822
    Parameters(size -> 1200000): 36.975254
    Parameters(size -> 1500000): 47.447057
    implicit class GroupBy[A](val t: TraversableOnce[A]) {
 def sortedGroupBy[K](f: A => K)(implicit ordering: Ordering[K]): immutable.SortedMap[K, ArrayBuffer[A]] = {
 val m = mutable.SortedMap.empty[K, ArrayBuffer[A]]
 for (elem <- t) {
 val key = f(elem)
 val bldr = m.getOrElseUpdate(key, mutable.ArrayBuffer[A]())
 bldr += elem
 }
 val b = immutable.SortedMap.newBuilder[K, ArrayBuffer[A]]
 for ((k, v) <- m) {
 b += ((k, v.result))
 }
 b.result
 }
 }
 example: val sizes = Gen.range("size")(300000, 1500000, 300000) and 
 groupByOrdered(_ % 10)
...