Find the closest items in an array to a given value

Ruby
1

Hi!

I’m searching for a light method for finding the closest items to a
given
value.

example/

1…10
in a range
i give, 5.5, return 5 and 6 for example…

as i’m working with arrays, containing numbers, but with no regular
step…
it will change i think.
example…

a = [ 1, 1.25, 2, 3, 3.5 ]

if i give 1.85, it gives me 1.25 and 2

It’s for a little music game, where player has to tap at the right
moment,
notes are register in a array, with the correct time, and as players
can’t
be accurate as a computer, i need some error margin. I working with
0.05
rounded values.

Also, if someone knows a good way to synchro Scrolling and Music with
tempo
value that would be great…
I mean, not the conversion to find how many frames between each beats.
but
how to convert, the number of frames between 2 beat to a distance in
pixel…? ( and possibly with a set-able speed) ?

Thanks.

2

On 29.10.2007 21:19, trebor777 wrote:

it will change i think.
example…

a = [ 1, 1.25, 2, 3, 3.5 ]

if i give 1.85, it gives me 1.25 and 2

It’s crucial to know whether your sequence of values is always sorted.
If it is, you can use #each_cons and return the pair where left is
less-or-equal than x and right is greater-than x.

If not, you can just iterate through the array and remember the last
match and its distance - overwrite when smaller distance.

robert

PS: A nice task for #inject. :slight_smile:

3

2007/10/29, trebor777 [email protected]:

i give, 5.5, return 5 and 6 for example…
It’s for a little music game, where player has to tap at the right moment,
pixel…? ( and possibly with a set-able speed) ?

Thanks.

–
View this message in context:
http://www.nabble.com/find-the-closest-items-in-an-array-to-a-given-value.-tf4714369.html#a13475984
Sent from the ruby-talk mailing list archive at Nabble.com.

Something like this? (Supposing the array may not be in order)

def array_between(a=[], v=0.0)
return [] if a.empty?
return [v, a.min] if v < a.min
return [a.max, v] if v > a.max
ret = []
ret.push a.find {|num| num < v}
ret.push a.find {|num| num > v}
ret.push v if ret.size < 2
return ret.sort
end

Just a quick 10-second sketch… Maybe you should have tried this too.
And i know you from other forums too! Nice to see you here trebor!!

4

Hi –

On Tue, 30 Oct 2007, Robert K. wrote:

PS: A nice task for #inject. :slight_smile:

Is that your .sig? :slight_smile:

David

5

trebor777 wrote:

Hi!

I’m searching for a light method for finding the closest items to a
given
value.

[1,2,3,4,5,6].min {Â |a,b| (a-value).abs <=> (b-value).abs }

Regards
Stefan

6

Stefan R. wrote:

trebor777 wrote:

Hi!

I’m searching for a light method for finding the closest items to a
given
value.

[1,2,3,4,5,6].min {Â |a,b| (a-value).abs <=> (b-value).abs }

Regards
Stefan

Since you want more than 1 you can either implement your own min method
that returns the 2 smallest ones, that’d happen in O(n), or you can sort
by the distance, which is O(nlogn):
ary.sort_by { |item| (value-item).abs }.first(n)
If you just want all values that are a max difference of x from y, you
can use:
ary.select { |item| item - x <= y }

Regards
Stefan

7

It’s crucial to know whether your sequence of values is
always sorted.

arr = […]
sorted_arr = arr.sort

PS: A nice task for #inject. :slight_smile:

Unfortunately, from tests I have done in other threads, it appears that
inject is not very efficient, i.e. it’s slow.

Flávio Lisbôa wrote:

def array_between(a=[], v=0.0)
return [] if a.empty?
return [v, a.min] if v < a.min
return [a.max, v] if v > a.max
ret = []
ret.push a.find {|num| num < v}
ret.push a.find {|num| num > v}
ret.push v if ret.size < 2
return ret.sort
end

Just a quick 10-second sketch… Maybe you should have tried this too.
And i know you from other forums too! Nice to see you here trebor!!

That doesn’t work:

a = [1.1, 1.3, 1.4, 2, 2.2, 3]
target = 1.85
p array_between(a, target)

–output:–
[1.1, 2]

detect returns the first value for which block isn’t false, which will
be the first value in the array that is less than the given number. The
op wants the biggest number in that array that is less than the given
number, which could be the last number in the array.

[1,2,3,4,5,6].min { |a,b| (a-value).abs <=> (b-value).abs }

That doesn’t work. It returns only the closest single value.

ary.sort_by { |item| (value-item).abs }.first(n)

That doesn’t work either. It returns the two closes values, which means
that both returned values could be less than or greater than the given
number. The op wants the two closest number that is lower than the
given number and the closest number that is higher than the given
number.

The following are two solutions that appear to do what the op wants.
The first one stores the closest lower value and the closest higher
value in two variables as it steps through the array:

a = [ 1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]
target = 1.85

closest_lower = nil
closest_higher = nil

a.each do |elmt|
if elmt < target
if !closest_lower or elmt > closest_lower
closest_lower = elmt
end

elsif elmt > target
if !closest_higher or elmt < closest_higher
closest_higher = elmt
end

else #if elmt == target
#do something
end
end

Surprisingly, this is slightly faster–even for very large arrays:

target = 1.85

less_than = []
greater_than = []

a.each do |elmt|
if elmt < target
less_than << elmt

elsif elmt > target
greater_than << elmt
end
end

puts less_than.max
puts greater_than.min

8

Ara.T.Howard-2 wrote:

rounded values.

[“b”, “c”, “c”]
[“c”, “c”, “d”]

a @ http://codeforpeople.com/

it is not enough to be compassionate. you must act.
h.h. the 14th dalai lama

While waiting for solutions, i did something really similar.

a = myhash.keys.sort[value-0.05…value+0.05]

then i just use

myhash[a[x]]

9

Flávio Lisbôa wrote:

Also, if someone knows a good way to synchro Scrolling and Music with

return [a.max, v] if v > a.max

Well must be RMXP.org… isn’t it?
(although it’s been a while i’ve been there)
I use the same username everywhere i go on the net… xD

10

From: trebor777 [mailto:[email protected]]

a = myhash.keys.sort[value-0.05…value+0.05]

then i just use

myhash[a[x]]

can you test without hash?

~> a
=> [1, 1.25, 1.9, 2, 3, 3.5]
~> val
=> 1.85
~> a[val-0.5…val+0.5]
=> [1.25, 1.9]
~> a.slice (val-0.5…val+0.5)
=> [1.25, 1.9]

kind regards -botp

11

On Oct 29, 2007, at 2:19 PM, trebor777 wrote:

in a range

It’s for a little music game, where player has to tap at the right
moment,
notes are register in a array, with the correct time, and as
players can’t
be accurate as a computer, i need some error margin. I working
with 0.05
rounded values.

install rbtree - it has upper_bound and lower_bound methods that do
just this - otherwise you can do something like this:

cfp:~ > cat a.rb
require ‘alib’

Array.send :include, alib.bsearch

list = %w( a b c c c d e f )
index = list.bsearch_first {|x| x <=> “c”}
p list[index - 1 … index + 1]

list = %w( a b c c c d e f )
index = list.bsearch_last {|x| x <=> “c”}
p list[index - 1 … index + 1]

cfp:~ > ruby a.rb
[“b”, “c”, “c”]
[“c”, “c”, “d”]

a @ http://codeforpeople.com/

12

trebor777 wrote:

as i’m working with arrays, containing numbers, but with no regular step…
it will change i think.
example…

a = [ 1, 1.25, 2, 3, 3.5 ]

if i give 1.85, it gives me 1.25 and 2

Of course there are many ways. Here’s one. Add your target value to
the array and sort, then return the values before and after it in
sequence.

Note that this code ‘wraps’ the values in the array – a target value
lower than the lowest value in the array, or higher than the highest
value, will return the starting and ending values.

#!/usr/bin/ruby -w

a is array of values, x is target value

def nearest(a,x)
tmp = a.sort
tmp << x
tmp.sort!
i = tmp.index x
[tmp[i-1], tmp[i+1]]
end

a = [ 1, 1.25, 2, 3, 3.5 ]
x = ARGV.shift.to_i

a,b = nearest(a,x)
puts “%0.2f => %0.2f,%0.2f” % [x, a, b]

13

On Behalf Of 7stud --:

a = [ 1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]

target = 1.85

closest_lower = nil

closest_higher = nil

a.each do |elmt|

if elmt < target

if !closest_lower or elmt > closest_lower

closest_lower = elmt

end

elsif elmt > target

if !closest_higher or elmt < closest_higher

closest_higher = elmt

end

else #if elmt == target

#do something

end

end

Surprisingly, this is slightly faster–even for very large arrays:

target = 1.85

less_than = []

greater_than = []

a.each do |elmt|

if elmt < target

less_than << elmt

elsif elmt > target

greater_than << elmt

end

end

puts less_than.max

puts greater_than.min

cool and straightforward. works in unordered list.

have you tried #partition?

~> a
=> [1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]
~> [(parts=a.partition{|i| i<=1.85}).first.max,parts.last.min]
=> [1.5, 1.9]

in 1.9, there is already group_by, so
~> [(parts=a.group_by{|e| e<=1.85}.values).last.max,parts.first.min]
=> [1.5, 1.9]

…but we may be working too hard if lists is ordered though. and for
ordered lists, a binary search like what ara posted should be the
fastest.

kind regards -botp

14

Peña, Botp wrote:

have you tried #partition?

~> a
=> [1.25, 1, 3, 1.9, 1.95, 2.1, 2.2, 1.5]
~> [(parts=a.partition{|i| i<=1.85}).first.max,parts.last.min]
=> [1.5, 1.9]

No, I haven’t. Thanks for pointing the partition method out to me.

I must have been testing my first method on a different, longer array
because now it runs slightly faster than my second method, as well as
the partition solution, which makes more sense to me. Here are the
results I get:

test1 exec time(1,000,000 loops): 10.348911 total
test2 exec time(1,000,000 loops): 13.916226 total
test4 exec time(1,000,000 loops): 12.912649 total

where test4 is this code:

a = [ 1.25, 1, 3, 2, 3.5, 4.25, 0.65, 1.5, 7.7, 9.2]
target = 1.85

arr = a.partition do |elmt|
elmt < target
end

closest_lower = arr[0].max
closest_higher = arr[1].min
end

But they are all pretty much equivalent. inject() is so slow, I just
hit ctrl-c after what seems like 5 minutes.

15

ignore that post.
what was i thinking, … again? :))

kind regards -botp

-----Original Message-----

From: Peña, Botp [mailto:[email protected]]

Sent: Tuesday, October 30, 2007 11:19 AM

To: ruby-talk ML

Subject: Re: find the closest items in an array to a given value.

From: trebor777 [mailto:[email protected]]

# a = myhash.keys.sort[value-0.05…value+0.05]

# then i just use

# myhash[a[x]]

can you test without hash?

~> a

=> [1, 1.25, 1.9, 2, 3, 3.5]

~> val

=> 1.85

~> a[val-0.5…val+0.5]

=> [1.25, 1.9]

~> a.slice (val-0.5…val+0.5)

=> [1.25, 1.9]

kind regards -botp

16

2007/10/29, David A. Black [email protected]:

Hi –

On Tue, 30 Oct 2007, Robert K. wrote:

PS: A nice task for #inject. :slight_smile:

Is that your .sig? :slight_smile:

Not until now. Thanks for the inspiration!

Cheers

robert