Skip to content
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.

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

Improve lookup algorithm efficiency #120

Open
pirj opened this issue Jul 11, 2019 · 0 comments
Open

Improve lookup algorithm efficiency #120

pirj opened this issue Jul 11, 2019 · 0 comments
Labels
feature request an issue that asks for a feature which is not supported yet help wanted

Comments

@pirj
Copy link
Contributor

pirj commented Jul 11, 2019

The way lookup works now:

examples_to_run = [ ]

changed_files.each do |file| # n
  examples.each do |ex| # n * n
    examples_to_run << ex if ex.related_files.include?(file) # n * n * n
  end
end

Invert the way data is stored

examples_to_run = changed_files.flat_map(&:related_examples) # O(n)

# For a single file (as in the file that was just
# saved when using --watch)
examples_to_run = changed_file.related_examples # O(1)

Pros:

  • Faster lookup
    Cons:
  • Uses more memory
  • Have larger dump files
  • Significant effort to perform this inversion
  • Backwards incompatibility
@pirj pirj added feature request an issue that asks for a feature which is not supported yet help wanted labels Jul 11, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
feature request an issue that asks for a feature which is not supported yet help wanted
Projects
None yet
Development

No branches or pull requests

1 participant