search nearest to elements in array (hash)

M

Mateus ..

Hi!

I'm interesting, what is the best way to find nearest element in array
in comparison with "needle"?

Thank you!
 
S

serialhex

[Note: parts of this message were removed to make it a legal post.]

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
 
7

7stud --

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
 
M

Martin DeMello

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
 
M

Martin DeMello

data =3D [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]
needle =3D rand 10

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

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

You're sorting when all you want is the minimum

data =3D [1.1, 4.2, 3.1, 2.6, 6.1, 5.0]
needle =3D rand 10

min, mini =3D nil, 0

data.each_with_index do |num, i|
if (num - needle).abs < min
min =3D (num - needle).abs
mini =3D i
end
end

puts "nearest element is #{min} at index #{mini}"

martin
 
7

7stud --

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]
 
M

Mateus ..

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top