¿Existe una combinación simple de funciones estándar de orden superior para contar los elementos únicos en una lista?Contando elementos únicos en una lista
Por ejemplo el resultado de
[1, 1, 4, 0, 4, 4]
sería algo así como
[(1,2), (4,3), (0,1)]
Si el orden no es importante esto funciona:
map (\[email protected](x:_) -> (x, length xs)) . group . sort
group . sort le dará una lista de listas donde todos los elementos que son iguales entre sí se agrupan en la misma sublista (sin sor t, solo los elementos iguales consecutivos se agruparían juntos). El map luego convierte cada sublista en un (element, lengthOfSublist) -tuple.
Si desea ordenar el resultado por primera vez, puede usar zip antes de ordenar para agregar un índice a cada elemento, luego, después de la agrupación, ordene de nuevo por ese índice y luego elimine el índice.
El género podría ser muy costoso en listas grandes. Podría ser mejor usar las soluciones de KennyTM o sdcwc para un desempeño más rápido. – GeneralBecos
@GeneralBecos ¿Por qué la clasificación sería más lenta que la creación de un mapa? Ambos son 'O (n log n)'. – sepp2k
Porque suponiendo que está haciendo una distribución de frecuencia, la cantidad de elementos solo en el peor de los casos será la misma que la cantidad de elementos en la lista. En el escenario más común, la cantidad de elementos en la distribución será mucho menor. Por lo tanto, en promedio, el mapa superará al género. – GeneralBecos
Lo más simple sería ordenar los elementos en orden, usar "grupo" para colocarlos en sublistas de elementos iguales, y luego contar los elementos en cada sub-lista.
map (\xs -> (head xs, length xs)) . group . sort
Por cierto, puede escribir '\ xs -> (xs cabeza, longitud xs)' como 'cabeza &&& length', utilizando el módulo Control.Arrow – sdcvvc
Si la lista contiene sólo números enteros, también se puede utilizar
import qualified Data.IntMap as I
countElems1 :: [Int] -> [(Int, Int)]
countElems1 = I.toList . foldr (\k -> I.insertWith (+) k 1) I.empty
(Recuerde que debe compilar con optimización sin embargo, de lo contrario esto será 2x más lento que el método group . sort. Con -O2 es ligeramente más rápido en un 14%.)
también es posible usar uno de los multisetpackages que hace la función tan simple como
import qualified Math.Combinatorics.Multiset as S
countElems4 = S.toCounts . S.fromList
pero es menos eficiente.
Todas las soluciones anteriores ignoran el orden original.
Y eso sin las recientes mejoras de velocidad en la biblioteca de contenedores, apostaría. –
Lo que estás hablando es solo run length encoding en los datos ordenados: el libro en línea gratuito Real World Haskell tiene un great example of this. Deberá ordenar la lista antes de pasarla por el runLengthEncoder.
Es * no * RLE. RLE dará '[(1,2), (4,1), (0,1), (4,2)] '. – kennytm
@KennyTM Tenga en cuenta que dije 'en datos ordenados'. Así que no es del todo RLE, pero casi con la entrada ordenada, creo que es, ¿no? –
Uso Data.Map y tupla secciones:
count = Map.fromListWith (+) . map (, 1)
(Añadir Map.toList si necesita una lista.)
Es importante pedido? Si es así, ¿cuál es el orden? Orden de la primera aparición? – sepp2k