toptal/crystalball

Improve lookup algorithm efficiency

pirj opened this issue · 0 comments

pirj commented

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