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

[trebor777]

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.

 

[Robert Klemme]

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 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.

 

[Stefan Rusterholz]

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

 

[David A. Black]

Hi --

PS: A nice task for #inject.

Is that your .sig?


David

--
Upcoming training by David A. Black/Ruby Power and Light, LLC:
* Advancing With Rails, Edison, NJ, November 6-9
* Advancing With Rails, Berlin, Germany, November 19-22
* Intro to Rails, London, UK, December 3-6 (by Skills Matter)
See http://www.rubypal.com for details!

 

[Stefan Rusterholz]

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

 

[ara.t.howard]

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.

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/

 

[trebor777]

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.

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/

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

 

[trebor777]

=20

Hi!

I'm searching for a light method for finding the closest items to a give= n
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 =3D [ 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.0= 5
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.

=20
=20
Something like this? (Supposing the array may not be in order)
=20
def array_between(a=3D[], v=3D0.0)
return [] if a.empty?
return [v, a.min] if v < a.min
return [a.max, v] if v > a.max
ret =3D []
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
=20
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!!
=20
=20

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
--=20
View this message in context: http://www.nabble.com/find-the-closest-items-=
in-an-array-to-a-given-value.-tf4714369.html#a13481371
Sent from the ruby-talk mailing list archive at Nabble.com.

 

[Peña, Botp]

From: trebor777 [mailto:[email protected]]=20
# a =3D myhash.keys.sort[value-0.05..value+0.05]
# then i just use=20
# myhash[a[x]]

can you test without hash?

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

kind regards -botp

 

[ermac]

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

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]

 

[7stud --]

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.

 

[Peña, Botp]

ignore that post.
what was i thinking, .. again? )=20

kind regards -botp


# -----Original Message-----
# From: Pe=F1a, Botp [mailto:[email protected]]=20
# 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.
#=20
# From: trebor777 [mailto:[email protected]]=20
# # a =3D myhash.keys.sort[value-0.05..value+0.05]
# # then i just use=20
# # myhash[a[x]]
#=20
# can you test without hash?
#=20
# ~> a
# =3D> [1, 1.25, 1.9, 2, 3, 3.5]
# ~> val
# =3D> 1.85
# ~> a[val-0.5..val+0.5]
# =3D> [1.25, 1.9]
# ~> a.slice (val-0.5..val+0.5)
# =3D> [1.25, 1.9]
#=20
# kind regards -botp
#=20
#=20

 

[Robert Klemme]

Hi --



Is that your .sig?

Not until now. Thanks for the inspiration!

Cheers

robert