Question and Request: Sorting after conversion to second

[ilya16]

Is your feature request related to a problem? Please describe. What is the reason for adding sorting after converting MIDI from ticks to seconds in symusic 0.4.0 https://github.com/Yikai-Liao/symusic/commit/f93d6aec086431985c33ffd8c65533095fdbf09d? I think it confuses the expectation of the conversion method as you expect the MIDI events to change their time domain but not the order.

In my use case, I need to keep track of the order of notes in MIDI at various stages of preprocessing. Sorting them under the hood during conversion leads to unexpected results. I'd rather sort the MIDI events afterwards if I need to.

Describe the solution you'd like I would like to have sorting after the time conversion optional by a boolean flag if there is a need for sorting.

Describe alternatives you've considered Sort the notes again after the conversion, but this adds overhead to the computation. Also, if the notes weren't sorted beforehand, it's harder to get them back in their original order.

[Yikai-Liao]

In our previous implementation of tick to second conversion, we always sorted all the events first and then converted them. Since we need to process start and end separately, the result returned by the old version is actually the result of sorting with end as the key. Later, in order to align the order of the notes decoded directly from midi, the notes are sorted according to (start, pitch, duration) after conversion.

But I miscalculated the complexity.

Assuming the number of events is n and the number of tempo is m, the sorting complexity is O(nlogn) and the subsequent conversion complexity is O(n). Then，the total complexity is O(nlogn).

If a binary search is performed for each event, the overall complexity is only O(nlogm).

Of course, frequent branch prediction in this can also have a large impact on performance. Or perhaps the performance difference between the two is negligible.

Order preserving is indeed better interface semantics, I'll take some time to test it out.

Thank you for your feedback.

[Yikai-Liao]

I have test them, using the mahler.mid

• sort version: 491 µs
• binary search version: 827 µs

It looks like the difference between these two algorithms, in terms of the constant factor of complexity, is relatively large.

Even using bisection search having lower complexity and in case N is large enough (mahler), the time consumed is still close to twice that of the sort version.

Of course, this time consumption, while a large increase in percentage, is still actually acceptable overall.

But do you think there is a better implementation of it for order preservation? @ilya16

[ilya16]

@Yikai-Liao I could not think of any other implementation for order preservation.

mahler.mid has many tempo changes, which is unusual for most MIDIs. What will be the time differences if you take e.g. 1 or <10 tempo changes?

And the conversion time is less than the MIDI read time, which is acceptable.

[Yikai-Liao]

I have commit the new order preserving implementation. By caching the binary search result, it could get a better speed. You could also test it yourself. @ilya16

[ilya16]

@Yikai-Liao I have tested the changes, works fine. Thank you for the service, I will close the issue.