Предложения по алгоритмическому анализу программ на Лиспе?

Question

Какие операции в программах Common Lisp следует считать достаточно примитивными, чтобы рассчитывать на один «шаг» в алгоритмическом анализе? Насколько широко современные лиспы различаются по своей реализации?

Конечно, арифметика с маленькими целыми числами будет считаться одним шагом, но как насчет больших чисел? А как насчет разницы между reverse и nreverse? В частности, nreverse тета reverse? Как насчет всех операций с массивами и последовательностями? Кроме того, как фигурируют макросы - как я должен думать о макросах при анализе сложности?

Answer 1

• Не пытайтесь найти нижний слой однородных «одиночных шагов», просто знайте, что O (1), а что нет.
• Добавление "больших чисел" (bignum s) должно быть O (log n), где n - это большее из целых чисел. Есть много разных алгоритмов для умножения; Я не эксперт в этой области, и это, вероятно, будет зависеть от конкретной реализации.
• reverse и nreverse могут быть оба реализованы O (n) (reverse с помощью стратегии cdr-input-and-cons-output; nreverse путем обмена указателями во время cdring). Если я правильно понимаю незнакомый термин «тета», тогда да. Обратите внимание, однако, что стандарт CL не дает никаких гарантий относительно временной сложности.
• Встроенные операции последовательности обычно реализуются путем выбора реализации для массива или списка в зависимости от типа аргумента, и поэтому следует ожидать, что это будет обычный эффективный алгоритм для этого типа данных.
• Макросы просто расширяются в другой код. Вы можете посмотреть на их расширение, посмотреть, что они задокументировали, или сделать обоснованное предположение об алгоритме, который использует их расширение. Сложность макроэкспандера совершенно не имеет значения (если вы не используете eval / compile, и в этом случае вам также нужно подумать о сложности компилятора реализации), поскольку он запускается во время компиляции, один раз; имеет значение только расширенный код.