Class: Hone::Patterns::BsearchVsFind

Inherits:
Base
  • Object
show all
Defined in:
lib/hone/patterns/bsearch_vs_find.rb

Overview

Pattern: sorted_array.find { |x| x >= target } -> sorted_array.bsearch { |x| x >= target }

When searching sorted data for the first element matching a comparison, bsearch uses binary search (O(log n)) vs find's linear search (O(n)).

This pattern is conservative and only reports when it detects:

  • find with a block containing >= or > comparison
  • The receiver name contains hints like "sorted" or common sorted collection names

Constant Summary collapse

SORTED_HINTS =

Names that suggest the array is sorted

%w[sorted ordered ranked].freeze

Instance Attribute Summary

Attributes inherited from Base

#findings

Instance Method Summary collapse

Methods inherited from Base

#add_finding, inherited, #initialize, scan_file

Constructor Details

This class inherits a constructor from Hone::Patterns::Base

Instance Method Details

#visit_call_node(node) ⇒ Object 



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
# File 'lib/hone/patterns/bsearch_vs_find.rb', line 20

def visit_call_node(node)
  super

  return unless node.name == :find
  return unless block_attached?(node)

  block = node.block
  return unless block.is_a?(Prism::BlockNode)
  return unless comparison_block?(block)
  return unless likely_sorted_receiver?(node.receiver)

  add_finding(
    node,
    message: "Consider `.bsearch { }` instead of `.find { }` for O(log n) search on sorted data",
    speedup: "O(log n) vs O(n) for sorted data"
  )
end