Hi!

I’m interesting, what is the best way to find nearest element in array

in comparison with “needle”?

Thank you!

Hi!

I’m interesting, what is the best way to find nearest element in array

in comparison with “needle”?

Thank you!

On Sat, May 14, 2011 at 5:05 PM, Mateus … [email protected] wrote:

Hi!

I’m interesting, what is the best way to find nearest element in array

in comparison with “needle”?Thank you!

hi, ok, i’m not sure i understand the question. are you asking for the

‘nearest’ as in [“foo”, “needle”, “bar”, “baz”] with “foo” & “bar” being

the

nearest, or something like a hamming distance (

http://en.wikipedia.org/wiki/Hamming_distance) which would be [“foo”,

“needle”, “bar”, “baz”, “feedle”] and “needle” & “feedle” being nearest

(because they have a hamming distance of 0 & 1 respectively).

hex

data = [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]

needle = rand 10

arr = data.map do |num|

[(num - needle).abs, num]

end

sorted = arr.sort_by {|sub_arr| sub_arr[0]}

puts needle

puts sorted.first[1]

–output:–

2

2.6

On Sun, May 15, 2011 at 2:35 AM, Mateus … [email protected] wrote:

Hi!

I’m interesting, what is the best way to find nearest element in array

in comparison with “needle”?

Depends - if there’s a comparison function, and your array is sorted

on it, then just do a binary search. If not, there’s nothing better

than a linear search, calculating the distance between each element

and the needle.

martin

On Sun, May 15, 2011 at 2:58 AM, 7stud – [email protected]

wrote:

data = [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]

needle = rand 10arr = data.map do |num|

[(num - needle).abs, num]

endsorted = arr.sort_by {|sub_arr| sub_arr[0]}

You’re sorting when all you want is the minimum

data = [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]

needle = rand 10

min, mini = nil, 0

data.each_with_index do |num, i|

if (num - needle).abs < min

min = (num - needle).abs

mini = i

end

end

puts “nearest element is #{min} at index #{mini}”

martin

thank you guys!

i really appreciate this.

i’m sorry if my question wasn’t understandable. main reason for this

purpose is consistent hashing, where we need to find for example next

bigger key in array comparing to the “needle”.

i haven’t tested yet your solutions but i will.

hope this topic helps for someone in future.

i’m also googled and find this:

https://github.com/superfeedr/consistent_hashr/blob/master/lib/consistent_hashr.rb

but i’m not sure that this is efficient way of doing things if we have

for example 10k elements in array.

for now, i think best way is making some binary search to reduce pool

(array) and then make some sort|loop|etc.

7stud – wrote in post #998723:

data = [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]

needle = rand 10arr = data.map do |num|

[(num - needle).abs, num]

endsorted = arr.sort_by {|sub_arr| sub_arr[0]}

puts needle

puts sorted.first[1]–output:–

2

2.6

And…if you want a ranking of the differences, add one more map():

data = [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]

needle = rand 10

arr = data.map do |num|

[(num - needle).abs, num]

end

sorted = arr.sort_by {|sub_arr| sub_arr[0]}

rankings = sorted.map {|sub_arr| sub_arr[1]}

puts needle

p sorted

puts sorted.first[1]

p rankings

–output:–

2

[[0.6000000000000001, 2.6], [0.8999999999999999, 1.1], [1.1, 3.1], [2.2,

4.2], [3.0, 5.0], [4.1, 6.1]]

2.6

[2.6, 1.1, 3.1, 4.2, 5.0, 6.1]

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs