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

Reply via email to