На самом деле, для определения, является ли строка палиндромной или нет, внешне определенный цикл не требуется.[Замечание: хорошо, я думал, что в начале.Но, как указали @coredump и @jkiiski, функция reverse замедляет процедуру, поскольку копирует всю строку один раз.]
Использование:
(defun palindromep (s)
(string= s (reverse s)))
[Эта функция будет более эффективной, чем ваш код, и она возвращает T, если s палиндромно, иначе NIL.] (Не верно,это только экономит ваши усилия при написании, но это менее эффективно, чем процедура, использующая loop.)
Подробная версия будет такой:
(defun palindromep (s)
(let ((result (string= s (reverse s))))
(write (if result
"Is a palindrome"
"Is not a palindrome"))
result))
Записывает ответ, который вы хотите, но возвращает T или NIL.
Соглашение об именовании для тестовой функции, возвращающей T или NIL, должно заканчиваться именем p для «предиката».
Функция реверса менее производительна, чем цикл while, предложенный @ coredump
Это была моя попытка новичка проверить скорость [не рекомендуется]:
;; Improved loop version by @coredump:
(defun palindromep-loop (string)
(loop with max = (1- (length string))
for i from 0
for j downfrom max
while (< i j)
always (char= (char string i)
(char string j))))
;; the solution with reverse
(defun palindromep (s)
(string= s (reverse s)))
;; the test functions test over and over the same string "abcdefggfedcba"
;; 10000 times over and over again
;; I did the repeats so that the measuring comes at least to the milliseconds
;; range ... (but it was too few repeats still. See below.)
(defun test-palindrome-loop ()
(loop repeat 10000
do (palindromep-loop "abcdefggfedcba")))
(time (test-palindrome-loop))
(defun test-palindrome-p ()
(loop repeat 10000
do (palindromep "abcdefggfedcba")))
(time (test-palindrome-p))
;; run on SBCL
[55]> (time (test-palindrome-loop))
Real time: 0.152438 sec.
Run time: 0.152 sec.
Space: 0 Bytes
NIL
[56]> (time (test-palindrome-p))
Real time: 0.019284 sec.
Run time: 0.02 sec.
Space: 240000 Bytes
NIL
;; note: this is the worst case that the string is a palindrome
;; for `palindrome-p` it would break much earlier when a string is
;; not a palindrome!
И этоПопытка @ coredump проверить скорость функций:
(lisp-implementation-type)
"SBCL"
(lisp-implementation-version)
"1.4.0.75.release.1710-6a36da1"
(machine-type)
"X86-64"
(defun palindromep-loop (string)
(loop with max = (1- (length string))
for i from 0
for j downfrom max
while (< i j)
always (char= (char string i)
(char string j))))
(defun palindromep (s)
(string= s (reverse s)))
(defun test-palindrome-loop (s)
(sb-ext:gc :full t)
(time
(loop repeat 10000000
do (palindromep-loop s))))
(defun test-palindrome-p (s)
(sb-ext:gc :full t)
(time
(loop repeat 10000000
do (palindromep s))))
(defun rand-char ()
(code-char
(+ #.(char-code #\a)
(random #.(- (char-code #\z) (char-code #\a))))))
(defun generate-palindrome (n &optional oddp)
(let ((left (coerce (loop repeat n collect (rand-char)) 'string)))
(concatenate 'string
left
(and oddp (list (rand-char)))
(reverse left))))
(let ((s (generate-palindrome 20)))
(test-palindrome-p s)
(test-palindrome-loop s))
Evaluation took:
4.093 seconds of real time
4.100000 seconds of total run time (4.068000 user, 0.032000 system)
[ Run times consist of 0.124 seconds GC time, and 3.976 seconds non-GC time. ]
100.17% CPU
9,800,692,770 processor cycles
1,919,983,328 bytes consed
Evaluation took:
2.353 seconds of real time
2.352000 seconds of total run time (2.352000 user, 0.000000 system)
99.96% CPU
5,633,385,408 processor cycles
0 bytes consed
Из чего я научился: - проверять более строго, повторять столько раз, сколько необходимо (диапазон секунд) - выполнить случайную генерацию, а затем проверить впараллель
Большое спасибо за хороший пример@coredump!И за замечание @jkiiski!