8000 Improves finder speed by tomcontileslie · Pull Request #16 · tomcontileslie/ThatChord · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Improves finder speed #16

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 6 commits into from
Aug 28, 2020
Merged

Improves finder speed #16

merged 6 commits into from
Aug 28, 2020

Conversation

tomcontileslie
Copy link
Owner
@tomcontileslie tomcontileslie commented Aug 28, 2020 •
edited
Loading

This addresses issue #8 about many-note guitar chords being noticeably slow. Thank you to @reiniscirpons for his helpful comments which have allowed some useless options which were being considered to be skipped.

The chord finding algorithm in find.py has been updated to do the following:

  • Pre-emptively optimise by removing any notes from the end of the chord request which makes it have more notes than the number of strings.
  • If the current chord attempt is missing k notes to cover all the important notes of the requested chord, increment the counter by enough steps that the first k strings have changed frets. (previously the incrementation was systematically one step). This does not catch all the dead branches - only the ones that are dead from the left side of the instrument neck. But on larger instruments this still skips a load of unnecessary computation.
  • At each step, update only the values of the strings that have been changed, to minimise unnecessary computation.
  • Rather than storing all possibilities then ranking, rank as you go and only store the few best options. (more of a memory-efficient solution than a time-efficient solution)

Empirical verifications suggest that this makes little difference for ukulele, but results in a 6x speedup for guitar chords containing 6 distinct notes (e.g. C11, Dm11) - down from ~7s to ~1s.

@tomcontileslie tomcontileslie merged commit 36b323b into master Aug 28, 2020
@tomcontileslie tomcontileslie mentioned this pull request Aug 28, 2020
Closed
@tomcontileslie tomcontileslie deleted the faster branch August 28, 2020 23:58
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
1 participant
@tomcontileslie
0