Есть ли прямая комбинация стандартных функций более высокого порядка для подсчета уникальных элементов в списке?Подсчет уникальных элементов в списке
Например результат для
[1, 1, 4, 0, 4, 4]
будет что-то вроде
[(1,2), (4,3), (0,1)]
Если порядок не важен это работает:
map (\[email protected](x:_) -> (x, length xs)) . group . sort
group . sort даст вам список списков где все элементы, которые равны друг другу, сгруппированы в один и тот же подсписк (без sor t, только последовательные равные элементы будут сгруппированы вместе). Затем map превращает каждый подсвечник в набор (element, lengthOfSublist).
Если вы хотите заказать результат по первому вхождению, вы можете использовать zip перед сортировкой, чтобы добавить индекс к каждому элементу, а затем, после группировки, снова отсортировать этот индекс, а затем удалить индекс.
Сортировка может быть очень дорогой в больших списках. Возможно, лучше использовать решения KennyTM или sdcwc для повышения производительности. – GeneralBecos
@GeneralBecos Почему сортировка будет медленнее, чем создание карты? Оба являются «O (n log n)». – sepp2k
Поскольку предполагается, что вы выполняете частотное распределение, количество элементов только в худшем случае будет таким же, как и количество элементов в списке. В более распространенном сценарии количество элементов в распределении будет намного меньше. Поэтому в среднем карта будет превосходить сортировку. – GeneralBecos
Простейшей задачей было бы отсортировать элементы в порядке, использовать «группу», чтобы поместить их в под-списки равных элементов, а затем подсчитать элементы в каждом под-списке.
map (\xs -> (head xs, length xs)) . group . sort
Кстати, вы можете написать '\ xs -> (head xs, length xs)' as 'head &&& length', используя модуль Control.Arrow. – sdcvvc
Если список содержит только целые числа, вы можете также использовать
import qualified Data.IntMap as I
countElems1 :: [Int] -> [(Int, Int)]
countElems1 = I.toList . foldr (\k -> I.insertWith (+) k 1) I.empty
(Не забудьте компилировать с оптимизацией, хотя, в противном случае это будет 2x медленнее, чем метод group . sort. С -O2 это немного быстрее на 14%.)
Вы также можете использовать один из multisetpackages, что делает функцию так просто, как
import qualified Math.Combinatorics.Multiset as S
countElems4 = S.toCounts . S.fromList
но менее эффективный.
Все вышеуказанные решения игнорируют первоначальный заказ.
И это без недавних улучшений скорости в библиотеке контейнеров, я готов поспорить. –
Что вы говорите, это просто run length encoding на отсортированных данных: в бесплатной онлайн-книге Real World Haskell есть great example of this. Вы захотите отсортировать список, прежде чем вводить его через runLengthEncoder.
Это * не * RLE. RLE даст '[(1,2), (4,1), (0,1), (4,2)] '. – kennytm
@KennyTM Обратите внимание, что я сказал« на отсортированные данные ». Таким образом, не совсем RLE, но почти с отсортированным входом, я думаю, это так, не так ли? –
Использование Data.Map и кортежей разделы:
count = Map.fromListWith (+) . map (, 1)
(Добавить Map.toList если вам нужен список.)
ли заказ важен? Если да, то какой порядок? Порядок первого появления? – sepp2k