toptal / crystalball

Regression Test Selection library for your RSpec test suite
https://toptal.github.io/crystalball/
MIT License
323 stars 41 forks source link

Improve lookup algorithm efficiency #120

Open pirj opened 5 years ago

pirj commented 5 years ago

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: