[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

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

trebor777

10/29/2007 8:20:00 PM


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.

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

Robert Klemme

10/29/2007 9:44:00 PM

0

On 29.10.2007 21:19, trebor777 wrote:
> 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

10/29/2007 10:52:00 PM

0

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
--
Posted via http://www.ruby-....

David A. Black

10/29/2007 10:54:00 PM

0

Stefan Rusterholz

10/29/2007 11:26:00 PM

0

Stefan Rusterholz 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
--
Posted via http://www.ruby-....

ara.t.howard

10/30/2007 1:47:00 AM

0


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

>
> 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://codeforp...
--
it is not enough to be compassionate. you must act.
h.h. the 14th dalai lama

trebor777

10/30/2007 2:19:00 AM

0




Ara.T.Howard-2 wrote:
>
>
> On Oct 29, 2007, at 2:19 PM, trebor777 wrote:
>
>>
>> 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://codeforp...
> --
> 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]]
--
View this message in context: http://www.nabble.com/find-the-closest-items-in-an-array-to-a-given-value.-tf4714369.html...
Sent from the ruby-talk mailing list archive at Nabble.com.

trebor777

10/30/2007 2:22:00 AM

0




Flávio Lisbôa wrote:
>
> 2007/10/29, trebor777 <mrobert@trebor777.net>:
>
>>
>> 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.
>>
>> --
>> View this message in context:
>> http://www.nabble.com/find-the-closest-items-in-an-array-to-a-given-value.-tf4714369.html...
>> 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!!
>
>

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

Peña, Botp

10/30/2007 3:19:00 AM

0

From: trebor777 [mailto:mrobert@trebor777.net]
# 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

ermac

10/30/2007 4:58:00 AM

0


trebor777 wrote:
> 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 --

10/30/2007 5:37:00 AM

0

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.

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