CODEWITHSUNDEEP
rubyalgorithmruby-on-rails-4
Edward Leon Jasper
Edward Leon Jasper

Reputation: 61

Find closest numbers in array to given value

I'm looking to create a method that will return to me the 5 closest numbers in an array. Here is what I have to get me started. I'm looking to compare differences but I feel there has to be a simpler way . 

def get_suggested_items
    @suggested_items = []
    new_price = self.price
    products = Product.all
    products.each do |product, difference|
        price = product.price
        old_difference = new_price - product.price
        difference = (new_price - product.price).abs
        while difference < old_difference 
            @suggested_items << product
        end

end

I'm looking to have returned the array @suggested_items with the 5 closest products by the price

Upvotes: 0

Views: 2940

Answers (2)

Cary Swoveland
Cary Swoveland

Reputation: 110675

Suppose arr is a sorted array of integers. (If it's not sorted, then sort as the first step.) I assume you want to find a sequence of five elements from the array, a = arr[i,5], such that a.last-a.first is minimum for all i, 0 <= i <= arr.size-4. If that's correct, then it's simply:

start_index = (arr.size-4).times.min_by { |i| arr[i+4]-arr[i] }

Suppose

arr = [1, 2, 4, 5, 8, 9, 11, 12, 13, 15, 17, 19, 23, 24, 24, 25, 30]
start_index = (arr.size-4).times.min_by { |i| arr[i+4]-arr[i] }
  #=> 4

So the "closest" five numbers would be:

arr[4,5]
  #=> [8, 9, 11, 12, 13]

Upvotes: 1

Todd Agulnick
Todd Agulnick

Reputation: 1995

SQL was designed for this sort of thing. Add the following class method to your Product model:

class Product < ActiveRecord::Base

  def self.with_price_nearest_to(price)
    order("abs(products.price - #{price})")
  end
end

Then you can write:

Product.with_price_nearest_to(3.99).limit(5)

There is a distinct performance advantage to this approach over what you outlined in your question. In this case, the database does the calculation and sorting for you and returns to ActiveRecord only the 5 products that you need. When you do Product.all or even Product.each you're forcing ActiveRecord to instantiate a model for every row in your table, which gets expensive as the table gets larger.

Note that this approach still requires a full table scan; if you want to improve the performance further, you can add an index to price column on the products table.

Upvotes: 4

Related Questions