Search nearest to elements in array (hash)

Ruby
1

Hi!

I’m interesting, what is the best way to find nearest element in array
in comparison with “needle”?

Thank you!

2

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 (
Hamming distance - Wikipedia) which would be [“foo”,
“needle”, “bar”, “baz”, “feedle”] and “needle” & “feedle” being nearest
(because they have a hamming distance of 0 & 1 respectively).
hex

3

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

4

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

5

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 10

arr = data.map do |num|
[(num - needle).abs, num]
end

sorted = 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

6

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.

7

7stud – wrote in post #998723:

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

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]