Добрый вечер!
Подскажите пожалуйста, как можно разграничить, когда применять массив, а когда список?
Я пришел в Lisp из Delphi, где из структур данных есть только массивы, классы да записи с указателями.
Списочных структур нет и в помине (т.е., конечно, можно сделать ручками в динамике).
А здесь - на выбор: и списки, и массивы, и хеши (и еще чего-то наверное есть, что я еще не знаю как использовать).
Начав практически пользоваться Лиспом стал замечать, что работаю со списками - как с массивами: обход по элементам,
обращение по индексу, (dotimes (i (length lst))... и т.д. Работать оно, конечно, работает, но как-то я не очень понимаю как.
В чем разница между списками и массивами, если я могу и там, и там наращивать длину, обращаться поэлементно,
менять содержимое произвольно (ибо типизация позволяет)?
Время доступа к элементам списка O(N), а у массива O(1), поэтому массивы нужно применять, когда нужен быстрый доступ. Вставка элементов в массив в его середину может быть накладной операцией в отличие от списков. Поэтому списки хороши, когда нужно много добавлять данных в середину.
Или как вариант - все делаем на списках, а потом если тормозить начинает - переписываем на что-то более подходящее:).
Да, разумно:) Прототипируем на списках, далее в соответствии с требованиями производительности меняем на массивы, ну типа того.
А вы вообще читали PCL и/или Мир Лиспа?
Там разъясняется строение списков. Массив же это просто область данных. В общем рекомендую изучить их строение, после этого всё станет очевидно.
вы можете использовать ф-ции высших порядков, это намного удобнее чем вручную с итерациями
А я люблю loop использовать. Требует практики, но окупается. Функционалы хороши, но не стоит ими злоупотреблять.
А вообще чем больше знаешь всяких техник и подходов в CL, тем лучше.
Спасибо большое за ответы!
О(N) и О(1), собственно, все объясняет.
LinkFly: PCL читаю, застрял на макросах ;) Ну а про списки... не дошло до меня сразу, видимо.
PS. Долго ответить не мог - лежал с температурой.
В CL во всем нужна практика, очень многое делается совершенно непривычным образом.
Ну а про подходы - это везде актуально :)
Интересно, кто-нибудь такую вещь как Series использует? С одной стороны, подход функциональный, а с другой - трансформируется все в циклы.
> Интересно, кто-нибудь такую вещь как Series использует?
Я пытался то и дело её освоить, но до сих пор не получалось. Наконец начал разбираться. Убедился, что Series не менее эффективны, чем простые циклы или хвостовая рекурсия. Главное их умение — собирать из нескольких циклов (никак до этого не связанных) единый цикл.
Вот например решение для 72-й задачи Проекта Эйлер — число несократимых дробей с знаменателем до 10
6; оно выразимо через функцию Эйлера (totient):
(defun primetest ()
(declare (optimizable-series-function))
(catenate
(series:scan '(2 3))
(producing
(primes) ((prime 5) (delta 1))
(declare (type fixnum prime delta))
(loop
(tagbody
(next-out primes prime)
(incf prime (- 3 delta))
(decf delta (* 2 delta)))))))(defun factors (n)
(declare (optimizable-series-function))
(let ((primetests (primetest)))
(producing (factors) ((primetests primetests)
prime (n n) (top (isqrt n)))
(declare (type fixnum prime top))
(loop
(tagbody
(when (= n 1) (terminate-producing))
(when prime (go repeate))
next-prime
(setq prime (next-in primetests nil))
(when (> prime top)
(setq prime n n 1)
(go next-out))
repeate
(unless (zerop (rem n prime))
(go next-prime))
(setq n (truncate n prime)
top (isqrt n))
next-out
(next-out factors prime))))))(defun unique (s)
(declare (optimizable-series-function)
(off-line-port 0))
(choose (mapping ((e s) (p (previous s)))
(not (equal e p)))
s))(defun totient (n)
(declare (optimize speed (safety 0))
(type fixnum n))
(iterate ((m (unique (factors n))))
(setf n (truncate (the fixnum (* n (- m 1))) m)))
n)(defun p072 (&optional (top (expt 10 6)))
(- (- 2 (1+ (collect-sum (#M totient (scan-range :from 1 :upto top)))))))Primetest генерирует 2, 3 и последовательность нечётных чисел, кроме делящихся на 3. Реализация Unique больше всего напоминает APL/J. Totient можно было бы написать функциональнее, через collect-product, но прямая итерация эффективнее за счёт работы только с целыми числами.
Документация в A. I. Memo 1082 полезнее той, что в CLtL2 или в комплекте с Series, но и её недостаточно.
Однако Primetest нужно писать проще:
(defun primetest ()
(declare (optimizable-series-function))
(catenate (series:scan '(2 3))
(mingle (scan-range :from 5 :by 6)
(scan-range :from 7 :by 6)
#'<)))Либо универсальнее:
(defmacro define-interleave- (n)
(let ((interleave-name (read-from-string (format nil "interleave-~d" n)))
(series-names (loop for i from 0 below n
collect (read-from-string (format nil "s~d" i)))))
`(defun ,interleave-name ,series-names
(declare (optimizable-series-function)
(off-line-port . ,series-names))
(producing (out) (item (index 0) (repeat ,n)
,@(mapcar 'list series-names series-names))
(declare (type fixnum index repeat))
(loop
(tagbody
(setq index (rem (1+ index) repeat))
(case index
,@(loop for i from 1 to n
for s in series-names
collect (list (rem i n) (list 'go s))))
,@(loop for s in series-names
collect s
collect `(setq item (next-in ,s (terminate-producing)))
collect '(go out))
out
(next-out out item)))))))(define-interleave- 2)(defun primetest ()
(declare (optimizable-series-function))
(catenate
(series:scan '(2 3))
(interleave-2
(scan-range :from 5 :by 6 :type 'fixnum)
(scan-range :from 7 :by 6 :type 'fixnum))))