Scala Group¿Para conservar el orden de inserción?

Question

El método groupBy en Listas, Mapas, etc., genera un Mapa después de la función.

¿Hay alguna manera de usar el grupo Por generar un Mapa que preserve el orden de inserción (LinkedHashMap, por ejemplo)?

Estoy usando bucles para insertar manualmente, pero quería saber si una de las funciones útiles ya definidas podría ayudarme.

Gracias de antemano.

Answer 1

groupBy como se define en TraversableLike produce un immutable.Map, por lo que no puede hacer que este método produzca algo más.

El orden de los elementos en cada entrada ya está conservado, pero no el orden de las teclas. Las teclas son el resultado de la función suministrada, por lo que realmente no tienen un pedido.

Si desea hacer un pedido basado en la primera aparición de una clave en particular, aquí hay un boceto de cómo podría hacerlo. Decimos que queremos enteros grupo por su valor/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 

Answer 2

La siguiente le daría un método groupByOrdered que se comporta como usted buscó.

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

Cuando utilizo este código como:

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

me sale el siguiente resultado:

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

Answer 3

Aquí hay uno sin mapas:

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

Podría ser útil si solo necesita acceder a los resultados secuencialmente (no hay acceso aleatorio) y desea evitar la sobrecarga de crear y usar objetos Map. Nota: No comparé el rendimiento con las otras opciones, en realidad podría ser peor.

EDITAR: Solo para ser claro; esto supone que su entrada ya está ordenada por la clave del grupo. Mi caso de uso es un SELECT ... ORDER BY.

Answer 4

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)