improve determine_absolute_timing complexity

Pieter Eendebakrequested to merge
peendebak/quantify-scheduler:feat/determine_absolute_scheduling into pieter_feat_determine_absolute_scheduling

Explanation of changes

The determine_aboslute_timing searched for each timing constraint for the corresponding reference operation. This search is done by a linear search, leading to an O(N**2) complexing for N the number of timing constraints.

This PR improves this by first sorting the list of labels in the timing contraints. Then a binary search can be used, leading to complexity O(N log(N)).

Motivation of changes

The determine_aboslute_timing is one of the (smaller) bottlenecks in generation of our larger schedules.

@AdriaanRol @dcrielaard

Merge checklist

See also merge request guidelines

  • Merge request has been reviewed and approved by a project maintainer.
  • Merge request contains a clear description of the proposed changes and the issue it addresses.
  • Merge request made onto appropriate branch (develop for most MRs).
  • New code is fully tested.
  • New code is documented and docstrings use numpydoc format.
  • CHANGELOG.rst and AUTHORS.rst have been updated (when applicable).
  • CI pipelines pass
    • pre-commit run --all-files --hook-stage commit passes (gitlab-ci),
    • test suite passes (gitlab-ci),
    • no degradation in code-coverage (codacy),
    • no (serious) new pylint code quality issues introduced (codacy),
    • documentation builds successfully (CI and readthedocs),
    • windows tests pass (manually triggered by maintainers before merging).

For reference, the issues workflow is described in the contribution guidelines.

Edited by Pieter Eendebak

Merge request reports