Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.ruby > #4545 > unrolled thread

search nearest to elements in array (hash)

Back to article view | Back to comp.lang.ruby

Contents

  search nearest to elements in array (hash) "Mateus .." <excanoe@gmail.com> - 2011-05-14 16:05 -0500
    Re: search nearest to elements in array (hash) serialhex <serialhex@gmail.com> - 2011-05-14 16:21 -0500
    Re: search nearest to elements in array (hash) 7stud -- <bbxx789_05ss@yahoo.com> - 2011-05-14 16:28 -0500
      Re: search nearest to elements in array (hash) Martin DeMello <martindemello@gmail.com> - 2011-05-14 16:33 -0500
      Re: search nearest to elements in array (hash) 7stud -- <bbxx789_05ss@yahoo.com> - 2011-05-14 16:36 -0500
    Re: search nearest to elements in array (hash) Martin DeMello <martindemello@gmail.com> - 2011-05-14 16:30 -0500
    Re: search nearest to elements in array (hash) "Mateus .." <excanoe@gmail.com> - 2011-05-15 01:33 -0500

#4545 — search nearest to elements in array (hash)

Hi!

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

Thank you!

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [next] | [standalone]

#4546

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

On Sat, May 14, 2011 at 5:05 PM, Mateus .. <excanoe@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#4547

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

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [prev] | [next] | [standalone]

#4549

On Sun, May 15, 2011 at 2:58 AM, 7stud -- <bbxx789_05ss@yahoo.com> 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

[toc] | [prev] | [next] | [standalone]

#4550

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]

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [prev] | [next] | [standalone]

#4548

On Sun, May 15, 2011 at 2:35 AM, Mateus .. <excanoe@gmail.com> 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

[toc] | [prev] | [next] | [standalone]

#4556

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.

-- 
Posted via http://www.ruby-forum.com/.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.ruby

csiph-web