Overview

Algorithm optimization in Ruby focuses on improving code performance through strategic choices in data structures, algorithms, and implementation patterns. Ruby provides numerous built-in optimizations and tools for analyzing and improving algorithmic efficiency.

The core optimization areas include time complexity reduction, space complexity management, and leveraging Ruby's built-in optimized methods. Ruby's standard library includes highly optimized implementations for common operations like sorting, searching, and data manipulation that often outperform custom implementations.

# Inefficient nested iteration - O(n²)
def find_duplicates_slow(array)
  duplicates = []
  array.each_with_index do |item, i|
    array[(i+1)..-1].each do |other|
      duplicates << item if item == other
    end
  end
  duplicates.uniq
end

# Optimized using Set - O(n)
require 'set'
def find_duplicates_fast(array)
  seen = Set.new
  duplicates = Set.new
  
  array.each do |item|
    if seen.include?(item)
      duplicates.add(item)
    else
      seen.add(item)
    end
  end
  
  duplicates.to_a
end

Ruby's garbage collector and memory management affect algorithmic performance. Understanding object allocation patterns helps optimize memory-intensive algorithms. The ObjectSpace module provides tools for analyzing memory usage and object lifecycle.

Profiling tools like ruby-prof, benchmark, and memory_profiler help identify bottlenecks and measure optimization effectiveness. Ruby's built-in Benchmark module provides basic timing capabilities, while external gems offer more detailed analysis.

Basic Usage

Basic optimization starts with choosing appropriate data structures for specific use cases. Arrays excel at indexed access but perform poorly for membership testing. Hashes provide constant-time lookups but consume more memory. Sets optimize membership testing and duplicate elimination.

# Array membership testing - O(n)
large_array = (1..10000).to_a
large_array.include?(9999)  # Linear search

# Hash key lookup - O(1)
large_hash = (1..10000).each_with_object({}) { |i, h| h[i] = true }
large_hash.key?(9999)  # Constant time

# Set membership testing - O(1)
require 'set'
large_set = (1..10000).to_set
large_set.include?(9999)  # Constant time

Enumerable methods provide optimized implementations for common operations. Methods like map, select, reduce, and group_by use internal iteration that outperforms manual loops in most cases.

# Manual iteration
result = []
(1..1000).each { |n| result << n * 2 if n.even? }

# Optimized enumerable chain
result = (1..1000).select(&:even?).map { |n| n * 2 }

# Further optimized with lazy evaluation for large datasets
result = (1..1_000_000).lazy.select(&:even?).map { |n| n * 2 }.first(100)

Memoization provides significant optimization for recursive algorithms by caching computed results. Ruby's Hash class serves as an effective memoization store for most scenarios.

# Fibonacci without memoization - exponential time complexity
def fibonacci_slow(n)
  return n if n <= 1
  fibonacci_slow(n - 1) + fibonacci_slow(n - 2)
end

# Fibonacci with memoization - linear time complexity
def fibonacci_fast(n, memo = {})
  return n if n <= 1
  memo[n] ||= fibonacci_fast(n - 1, memo) + fibonacci_fast(n - 2, memo)
end

String operations benefit from strategic optimization. String concatenation using << outperforms + for building strings iteratively. The String#tr method provides optimized character replacement that outperforms regular expressions for simple substitutions.

# Inefficient string building
result = ""
1000.times { |i| result = result + i.to_s }

# Optimized string building
result = ""
1000.times { |i| result << i.to_s }

# Most efficient for complex building
result = []
1000.times { |i| result << i.to_s }
final = result.join

Advanced Usage

Advanced optimization techniques involve algorithmic complexity analysis and sophisticated data structure selection. Understanding Big O notation helps evaluate algorithm efficiency and choose appropriate approaches for different problem scales.

Dynamic programming represents a class of optimization techniques that break complex problems into overlapping subproblems. The technique applies memoization systematically to avoid redundant computation.

class LongestCommonSubsequence
  def initialize
    @memo = {}
  end
  
  def lcs_length(str1, str2, i = str1.length - 1, j = str2.length - 1)
    return 0 if i < 0 || j < 0
    
    key = [i, j]
    return @memo[key] if @memo.key?(key)
    
    if str1[i] == str2[j]
      @memo[key] = 1 + lcs_length(str1, str2, i - 1, j - 1)
    else
      @memo[key] = [
        lcs_length(str1, str2, i - 1, j),
        lcs_length(str1, str2, i, j - 1)
      ].max
    end
    
    @memo[key]
  end
end

Custom data structures can provide significant optimizations for specific use cases. Implementing specialized structures like tries for string matching or binary heaps for priority queues often outperforms generic alternatives.

class Trie
  def initialize
    @root = {}
  end
  
  def insert(word)
    node = @root
    word.each_char do |char|
      node[char] ||= {}
      node = node[char]
    end
    node[:end] = true
  end
  
  def search(word)
    node = @root
    word.each_char do |char|
      return false unless node[char]
      node = node[char]
    end
    !!node[:end]
  end
  
  def starts_with(prefix)
    node = @root
    prefix.each_char do |char|
      return false unless node[char]
      node = node[char]
    end
    true
  end
end

Algorithmic optimization often involves trading space for time or vice versa. Preprocessing data structures can convert expensive runtime operations into constant-time lookups.

class RangeQueryOptimizer
  def initialize(array)
    @array = array
    @prefix_sums = build_prefix_sums
  end
  
  # Preprocessing: O(n) time, O(n) space
  def build_prefix_sums
    sums = [0]
    @array.each_with_index do |val, i|
      sums << sums[i] + val
    end
    sums
  end
  
  # Query: O(1) time after preprocessing
  def range_sum(left, right)
    @prefix_sums[right + 1] - @prefix_sums[left]
  end
end

Bitwise operations provide extreme optimization for specific scenarios involving binary data or boolean arrays. Ruby supports all standard bitwise operators and can perform these operations efficiently.

class BitVector
  def initialize(size)
    @size = size
    @bits = Array.new((size + 31) / 32, 0)
  end
  
  def set_bit(index)
    word_index = index / 32
    bit_index = index % 32
    @bits[word_index] |= (1 << bit_index)
  end
  
  def get_bit(index)
    word_index = index / 32
    bit_index = index % 32
    (@bits[word_index] & (1 << bit_index)) != 0
  end
  
  def count_set_bits
    @bits.sum { |word| word.to_s(2).count('1') }
  end
end

Performance & Memory

Performance measurement requires systematic benchmarking to validate optimization effectiveness. Ruby's Benchmark module provides basic timing capabilities, while benchmark-ips gem offers iterations-per-second measurements that account for Ruby's garbage collection patterns.

require 'benchmark'
require 'benchmark/ips'

# Basic timing comparison
array = (1..10000).to_a
Benchmark.bm(20) do |x|
  x.report("Array#include?:") { 1000.times { array.include?(5000) } }
  x.report("Binary search:") { 1000.times { binary_search(array, 5000) } }
end

# Iterations per second measurement
Benchmark.ips do |x|
  x.report("linear search") { array.include?(5000) }
  x.report("binary search") { binary_search(array, 5000) }
  x.compare!
end

Memory optimization involves understanding Ruby's object allocation patterns and garbage collection behavior. The memory_profiler gem tracks object allocations and identifies memory-intensive operations.

require 'memory_profiler'

report = MemoryProfiler.report do
  # Code to profile
  large_array = Array.new(100000) { |i| "string_#{i}" }
  result = large_array.select { |s| s.include?('5') }
end

report.pretty_print

Lazy evaluation through Ruby's Enumerator::Lazy prevents unnecessary memory allocation when processing large datasets. Lazy enumerators compute values on demand rather than materializing entire intermediate collections.

# Memory-intensive: creates multiple intermediate arrays
def process_large_dataset_eager(data)
  data.map { |x| x * 2 }
      .select { |x| x > 100 }
      .map { |x| x.to_s }
      .first(10)
end

# Memory-efficient: lazy evaluation
def process_large_dataset_lazy(data)
  data.lazy
      .map { |x| x * 2 }
      .select { |x| x > 100 }
      .map { |x| x.to_s }
      .first(10)
end

Algorithm choice dramatically affects performance characteristics. Sorting algorithms demonstrate this principle clearly, with different algorithms performing better under different conditions.

class SortingBenchmark
  def self.compare_sorts(array_size)
    data = Array.new(array_size) { rand(1000) }
    
    Benchmark.bm(15) do |x|
      # Ruby's built-in sort (optimized quicksort/mergesort hybrid)
      x.report("Built-in sort:") do
        data.dup.sort
      end
      
      # Custom quicksort implementation
      x.report("Custom quicksort:") do
        quicksort(data.dup)
      end
      
      # Insertion sort (good for small arrays)
      x.report("Insertion sort:") do
        insertion_sort(data.dup)
      end if array_size < 1000
    end
  end
  
  def self.quicksort(array, low = 0, high = array.length - 1)
    return array if low >= high
    
    pivot = partition(array, low, high)
    quicksort(array, low, pivot - 1)
    quicksort(array, pivot + 1, high)
    array
  end
  
  def self.partition(array, low, high)
    pivot = array[high]
    i = low - 1
    
    (low...high).each do |j|
      if array[j] <= pivot
        i += 1
        array[i], array[j] = array[j], array[i]
      end
    end
    
    array[i + 1], array[high] = array[high], array[i + 1]
    i + 1
  end
end

Cache-friendly algorithms consider memory access patterns to optimize performance on modern processors. Sequential memory access patterns significantly outperform random access patterns due to CPU cache behavior.

Common Pitfalls

Premature optimization represents the most common pitfall in algorithmic optimization. Optimizing code before identifying actual bottlenecks through profiling often results in increased complexity without meaningful performance gains.

# Premature optimization: complex caching for rarely-called method
class User
  def expensive_calculation
    @cached_result ||= begin
      # Simple calculation that runs once per user
      age * 365
    end
  end
end

# Better: simple implementation until profiling shows bottleneck
class User
  def age_in_days
    age * 365
  end
end

Micro-optimizations often provide negligible benefits while harming code readability. Focus optimization efforts on algorithmic improvements rather than minor syntax changes.

# Micro-optimization with minimal impact
def sum_even_numbers(numbers)
  sum = 0
  i = 0
  while i < numbers.length
    sum += numbers[i] if numbers[i] & 1 == 0
    i += 1
  end
  sum
end

# Clearer code with equivalent performance
def sum_even_numbers(numbers)
  numbers.select(&:even?).sum
end

Memory leaks occur when optimization attempts inadvertently retain object references. Global caches without size limits or cleanup mechanisms consume increasing memory over time.

# Memory leak: unbounded cache growth
class DataProcessor
  @@cache = {}
  
  def self.process(key)
    @@cache[key] ||= expensive_computation(key)
  end
end

# Fixed: bounded cache with LRU eviction
require 'lru_redux'
class DataProcessor
  @@cache = LruRedux::Cache.new(1000)
  
  def self.process(key)
    @@cache.getset(key) { expensive_computation(key) }
  end
end

Incorrect complexity analysis leads to choosing inappropriate algorithms for specific use cases. Hash operations appear constant-time but degrade with poor hash functions or high collision rates.

# Poor hash function causing O(n) performance
class BadHash
  def initialize
    @buckets = Array.new(10) { [] }
  end
  
  def store(key, value)
    # All keys hash to same bucket
    bucket_index = 0
    @buckets[bucket_index] << [key, value]
  end
  
  def retrieve(key)
    @buckets[0].find { |k, v| k == key }&.last
  end
end

Optimization without measurement often targets wrong bottlenecks. Code that appears slow may not impact overall performance if called infrequently.

# Measuring optimization impact
def benchmark_optimization
  original_time = Benchmark.realtime do
    1000.times { slow_method }
  end
  
  optimized_time = Benchmark.realtime do
    1000.times { fast_method }
  end
  
  improvement = (original_time - optimized_time) / original_time * 100
  puts "Optimization improved performance by #{improvement.round(2)}%"
end

Production Patterns

Production optimization requires balancing performance with maintainability, monitoring, and operational concerns. Cached computations must handle cache invalidation correctly to prevent serving stale data.

class ProductionCache
  def initialize(ttl: 3600)
    @cache = {}
    @ttl = ttl
  end
  
  def get(key, &block)
    entry = @cache[key]
    
    if entry && (Time.now - entry[:timestamp] < @ttl)
      entry[:value]
    else
      value = block.call
      @cache[key] = { value: value, timestamp: Time.now }
      cleanup_expired_entries
      value
    end
  end
  
  private
  
  def cleanup_expired_entries
    return unless @cache.size > 1000
    
    cutoff = Time.now - @ttl
    @cache.reject! { |_, entry| entry[:timestamp] < cutoff }
  end
end

Database query optimization often provides greater performance improvements than application-level algorithmic optimization. N+1 query problems cause exponential performance degradation as dataset size increases.

# N+1 query problem
def show_users_with_posts
  users = User.all
  users.each do |user|
    puts "#{user.name}: #{user.posts.count} posts"  # N queries
  end
end

# Optimized with includes
def show_users_with_posts_optimized
  users = User.includes(:posts)
  users.each do |user|
    puts "#{user.name}: #{user.posts.size} posts"  # 1 query
  end
end

Background processing moves expensive computations away from request threads, improving perceived performance. Queue-based architectures handle optimization asynchronously.

class OptimizationWorker
  include Sidekiq::Worker
  
  def perform(user_id, data_type)
    user = User.find(user_id)
    
    case data_type
    when 'analytics'
      result = compute_user_analytics(user)
      user.update(analytics_cache: result)
    when 'recommendations'
      recommendations = generate_recommendations(user)
      user.update(recommendations_cache: recommendations)
    end
  end
  
  private
  
  def compute_user_analytics(user)
    # Complex computation moved to background
    user.activities.group_by(&:date).transform_values(&:count)
  end
end

Monitoring optimization effectiveness in production requires metrics collection and alerting. Performance regressions often occur gradually and need systematic detection.

class PerformanceMonitor
  def self.track(operation_name)
    start_time = Time.now
    memory_before = get_memory_usage
    
    result = yield
    
    duration = Time.now - start_time
    memory_after = get_memory_usage
    memory_delta = memory_after - memory_before
    
    log_metrics(operation_name, duration, memory_delta)
    
    result
  end
  
  private
  
  def self.get_memory_usage
    GC.stat[:heap_allocated_pages] * GC::INTERNAL_CONSTANTS[:HEAP_PAGE_OBJ_LIMIT]
  end
  
  def self.log_metrics(operation, duration, memory_delta)
    Rails.logger.info({
      operation: operation,
      duration_ms: (duration * 1000).round(2),
      memory_delta_kb: (memory_delta / 1024.0).round(2),
      timestamp: Time.now.iso8601
    }.to_json)
  end
end

Reference

Core Optimization Methods

Complexity Reference

Memory Profiling Tools

Common Algorithm Patterns

Benchmarking Template

require 'benchmark'
require 'benchmark/ips'

# Basic timing
Benchmark.bm(20) do |x|
  x.report("method_name:") { method_call }
end

# Iterations per second
Benchmark.ips do |x|
  x.report("approach_1") { method_1 }
  x.report("approach_2") { method_2 }
  x.compare!
end

Performance Checklist

• Profile before optimizing
• Measure optimization impact
• Consider algorithmic complexity
• Choose appropriate data structures
• Cache expensive computations
• Use lazy evaluation for large datasets
• Avoid premature optimization
• Monitor production performance