Sugerencias para el análisis algorítmico de programas Lisp?

Question

¿Qué operaciones en los programas Common Lisp se deben considerar suficientemente primitivas como para contar para un único "paso" en el análisis algorítmico? ¿Cuán ampliamente varían los ceceos modernos en su implementación?

Ciertamente, la aritmética con enteros pequeños contaría como un solo paso, pero ¿qué pasa con los números más grandes? ¿Y si consideramos la diferencia entre reverse y nreverse? Específicamente, ¿es nreverse theta de reverse? ¿Qué pasa con todas las operaciones de matriz y secuencia? Además, ¿cómo figuran las macros? ¿Cómo debo pensar en las macros cuando analizo la complejidad?

Answer 1

• No intente encontrar una capa inferior de "pasos únicos" uniformes, solo sepa lo que es O (1) y lo que no.
• La adición de "números más grandes" (bignum s) debe ser O (log n) donde n es el mayor de los enteros. Hay muchos algoritmos diferentes para la multiplicación; No soy un experto en el campo, y es probable que sea específico de la implementación.
• reverse y nreverse pueden ambos implementarse O (n) (reverse por una estrategia de CDR-input-y-contra-salida; nreverse mediante el intercambio de punteros mientras cdring). Si entiendo el término desconocido "theta of" correctamente, entonces sí. Tenga en cuenta, sin embargo, que el estándar CL no ofrece ninguna garantía sobre la complejidad del tiempo.
• Las operaciones de secuencia incorporadas generalmente se implementan eligiendo una implementación de matriz o de lista específica según el tipo de argumento, por lo que se espera que sea el algoritmo eficiente ordinario para ese tipo de datos.
• Las macros simplemente se expanden a otro código. Puedes ver su expansión, o ver lo que están documentados para hacer, o hacer una conjetura sobre el algoritmo que usa su expansión. La complejidad del macroexpandidor es completamente irrelevante (a menos que esté usando eval/compile, en cuyo caso también debe pensar en la complejidad del compilador de la implementación) ya que se ejecuta en tiempo de compilación, una vez; solo el código expandido importa.