Зацикливаясь на массивах или списках безразлично
проблема
Допустим, у вас есть несколько списков или массивов, скажем, два для примера:
(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 коде.
3 ответа
Для тривиального использования вы можете сделать
(flet ((do-something (e)
...))
(etypecase foo
(vector (loop for e across foo do (do-something e)))
(list (loop for e in foo do (do-something e))))
Диспетчеризация типа времени выполнения, вероятно, будет быстрее, чем общая итерационная конструкция, использующая абстракцию последовательности.
Библиотека для Шинмера, имеет общий over итератор:
(ql:quickload "for")
(for:for ((a over *arr*)
(b over *list*))
(print (list a b)))
;; (1 4)
;; (2 5)
;; (3 6)
Он также имеет "in" и "accross", поэтому он может помочь использовать "over" во время разработки и уточнить позже, если это необходимо.
Я дам вам сделать тесты:)
То, что вы ищете, называется map: и то и другое
(map nil #'princ '(1 2 3))
а также
(map nil #'princ #(1 2 3))
Распечатать 123,
Однако списки и массивы очень разные звери, и лучше заранее решить, какой из них вы хотите использовать.
Принуждение массива к списку с последующим циклом дает такую же производительность, как если бы это был список в первую очередь, что не так хорошо, как с массивом, но не так плохо, как использование element, и у него есть достоинство работы со списком или массивом без дополнительного оборудования:
(loop for x in (coerce array 'list) do something)