Prev: What do you recommend for documentation generation?
Next: Utility to swap Caps Lock as Control key, or swap Control withAlt
From: vanekl on 10 Mar 2010 21:38
Thomas A. Russ wrote:
> "vanekl" <vanek(a)acd.net> writes:
>
>> floaiza wrote:
>>> Five possible ways have been suggested to address the question of
>>> how to generate a string that is N times some component string,
>>> e.g., "-". ...
>>> QUESTION: Is there one or more criteria to decide which one to use?
>>
>> Picking the algorithm that CONSes the least usually pays off,
>> assuming you need to optimize. More on that below.
>>
>>
>>> Speed of execution is mentioned as something to keep in mind; is
>>> this the only criterion?
>>
>> No. Don't create garbage (memory allocations) if you can help it.
>> Write a long-running program and you'll figure out why.
>
> Well, these garbage collection concerns were once a lot more important
> than they are today. Short-lived garbage is often no longer a problem
> with the use of a good generational garbage collector.
>
> Perhaps the most important consideration is to make sure that you
> don't end up using a hopelessly inefficient algorithm. Lisp can
> often lead new programmers astray because there are a lot of
> convenient constructs that hide their true complexity. No amount of
> micro-optimization will save you from algorithms with terrible
> asymptotic performance.
>
> Consider the classic case of adding things to the end of a list.
>
> (defun square-list (list-of-numbers)
> "Don't write programs like this one!"
> (let ((result nil))
> (dolist (n list-of-numbers)
> (setq result (append result (list (* n n)))))
> result))
>
> It doesn't matter what you do to the compuation of (* n n) because you
> will be killed by the N^2 behavior of the repeated calls to APPEND.


In theory I agree with everything you are saying, and, in fact, say as much
elsewhere in my note. In practice, Big-O problems are a rarer problem (for
me) than the long pauses I see when I'm not careful with my consing. It may
be a problem with the CL implementation I use, or not, but this efficiency
concern is certainly always present for those of us commies (I think that's
what Kenny called us) who prefer using a free lisp with
not-quite-state-of-the-art garbage collection.


First  |  Prev  | 
Pages: 1 2 3
Prev: What do you recommend for documentation generation?
Next: Utility to swap Caps Lock as Control key, or swap Control withAlt