optimize this ruby code

Question

So this code will count the total number of pairs of numbers whose difference is K. it is naive method and I need to optimize it. suggestions?

test = $stdin.readlines 

input = test[0].split(" ")

numbers = test[1].split(" ")

N = input[0]
K = input[1]

count = 0

for i in numbers
   current = i.to_i
   numbers.shift
   for j in numbers
       difference = (j.to_i - current).abs
       if (difference == K)
           count += 1
       end
   end
end

puts count

Is N even useful? If there is another part of the code we can't see, could you remove the parts we don't need? XD — JMichelB
– JMichelB, Commented Aug 8, 2011 at 18:49
numbers.shift, doesn't it make the loops innacurate? If you have [1,2,3,4], wouldn't i take only 1 and 3 as values? — JMichelB
– JMichelB, Commented Aug 8, 2011 at 19:08
Can you try running this small script? arr = [1,2,3,4,5,6] for i in arr puts i arr.shift end — JMichelB
– JMichelB, Commented Aug 8, 2011 at 19:52

Joshua Cheek · Accepted Answer · 2011-08-08 21:08:11Z

4

Would have been nice for you to give some examples of input and output, but I think this is correct.

require 'set'

def count_diff(numbers, difference)
  set = Set.new numbers
  set.inject 0 do |count, num|
    set.include?(num+difference) ? count+1 : count
  end
end


difference  =  gets.split[1].to_i
numbers     =  gets.split.map { |num| num.to_i }

puts count_diff(numbers, difference)

answered Aug 8, 2011 at 21:08

Joshua Cheek

32.1k18 gold badges80 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

hugomg · Accepted Answer · 2011-08-08 18:56:53Z

3

Untested, hopefully actual Ruby code

Documentation for Set: http://www.ruby-doc.org/stdlib/libdoc/set/rdoc/classes/Set.html

require 'set'
numbers_set = Set.new
npairs = 0

numbers.each do |number|
     if numbers_set.include?(number + K)
         npairs += 1
     end
     if numbers_set.include?(number - K)
         npairs += 1
     end
     numbers_set.add(number)
end

edited Aug 8, 2011 at 18:56

answered Aug 8, 2011 at 18:41

hugomg

70.4k30 gold badges168 silver badges257 bronze badges

Comments

JMichelB · Accepted Answer · 2011-08-08 19:04:06Z

1

Someone deleted his post, or his post was deleted... He had the best solution, here it is :

test = $stdin.readlines
input = test[0].split(" ")
numbers = test[1].split(" ")
K = input[1]
count = 0
numbers.combination(2){|couple| couple.inject(:-).abs == K ? count++}
puts count

You don't even need N.

answered Aug 8, 2011 at 19:04

JMichelB

4753 silver badges8 bronze badges

2 Comments

Evan Over a year ago

this was slower then mine thats why he delete it

JMichelB Over a year ago

If I am right about the lost data (mentioned in comments of the question), then you are running at least two times too fast.

tskuzzy · Accepted Answer · 2011-08-08 18:42:17Z

0

I do not know Ruby so I'll just give you the big idea:

Get the list
Keep a boolean array (call it arr), marking off numbers as true if the number exists in the list
Loop through the list and see if arr[num-K] and/or arr[num+K] is true where num is a number in your list

This uses up quite a bit of memory though so another method is to do the following:

Keep a hash map from an integer n to an integer count
Go through your list, adding num+K and num-K to the hash map, incrementing count accordingly
Go through your list and see if num is in the hash map. If it is, increment your counter by count

answered Aug 8, 2011 at 18:42

tskuzzy

36.6k15 gold badges78 silver badges145 bronze badges

Collectives™ on Stack Overflow

optimize this ruby code

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related