Элегантный способ подсчета предметов
У меня есть список в форме, как это:
'(("Alpha" . 1538)
("Beta" . 8036)
("Gamma" . 8990)
("Beta" . 10052)
("Alpha" . 12837)
("Beta" . 13634)
("Beta" . 14977)
("Beta" . 15719)
("Alpha" . 17075)
("Rho" . 18949)
("Gamma" . 21118)
("Gamma" . 26923)
("Alpha" . 31609))
Как можно подсчитать общее количество вхождений терминов в машину каждого элемента в списке? В основном я хочу:
(("Alpha" . 4)
("Beta" . 5)
("Gamma" . 3)
("Rho" . 1))
Нет, это не домашняя работа. У меня просто пока нет мысли о мышлении на Лиспе.
В C# я бы использовал LINQ для этого. Я могу сделать это и в lisp, используя циклы while и тому подобное, но способ, которым я думаю об этом, кажется слишком сложным.
РЕДАКТИРОВАТЬ
Вот что у меня есть:
(defun count-uniq (list)
"Returns an alist, each item is a cons cell where the car is
a unique element of LIST, and the cdr is the number of occurrences of that
unique element in the list. "
(flet ((helper (list new)
(if (null list)
new
(let ((elt (assoc (car list) new)))
(helper (cdr list)
(if elt
(progn (incf (cdr elt)) new)
(cons (cons (car list) 1) new)))))))
(nreverse (helper list nil))))
10 ответов
Я не знаю, что это самое элегантное, но кажется разумным
(defun add-for-cheeso (data)
(let (result)
(dolist (elt data result)
(let ((sofar (assoc (car elt) result)))
(if sofar
(setcdr sofar (1+ (cdr sofar)))
(push (cons (car elt) 1) result))))))
(defun freqs (list &optional test key)
(let ((h (make-hash-table :test test)))
(dolist (x list)
(let ((key (if key (funcall key x) x)))
(puthash key (1+ (gethash key h 0)) h)))
(let ((r nil))
(maphash #'(lambda (k v) (push (cons k v) r)) h)
(sort r #'(lambda (x y) (< (cdr x) (cdr y)))))))
(freqs '(("Alpha" . 1538)
("Beta" . 8036)
("Gamma" . 8990)
("Beta" . 10052)
("Alpha" . 12837)
("Beta" . 13634)
("Beta" . 14977)
("Beta" . 15719)
("Alpha" . 17075)
("Rho" . 18949)
("Gamma" . 21118)
("Gamma" . 26923)
("Alpha" . 31609))
#'equal #'car)
Объединение функций Common Lisp более высокого уровня:
(defun count-unique (alist)
(mapcar
(lambda (item)
(cons (car item)
(count (car item) alist :test #'equal :key #'car)))
(remove-duplicates alist :test #'equal :key #'car)))
Это не масштабируется до больших списков, хотя. Если вам нужна производительность O(n), используйте вместо этого решение на основе хеш-таблицы, такое как менее элегантное:
(defun count-unique (alist)
(loop
with hash = (make-hash-table :test #'equal)
for (key . nil) in alist
do (incf (gethash key hash 0))
finally (return
(loop for key being each hash-key of hash
using (hash-value value)
collect (cons key value)))))
Каждый раз, когда вы хотите просмотреть список и впоследствии вернуть какое-то значение, будь то новый список или какой-либо совокупный результат, вы думаете о сгибе, также называемом "уменьшить" в Python и Lisps. Fold - отличная абстракция, так как она позволяет писать общий код, применимый для многих вариантов использования, просто настраивая некоторые элементы. Что сходно между поиском суммы из нескольких чисел, поиском товара, поиском минимального целого числа? Все они складываются, потому что вы пробегаетесь по списку, а затем возвращаете некоторый результат на основе его содержимого. В Emacs Lisp они выглядят так:
(reduce '+ '(1 2 3 4 5)) ; 15
(reduce '* '(1 2 3 4 5)) ; 120
(reduce 'min '(1 2 3 4 5)) ; 1
Но складки еще более общие, чем это. Что схоже между поиском суммы, подсчетом числа четных чисел в списке, удалением каждого нечетного числа и построением списка с каждым числом, увеличенным на 5? Каждая такая функция может быть реализована путем принятия некоторого базового значения, последовательно преобразовывая его, пока вы не получите результат. Вы берете это базовое значение, метафорический шарик глины, называете его "аккумулятор", затем берете один элемент из списка и, основываясь на этом элементе, делаете что-то с этим шариком глины, делая его черновиком великолепной скульптуры. Затем вы берете следующий элемент из списка и делаете что-то новое для вашей скульптуры. Вы повторяете это до тех пор, пока список не станет пустым, и вы не получите шедевр. Как будто каждый элемент списка представляет собой отдельную инструкцию в большом рецепте. Просто имейте в виду, что вы абсолютно свободны делать что-либо с глиной, вам не нужно напрямую использовать элементы списка в результате - технически это означает, что аккумулятор (и, следовательно, результат) может иметь другой тип.
(reduce '+ '(1 2 3 4 5) :initial-value 0) ; 15
(reduce (lambda (acc x) (if (evenp x) (1+ acc) acc)) '(1 2 3 4 5) :initial-value 0) ; 2
(reduce (lambda (x acc) (if (oddp x) acc (cons x acc))) '(1 2 3 4 5) :initial-value '() :from-end t) ; (2 4)
(reduce (lambda (x acc) (cons (+ x 5) acc)) '(1 2 3 4 5) :initial-value '() :from-end t) ; (6 7 8 9 10)
Примечание по сокращению от конца: списки в Лиспе не являются интеллектуальными массивами, как в Python или Java, они являются связанными списками, поэтому доступ к элементу в списке или его изменение где-либо в списке является операцией O(n), в то время как "обращаясь" к началу список O(1). Другими словами, добавление элемента в конец списка является дорогостоящим, поэтому Лисперс обычно добавляет элементы в начало списка, а затем, наконец, обращает список, который называется push / nreverse idiom. Если бы мы делали обычное уменьшение в последних 2 функциях, мы бы взяли 1 к аккумулятору и получили (1), затем 2 к аккумулятору и получили (2 1), пока мы не получим правильный результат, но в обратном порядке. Мы могли бы использовать
reverseфункция после этого, но, к счастью, Emacs'sreduceопоры:from-endключевое слово аргумент, так что оно составляет 5, затем 4, затем 3 и так далее.
Теперь ясно, что ваша операция - это фолд, обход исходного списка и подсчет вхождений каждой клавиши. Прежде чем писать наш фолд, давайте сначала поговорим об алистах. Alist в Lisp - хэш-таблица для бедняков. Вы обычно не возитесь с деталями реализации хэш-таблицы языка программирования? Вы работаете с API. В Python этот API выглядит как синтаксис квадратной скобки (d['a'] = 1) и диктовые методы (d.keys()). Для Alists API содержит функциюassoc, который возвращает элемент при условии ключа.
(assoc 'a '((a . 1) (b . 2))) ; (a . 1)
Почему я говорю о деталях реализации? Потому что вы работаете черезassoc и вам все равно, как именно выглядит этот список, вы абстрагируете это. Другая часть API заключается в том, что если вы хотите добавить новый элемент или изменить существующий, вы просто добавляете пунктирную пару к списку. Это то, как вы должны работать со списками, независимо от их внутренней структуры. Почему это работает? Например, если я хочу изменить значение для ключа a до 10, я бы просто запустить (cons '(a . 10) my-alist), а также my-alist будет в конечном итоге'((a . 10) (a . 1) (b . 2)), Но это не проблема, потому чтоassocвозвращает только первую пару с точками и игнорирует остальные, поэтому вы можете рассматривать alist, как и любую другую структуру данных ключ-значение. Имея это в виду, давайте напишем наш первый серьезный фолд.
(reduce (lambda (acc x)
(let* ((key (car x))
(pair (assoc key acc))
(count (cdr pair)))
(if pair
(cons (cons key (1+ count)) acc)
(cons (cons key 1) acc))))
my-alist
:initial-value '())
Что здесь происходит? Мы берем ваши данные и пустой список, который вскоре станет нашим желаемым результатом. На каждом шаге мы берем пару из данных и спрашиваем: содержит ли наш результат информацию об этой паре? Если нет, то мы добавляем его к результату и ставим 1 - мы встретили этот ключ впервые. Однако, если мы находим информацию об этой паре в нашем результате, то мы должны снова добавить ее к нашему результату, но на этот раз с числом, увеличенным на 1. Повторите эту процедуру для каждого элемента в ваших данных, и вы получите:
(("Alpha" . 4) ("Gamma" . 3) ("Gamma" . 2) ("Rho" . 1) ("Alpha" . 3)
("Beta" . 5) ("Beta" . 4) ("Beta" . 3) ("Alpha" . 2) ("Beta" . 2)
("Gamma" . 1) ("Beta" . 1) ("Alpha" . 1))
Помни что assocзаботится только о первом появлении ключа? Этот список будет вести себя так же, как если бы он был просто (("Alpha" . 4) ("Gamma" . 3) ("Rho" . 1) ("Beta" . 5)) так что нам здесь хорошо. Тем не менее, можем ли мы изменить наш фолд, чтобы получить последний, более короткий результат? Подожди, зачем нам слишком усложнять наш фолд, если бы мы могли потом подправить результат? В конце концов, что такое компьютерное программирование, если не серия преобразований данных? Нет причины, по которой вы не могли бы просто удалить все "устаревшие" пары из своего списка, просто используйтеcl-remove-duplicates с правильными аргументами, и все готово.
Таким образом, мы гордимся собой, мы написали сгиб, столп функционального программирования, но тщательное изучение выявляет неэффективность: мы пересекаем аккумулятор сassocнайти пару и ее значение для приращения.assocвзять на себя),reduceсам по себе принимает O(n), поэтому наш алгоритм O(n²) (читайте о порядке роста, если вы не понимаете обозначения Big-O). Понятно, что вместо этого нам лучше работать с надлежащей оптимизированной хэш-таблицей и преобразовывать ее в alist, когда нам это нужно. Перепишите наш сгиб:
(reduce (lambda (acc x)
(cl-incf (gethash (car x) acc 0))
acc)
my-alist
:initial-value (make-hash-table :test 'equal))
(gethash k d 0)эквивалентно питонуd.get('k', 0)где последний аргумент по умолчанию.cl-incf (Common Lisp эквивалент incf) - это умный макрос, который увеличивает свой аргумент на месте (читайте о setf понимать умные задания). make-hash-table требует специальной тестовой функции, потому что строки нельзя сравнивать со стандартными eqlфункция. Чтобы получить список, просто конвертируйте хэш-таблицу результатов нашего сгиба с помощьюht->alistфункция, которую мы либо берем от Уилфредаht.el библиотека, или напишите сами:
(defun ht->alist (table)
(let (alist)
(maphash (lambda (k v)
(push (cons k v) alist))
table)
alist))
Использование расширений Common Lisp:
(require 'cl)
(loop with result = nil
for (key . dummy) in original-list
do (incf (cdr (or (assoc key result)
(first (push (cons key 0) result)))))
finally return (sort result
(lambda (a b) (string< (car a) (car b)))))
Вы можете просто сказать finally return result если вы не заботитесь о сортировке конечного результата.
(require 'cl)
(defun count-uniq (list)
(let ((k 1) (list (sort (mapcar #'car list) #'string<)))
(loop for (i . j) on list
when (string= i (car j)) do (incf k)
else collect (cons i k) and do (setf k 1))))
Использование функций высокого порядка сортировки и уменьшения.
Сначала сортировка (с использованием строки<), затем уменьшение (подсчет последовательной строки = значения в ячейках cons):
(reduce (lambda (r e)
(if (and r (string= (caar r) e))
(cons
(cons (caar r) (1+ (cdar r)))
(cdr r))
(cons (cons e 1) r)))
(sort (mapcar 'car alist) 'string<)
:initial-value nil)
Это довольно просто и очень просто, используя библиотеку dash:
(require 'dash)
(defun frequencies (values)
"Return an alist indicating the frequency of values in VALUES list."
(mapcar (-lambda ((value . items))
(cons value (length items)))
(-group-by #'identity
values)))
(frequencies (mapcar #'car my-list))
Вот то, что я считаю элегантным функциональным решением, использующим альтернативные функции Emacs, что дает возможность многократного использования frequencies функция, аналогичная ответу Элая:
(defun frequencies (vals)
(reduce
(lambda (freqs key)
(cons (cons key (+ 1 (or (cdr (assoc key freqs)) 0)))
(assq-delete-all-with-test key freqs 'equal)))
vals
:initial-value nil)))
(frequencies (mapcar 'car
'(("Alpha" . 1538)
("Beta" . 8036)
("Gamma" . 8990)
("Beta" . 10052)
("Alpha" . 12837)
("Beta" . 13634)
("Beta" . 14977)
("Beta" . 15719)
("Alpha" . 17075)
("Rho" . 18949)
("Gamma" . 21118)
("Gamma" . 26923)
("Alpha" . 31609))))
=> (("Alpha" . 4) ("Gamma" . 3) ("Rho" . 1) ("Beta" . 5))
Благодаря поддержке
cl-incf для
alist-get:
;; (require 'cl-lib)
(defun simple-count (seq)
"Count each unique element in SEQ."
(let (counts)
(dolist (element seq)
(cl-incf (alist-get element counts 0 nil 'equal)))
counts))
Пример:
(let ((data '(("Alpha" . 1538)
("Beta" . 8036)
("Gamma" . 8990)
("Beta" . 10052)
("Alpha" . 12837)
("Beta" . 13634)
("Beta" . 14977)
("Beta" . 15719)
("Alpha" . 17075)
("Rho" . 18949)
("Gamma" . 21118)
("Gamma" . 26923)
("Alpha" . 31609))))
(simple-count (mapcar 'car data)))
=> (("Rho" . 1) ("Gamma" . 3) ("Beta" . 5) ("Alpha" . 4))