Prepend vs. Append perf в Mathematica

в Lisp-подобных системах, cons - это нормальный способ PREPEND элемента к списку. Функции, которые добавляют к списку, намного дороже, потому что они проходят список до конца, а затем заменяют последний нуль ссылкой на добавленный элемент. IOW (pseudoLisp)

(prepend list item) = (cons item list) = cheap!
(append list item) = (cond ((null? list) (cons item null))
                           (#t (cons (car list (append (cdr list) item)))))

Вопрос в том, похожа ли ситуация в Mathemtica? В большинстве случаев списки Mathematica кажутся односвязными, как списки lisp, и, если это так, мы можем предположить, что Append [list, item] намного дороже, чем Prepend [list, item]. Однако мне не удалось найти что-либо в документации по Mathematica, чтобы ответить на этот вопрос. Если списки Mathematica двусвязаны или реализованы более умно, например, в куче или просто с сохранением указателя на последний, то вставка может иметь совершенно другой профиль производительности.

Мы будем благодарны за любой совет или опыт.

8
задан Reb.Cabin 9 December 2011 в 19:37
поделиться