Как мне поймать счет в этом рекурсивном цикле?

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

Обычная задача, которую я люблю делать, — сообщать о результате функции с помощью format:


(defun csv-counter (list)
  (let ((counter 0)
    (email (first list)))
    (if (null list)
    nil
    (progn
      (+ 1 (count email list :test #'string=))
      (incf counter)
      (csv-counter (rest list))))
    (format t "count for email ~a is ~a~%" email counter)))


Номер счетчика в функции формата фактически не накапливает общее число, вместо этого он сообщает о каждом случае как 1

...
count for email [email protected] is 1
count for email [email protected] is 1
count for email [email protected] is 1
... 

Что я делаю не так?

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

leetwinski 18.01.2023 10:28

Но счетчик будет разным для каждой записи в CSV-файле. Мне нужно, чтобы счетчик начинался с 0 для каждого адреса электронной почты.

Vinn 18.01.2023 10:45

Ах! извините, кажется, я неправильно понял .. Не могли бы вы добавить желаемый пример ввода/вывода?

leetwinski 18.01.2023 11:21
Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
1
3
58
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Неясно, для чего предназначена ваша функция или чего вы пытаетесь достичь. Тем не менее, о нем можно кое-что сказать. Ниже я изменил его и прокомментировал некоторые точки цифрами.

(defun csv-counter (list)
  (let ((counter 0)
        (email (first list)))
    ;; (0)
    (if (null list)
        nil
      (progn
        (+ 1 (count email list :test #'string=)) ;(1)
        (incf counter)                           ;(2)
        (csv-counter (rest list))))
    ;; (3)
    (format t "count for email ~a is ~a~%" email counter)))

В (0) counter будет равно нулю при каждом вызове.

В (1) находится выражение, (+ 1 (count email list :test #'string=)) значение которого не используется. Таким образом, это выражение не делает вообще ничего полезного: оно просто служит для того, чтобы сделать временную сложность квадратичной, а не линейной.

В (2) counter увеличивается на 1, что означает, что теперь он будет равен 1. Результатом (2) является то, что если список не пуст, значение counter будет равно 1.

В (3) сообщается это значение: оно будет 1, если список не пустой, 0 в противном случае.

Итак, мы получаем:

count for email nil is 0
count for email fish@bat is 1
count for email foo@bar is 1
count for email foo@bar is 1

Теперь, как я уже сказал выше, непонятно, чего вы пытаетесь достичь. Однако это может быть подсчет количества различных вхождений каждого адреса электронной почты (представленного в виде строки) в их списке. Так, например, учитывая ("foo@bar" "foo@bar" "fish@bat"), вы хотите считать 2 для "foo@bar и 1 для "fish@bat".

Для этого вам нужны две вещи: подсчет для каждого электронного письма и представление о том, какие электронные письма вы видели. Второе имеет решающее значение.

Итак, вот первоначальный подход к этому:

(defun count-distinct-emails (emails)
  (labels ((cde-loop (tail seen counts)
             (cond
              ((null tail)
               counts)
              ((member (first tail) seen :test #'string=)
               ;; already counted this one
               (cde-loop (rest tail) seen counts))
              (t
               ;; a new email
               (let ((email (first tail))
                     (more (rest tail)))
                 (cde-loop more
                           (cons email seen)
                           (acons email (+ 1 (count email more :test #'string=)) counts)))))))
    (cde-loop emails '() '())))

Эта функция сама по себе не является рекурсивной, но у нее есть рекурсивная вспомогательная функция cde-loop, которая записывается как внутреннее определение. Он написан как внутренняя функция, чтобы избежать кошмара, связанного с необходимостью всевозможных странных дополнительных, возможно, необязательных аргументов для функции, которую вы на самом деле вызываете, и потому, что она не вызывается никакой другой функцией, кроме ее родителя. В cde-loop вы можете видеть, что он поддерживает таблицу (список) электронных писем, которые он видел, и создает другую таблицу (список) адресов с подсчетами.

Для этой функции:

> (count-distinct-emails '("foo@bar" "foo@bar" "fish@bat"))
(("fish@bat" . 1) ("foo@bar" . 2))

Затем вы можете написать небольшую функцию репортера:

(defun report-emails (table)
  (dolist (email&count table)
    (format t "~&count for ~A: ~D~%"
            (car email&count) (cdr email&count))))

Так:

> > (report-emails (count-distinct-emails '("foo@bar" "foo@bar" "fish@bat")))
count for fish@bat: 1
count for foo@bar: 2
nil

Теперь count-distinct-emails ужасен: не потому, что он рекурсивен (любая разумная реализация превратит это в цикл), а потому, что он постоянно проверяет список вещей, которые он видел, и список электронных писем, которые он ищет. Гораздо лучший подход — объединить эти две вещи в одну и использовать хеш-таблицу с лучшей производительностью поиска:

(defun count-distinct-emails (emails)
  (labels ((cde-loop (tail table)
             (if (null tail)
                 table
               (progn
                 (incf (gethash (first tail) table 0))
                 (cde-loop (rest tail) table)))))
    (cde-loop emails (make-hash-table :test #'equal))))

Затем функция репортера также должна знать, как использовать хеш-таблицу:

(defun report-emails (table)
  (maphash (lambda (email count)
             (format t "~&count for ~A: ~D~%"
                     email count))
           table))

Обратите внимание, что cde-loop использует хороший трюк: он говорит (incf (gethash (first tail) table 0)): incf знает, как увеличить значение записи в хеш-таблице, и использование значения по умолчанию 0, когда запись отсутствует, означает, что запись возникнет, поэтому вы Не нужно делать неуклюжую «проверку наличия записи, увеличивать, если да», самостоятельно.

Наконец, после того, как вы уступили и использовали хеш-таблицу, это тот случай, когда простое итеративное решение, вероятно, будет более понятным:

(defun count-distinct-emails (emails)
  (let ((table (make-hash-table :test #'equal)))
    (dolist (email emails table)
      (incf (gethash email table 0)))))

Да, это то, что я пытался сделать. Мне нужно будет изучить это. Спасибо за ваше руководство.

Vinn 18.01.2023 11:52

Что делает третий аргумент dolist (в данном случае — таблица)? (dolist (email emails table)

Vinn 19.01.2023 18:25

Винн: Это значение, возвращаемое формой.

ignis volens 20.01.2023 10:58

Для полноты, я думаю, вы могли бы использовать remove-duplicates здесь:

(defun count-distinct-emails (emails)
  (length (remove-duplicates emails :test #'string=)))

Другие вопросы по теме