Задача
Допустим, у вас есть несколько списков или массивов, скажем, два для примера:
(defparameter *arr* #(1 2 3))
(defparameter *list* '(4 5 6))
Вы можете loop над ними, используя across или in ключевые слова:
(loop for elem across *arr* do (format t "~a" elem))
=> 123
(loop for elem in *list* do (format t "~a" elem))
=> 456
Я хочу иметь возможность loop для этих массивов или списков, используя тот же синтаксис. Я использую SBCL, и скорость выполнения является проблемой.
Использование being the elements of
Этот синтаксис хорош, поскольку он работает независимо от того, является ли аргумент list или array.
(loop for elem being the elements of *arr* do (format t "~a" elem))
=> 123
(loop for elem being the elements of *list* do (format t "~a" elem))
=> 456
Но его скорость ужасна. Если мы сделаем быстрое сравнение, получив доступ к спискам или массивам из 100 элементов 1M раз:
(format t "# Test 1.1.1 : Accessing list of doubles with loop 'in': ") (terpri)
(let ((test-list (make-list 100 :initial-element 12.2d0))
(testvar 0d0))
(declare (optimize (speed 3))
(type list test-list)
(type double-float testvar))
(time (dotimes (it 1000000 t) (loop for el in test-list do
(setf testvar (the double-float el))))))
(format t "# Test 1.1.2 : Accessing list of doubles with loop 'elements': ") (terpri)
(let ((test-list (make-list 100 :initial-element 12.2d0))
(testvar 0d0))
(declare (optimize (speed 3))
(type list test-list)
(type double-float testvar))
(time (dotimes (it 1000000 t) (loop for el being the elements of test-list do
(setf testvar (the double-float el))))))
(format t "# Test 1.2.1 : Accessing simple-array of doubles using loop 'across' : ") (terpri)
(let ((test-array (make-array 100 :initial-element 12.2d0 :element-type 'double-float))
(testvar 0d0))
(declare (optimize (speed 3))
(type double-float testvar)
(type simple-array test-array))
(time (dotimes (it 1000000 t) (loop for el across test-array do
(setf testvar (the double-float el))))))
(format t "# Test 1.2.2 : Accessing simple-array of doubles using loop 'elements' : ") (terpri)
(let ((test-array (make-array 100 :initial-element 12.2d0 :element-type 'double-float))
(testvar 0d0))
(declare (optimize (speed 3))
(type double-float testvar)
(type simple-array test-array))
(time (dotimes (it 1000000 t) (loop for el being the elements of test-array do
(setf testvar (the double-float el))))))
Это дает нам:
# Test 1.1.1 : Accessing list of doubles with loop 'in':
Evaluation took:
0.124 seconds of real time
0.123487 seconds of total run time (0.123471 user, 0.000016 system)
99.19% CPU
445,008,960 processor cycles
672 bytes consed
# Test 1.1.2 : Accessing list of doubles with loop 'elements':
Evaluation took:
0.843 seconds of real time
0.841639 seconds of total run time (0.841639 user, 0.000000 system)
99.88% CPU
3,034,104,192 processor cycles
0 bytes consed
# Test 1.2.1 : Accessing simple-array of doubles using loop 'across' :
Evaluation took:
0.062 seconds of real time
0.062384 seconds of total run time (0.062384 user, 0.000000 system)
100.00% CPU
224,896,032 processor cycles
0 bytes consed
# Test 1.2.2 : Accessing simple-array of doubles using loop 'elements' :
Evaluation took:
1.555 seconds of real time
1.554472 seconds of total run time (1.541572 user, 0.012900 system)
[ Run times consist of 0.094 seconds GC time, and 1.461 seconds non-GC time. ]
99.94% CPU
5,598,161,100 processor cycles
1,600,032,848 bytes consed
Я думаю, что он должен использовать аксессор elt? В любом случае штраф в скорости недопустим.
Пытаться быть умным с макросами
Я написал что-то, чтобы можно было достичь того же синтаксиса для list и array. Я думаю, что это не здорово, потому что это кажется слишком неловким, но здесь:
(defun forbuild (el-sym list-or-array list-or-array-sym)
"Outputs either :
* (for el-sym in list-or-array)
* (for el-sym across list-or-array)
Depending on type of list-or-array.
el-sym : symbol, eg. 'it1
list-or-array : declared, actual data for list or array
list-or-array-sym : symbol name for the table, to avoid writing the data in full
in the 'loop' call using eval.
Example call : (forbuild 'it1 arr 'arr)"
(cond ((typep list-or-array 'array)
`(for ,el-sym across ,list-or-array-sym))
((typep list-or-array 'list)
`(for ,el-sym in ,list-or-array-sym))))
(defun forbuild-l (l-elsyms l-lars l-larsyms)
"forbuild but over lists of things."
(let ((for-list nil)
(list-temp nil))
(loop for elem in l-elsyms
for lar in l-lars
for larsym in l-larsyms do
(setf list-temp (forbuild elem lar larsym))
(loop for word-temp in list-temp do
(push word-temp for-list)))
(nreverse for-list)))
(defun loop-expr (forlist body)
"Creates the expression ready to be evaluated to execute the loop.
forlist : List of symbols to be inserted syntactically. eg.
FOR IT1 ACROSS ARR1 FOR IT2 IN ARR2
body : all the expression after the 'for' clauses in the 'loop'."
`(loop ,@forlist ,@body))
(defmacro looparl (element list-or-array &rest body)
(let ((forlist (gensym)))
`(let ((,forlist (forbuild2-l (quote ,element)
(list ,@list-or-array)
(quote ,list-or-array))))
(loop-expr ,forlist (quote ,body)))))
В основном я строю правильный loop синтаксис из аргументов. Приведенную здесь версию looparl можно назвать так:
(let ((arr1 #(7 8 9))
(list2 (list 10 11 12)))
(looparl (it1 it2) (arr1 list2) do (format t "~a ~a" it1 it2) (terpri)))
=> (LOOP FOR IT1 ACROSS ARR1
FOR IT2 IN LIST2
DO (FORMAT T "~a ~a" IT1 IT2) (TERPRI))
Фактическая оценка этого выведенного выражения в этом примере опущена, поскольку он не работает с неглобальными именами. Если мы добавим eval в конце looparl:
(defmacro looparl (element list-or-array &rest body)
(let ((forlist (gensym)))
`(let ((,forlist (forbuild2-l (quote ,element)
(list ,@list-or-array)
(quote ,list-or-array))))
(eval (loop-expr ,forlist (quote ,body))))))
И работая с глобальными переменными, мы видим, что у нас все еще есть проблема скорости, так как во время выполнения происходят оценки:
(looparl (it1 it2) (*arr* *list*) for it from 100
do (format t "~a ~a ~a" it1 it2 it) (terpri))
=> 1 4 100
2 5 101
3 6 102
(time (dotimes (iter 1000 t) (looparl (it1 it2) (*arr* *list*) for it from 100
do (format t "~a ~a ~a" it1 it2 it) (terpri))))
=> Evaluation took:
1.971 seconds of real time
1.932610 seconds of total run time (1.892329 user, 0.040281 system)
[ Run times consist of 0.097 seconds GC time, and 1.836 seconds non-GC time. ]
98.07% CPU
1,000 forms interpreted
16,000 lambdas converted
7,096,353,696 processor cycles
796,545,680 bytes consed
Макросы оцениваются каждый раз по тысяче раз. Но наверняка тип известен во время компиляции нет? Тип синтаксиса в looparl очень хорош, и я хотел бы использовать его без потери скорости.
Я прочитал эту заметку в Книга Питера Сейбела «Практический общий Лисп», глава «Петля для черных поясов»
3 Вы можете задаться вопросом, почему LOOP не может выяснить, циклично ли он над списком или вектором, не требуя других предлогов. Это еще одно следствие того, что LOOP является макросом: значение списка или вектора не будет известно до времени выполнения, но LOOP как макрос должен генерировать код во время компиляции. И дизайнеры LOOP хотели, чтобы он генерировал чрезвычайно эффективный код. Чтобы иметь возможность генерировать эффективный код для циклического прохождения, скажем, вектора, он должен знать во время компиляции, что значение будет вектором во время выполнения - таким образом, необходимы различные предлоги.
Я совершаю какую-то большую ерунду из Common-Lisp? Как бы вы пошли на создание рабочего, быстрого looparl?
Редактировать 1: FOR библиотека
Спасибо, Эвинс, за ссылку на библиотеку FOR . Ключевое слово over в функции for:for - это именно то, что мне нужно. Однако тесты действительно не впечатляют:
(let ((test-list (make-list 100 :initial-element 12.2d0))
(testvar 0d0))
(declare (optimize (speed 3))
(type list test-list)
(type double-float testvar))
(time (dotimes (it 1000000 t)
(for:for ((el over test-list))
(setf testvar (the double-float el))))))
(let ((test-array (make-array 100 :initial-element 12.2d0))
(testvar 0d0))
(declare (optimize (speed 3))
(type simple-array test-array)
(type double-float testvar))
(time (dotimes (it 1000000 t)
(for:for ((el over test-array))
(setf testvar (the double-float el))))))
Evaluation took:
4.802 seconds of real time
4.794485 seconds of total run time (4.792492 user, 0.001993 system)
[ Run times consist of 0.010 seconds GC time, and 4.785 seconds non-GC time. ]
99.83% CPU
17,286,934,536 processor cycles
112,017,328 bytes consed
Evaluation took:
6.758 seconds of real time
6.747879 seconds of total run time (6.747879 user, 0.000000 system)
[ Run times consist of 0.004 seconds GC time, and 6.744 seconds non-GC time. ]
99.85% CPU
24,329,311,848 processor cycles
63,995,808 bytes consed
Скорость этой библиотеки с использованием специализированных ключевых слов in и across такая же, как и для стандартного loop. Но очень медленно с over.
Редактировать 2: map и etypecase
Спасибо, sds и Райнер Йосвиг за предложения. Это действительно будет работать для простого случая, когда у меня будет только один массив / список для повторения. Позвольте мне рассказать вам об одном сценарии использования, который я имел в виду: я реализовал оболочку gnuplot , как для обучения, так и для того, чтобы в моем наборе инструментов была своя собственная программа. Я хотел равнодушно взять из списков пользователей или массивов серию для передачи в gnuplot. Вот почему мне нужно иметь возможность циклически обрабатывать несколько массивов / списков одновременно, используя элегантные предложения цикла для номера итерации и т. Д.
В этом случае использования (оболочка gnuplot) у меня есть только два или три предложения for в моем loop для каждого «блока данных», поэтому я подумал о написании каждой комбинации в зависимости от типа ввода вручную и это возможно, но очень неловко. И я бы застрял, если бы мне пришлось сделать что-то вроде:
(loop for el1 in list1
for el2 across arr1
for el3 in list2
for el4 in list3
...)
С входами list-i и arr-i.Еще один запасной план для этого варианта использования - просто преобразовать все в массивы.
Я подумал, что, поскольку это довольно легко концептуализировать, я мог бы написать что-то гибкое и быстрое раз и навсегда, но должна быть причина, почемуего нет ни в спецификации, ни в специфичном для SBCL коде.