On Wed, Sep 23, 2015 at 6:54 AM, David Kastrup <d...@gnu.org> wrote:
[...]
>
> Well, I don't know who is responsible for this particular idiom
> encountered frequently in here,
That would be me....
> but the following open-coded loop is
> both opaque and inefficient (namely O(n^2) as _appending_ to a list is
> an O(n) operation):
>
> extractLyricEventInfo =
> #(define-scheme-function (lst) (ly:music?)
> "Given a music expression @var{lst}, return a list of pairs. The
> @code{car} of each pair is the text of any @code{LyricEvent}, and the
> @code{cdr} is a boolean representing presence or absence of a hyphen
> associated with that @code{LyricEvent}."
> ;; TODO: include duration info, skips?
> (let ((grist (extract-named-music lst '(LyricEvent))))
> (let mill ((grist grist) (flour '()))
> (if (null? grist)
> flour
> (let* ((text (ly:music-property (car grist) 'text))
> (hyphen (extract-named-music (car grist) 'HyphenEvent))
> (hyphen? (not (null? hyphen))))
> (mill (cdr grist)
> (append flour (list (cons text hyphen?)))))))))
>
> Open-coded, you are much better off writing:
>
> (let ((grist (extract-named-music lst '(LyricEvent))))
> (let mill ((grist grist) (flour '()))
> (if (null? grist)
> (reverse! flour)
> (let* ((text (ly:music-property (car grist) 'text))
> (hyphen (extract-named-music (car grist) 'HyphenEvent))
> (hyphen? (not (null? hyphen))))
> (mill (cdr grist)
> (cons (cons text hyphen?) flour))))))
>
> Since cons is O(1) and the final reverse! O(n) is only done once, you
> arrive at O(n) for all. But why open-code in the first place?
>
> (map (lambda (elt)
> (let* ((text (ly:music-property elt 'text))
> (hyphen (extract-named-music elt 'HyphenEvent))
> (hyphen? (pair? hyphen)))
> (cons text hyphen)))
> (extract-named-music lst 'LyricEvent)))
>
> For something that is one-on-one, this is far more transparent. And
> even for something that is one-to-some (namely resulting in possibly 0,
> 1, or more elements), (append-map (lambda (elt) ...) ...) tends to be
> much clearer.
>
>
OK, thanks! Will update accordingly.
DN
_______________________________________________
lilypond-user mailing list
lilypond-user@gnu.org
https://lists.gnu.org/mailman/listinfo/lilypond-user
