Common Lisp: В чем недостаток использования этой функции фильтра в очень больших списках?

Question

Я хочу отфильтровать все элементы списка «a из списка» b и вернуть отфильтрованный b.Это моя функция:

(defun filter (a b)
  "Filters out all items in a from b"
    (if (= 0 (length a)) b
      (filter (remove (first a) a) (remove (first a) b))))

Я новичок в lisp и не знаю, как 'remove работает, в какое время будет работать этот фильтр?

Answer 1

Есть два способа узнать:

• вы можете проверить это с данными

• вы можете проанализировать ваш исходный код

Давайте посмотрим на исходный код.

• списки построены из связанных cons-ячеек

• длина должна пройти один раз по списку

• для КАЖДОГО рекурсивного вызова FILTER вы вычисляете длину a. BAD!

  (используйте ENDP.)

• УДАЛИТЬ нужно пройти один раз по списку

• для каждого рекурсивного вызова, который вы вычисляете УДАЛИТЬ дважды: ПЛОХО!

  (Вместо того, чтобы использовать REMOVE на a, выполнить рекурсив с REST.)

• вызов FILTER не обязательно будет оптимизированным оконечным вызовом. В некоторых реализациях это может произойти, в некоторых вам нужно указать компилятору что вы хотите оптимизировать для хвостовых вызовов, в некоторых реализациях Оптимизация хвостовых вызовов недоступна. Если нет, то вы получите стек переполнение достаточно длинных списков.

  (Используйте циклические конструкции, такие как DO, DOLIST, DOTIMES, LOOP, REDUCE, MAPC, MAPL, MAPCAR, MAPLIST, MAPCAN или MAPCON вместо рекурсии, когда это применимо.)

Резюме: это очень наивный код с низкой производительностью.

Common Lisp предоставляет это встроенное: SET-DIFFERENCE должен делать то, что вы хотите.

http://www.lispworks.com/documentation/HyperSpec/Body/f_set_di.htm#set-difference

Answer 2

(defun filter (a b)
  "Filters out all items in a from b"
    (if (not (consp a)) b
      (filter (rest a) (rest b))))

Answer 3

Я бы не писал эту функцию, потому что Райнер Йосвиг говорит , стандарт уже обеспечивает SET-DIFFERENCE. Тем не менее, если бы мне пришлось предоставить реализацию функции, я бы использовал ее:

(defun filter (a b)
  (let ((table (make-hash-table)))
    (map 'nil (lambda (e) (setf (gethash e table) t)) a)
    (remove-if (lambda (e) (gethash e table)) b)))

Делая это таким образом, вы получаете несколько преимуществ, наиболее важным из которых является то, что он проходит только b один раз; использование хеш-таблицы для отслеживания того, какие элементы находятся в a, вероятно, будет работать намного лучше, если a длинный.

Кроме того, использование общих функций последовательности, таких как MAP и REMOVE-IF, означает, что эта функция может использоваться со строками и векторами, а также со списками, что является преимуществом даже по сравнению со стандартной функцией SET-DIFFERENCE. Основным недостатком этого подхода является то, что если вы хотите расширить функцию с помощью аргумента :TEST, который позволяет пользователю предоставлять предикат равенства, отличный от значения по умолчанию EQL, поскольку хеш-таблицы CL работают только с небольшим числом предварительно определенные предикаты равенства (точнее, EQ, EQL, EQUAL и EQUALP).

Answer 4

Common Lisp не поддерживает оптимизацию хвостового вызова (согласно стандарту), и вам может просто не хватить памяти с ужасным стеком вызовов (в зависимости от реализации).