lilypond-user
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Efficiency of alist vs. vector/array


From: Urs Liska
Subject: Re: Efficiency of alist vs. vector/array
Date: Wed, 19 Jul 2017 09:47:15 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.8.0

Obviously I didn't make myself clear enough and probably I should have
invested the time for a minimal example. When sloppily using the word
"override" I didn't mean "\override" but applying a value to a grob
property in a grob callback function.

I have a data structure idTweaks, currently using an alist:

    idTweaks = #'()

This alist gets populated with elements consisting of a key and a
#'(property . value) pair with

idTweak =
#(define-void-function (id prop val)(string? symbol? scheme?)
   (set! idTweaks (assoc-set! idTweaks id (cons prop val))))

using commands like

\idTweak "id-1" color #red
\idTweak "id-2" extra-offset #'(2 . -2)

In the callback stage the callback function looks up if a grob has an
'id property and if there's a matching entry in idTweaks:

#(define (apply-tweaks grob)
   (let*
    ((id (ly:grob-property grob 'id))
     (tweak (if (null? id)
                #f
                (assoc-ref idTweaks id))))
    (if tweak
        (ly:grob-set-property! grob (car tweak) (cdr tweak)))))

Finally in the music the callback is registered and ids assigned to grobs:

{
  \override NoteHead.before-line-breaking = #apply-tweaks
  \override Script.before-line-breaking = #apply-tweaks
  \once \override NoteHead.id = "id-1"
  c' d' -\tweak #'id "id-3" \f e' -\tweak #'id "id-2" ->
}

In this case three items have an id but only two have a tweak assigned:
the c' notehead will be red and the accent on the e will be offset.

(With some additional complexity this can be extended to store lists of
tweaks to an object (e.g. override both color and extra-offset) and to
access the notecolumn, e.g. to shift a note horizontally when still in
the before-line-breaking stage).


Am 18.07.2017 um 18:52 schrieb David Kastrup:
> Urs Liska <address@hidden> writes:
>
>> What I do *not* know is: would that be worth it (apart from the
>> educational value) in real life? In that project I had a song of a few
>> pages containing about 5.600 IDs. It's not clear how many override
>> that would get when finished, but let's assume it'll grow to a few
>> hundred and take 100 as a hypothetical reference.
> Why?  If you do \override without \temporary, any previous alist element
> with the given id set in the same context will be removed first.
>
> So where do you get the 100?

The 100 is a hypothetical number of tweaks that I may need to apply when
I'm going to bring the score to publication quality.
The 5.600 is the actual number of 'id tweaks produced by the external
script that has generated the .ly file.

My question is: an alist is obviously not the ideal data structure for
this setting as it will require 5.600 alist lookups with 555.000 actual
comparisons. If idTweaks was something that can be searched binarily it
would be 5.500x8 (for the unused ids) + 100x4 (for the actual matches)
comparisons, which is significantly less.

The question (at my learning stage) is: does it really matter in that
order of magnitude or would it be "premature optimization" to look for
an improved algorithm/data structure?
And how would the perspective of dramatically bigger scores affect that
estimate?

>
>> My gut feeling is that's really a lot of unnecessary stuff, and one
>> should try to improve where possible. OTOH I don't really have
>> substantial experience wtih this tpic and don't know how that relates
>> to what's going on in the whole compilation process. OTOH what would
>> be if I consider using such a setting for a full symphony with maybe
>> 100.000 grobs and 1.000 overrides? Would I then have to consider a
>> better data structure? Would I then have to think about a totally
>> different approach?
>>
>> Any food for thought, educated guesses, advice?
> You could use an object property just for storing the id of a grob if
> the override machinery (which works in context hierarchies and handles
> subproperties) is not needed.
>
> Check out make-object-property in the manual.

This probably doesn't apply to my original use-case but I'll do that
anyway, of course.

Best
Urs

-- 
address@hidden
https://openlilylib.org
http://lilypondblog.org




reply via email to

[Prev in Thread] Current Thread [Next in Thread]