Jesús Gabriel y Galán
10/3/2007 12:35:00 PM
On 10/3/07, FireAphis <FireAphis@gmail.com> wrote:
> > > I have a very big array of objects sorted by one of its numeric data
> > > members. During the flow of my application I need occasionally to get
> > > all the elements in a specific range.
> Sorry if my explanation has been misleading. The array isn't
> necessarily comprised of continuous or consecutive numbers. Moreover
> they don't necessarily start from zero. For example:
>
> my_array = [-100, -99, -2, 0, 3, 125, 1742, 1234568763]
>
> now I want to get all the elements bigger than 1 and smaller than
> 1000. AFAIK my_array[1..1000] doesn't help in this case.
Here is my try:
class Array
# assumes a sorted array whose elements respond appropriately to <=>
def subrange(lower, higher)
low = find_index_lower(lower)
high = find_index_higher(higher)
if (low >= length) || (high < 0)
[]
else
self[low..high]
end
end
# Finds the lowest index whose value is greater than the specified parameter
# If all values in the array are lower, returns the index after the last one
# If all values are higher, returns 0
def find_index_lower(lower)
return length if ((last <=> lower) == -1)
return 0 if ((first <=> lower) == 1)
low = 0
high = self.length - 1
while low < high
index = low + (high - low) / 2
element = self[index]
test = element <=> lower
case test
when 0:
return index + 1
when -1:
return (index + 1) if ((self[index+1] <=> lower) == 1)
low = index + 1
when 1:
return (index) if ((self[index-1] <=> lower) <= 0)
high = index - 1
end
end
end
# Finds the highest index whose value is lower than the specified parameter
# If all values in the array are higher, returns -1
# If all values are lower, returns length-1
def find_index_higher(higher)
return -1 if ((first <=> higher) >= 0)
return length - 1 if ((last <=> higher) == -1)
low = 0
high = self.length - 1
while low < high
index = low + (high - low) / 2
element = self[index]
test = element <=> higher
case test
when 0:
return index - 1
when -1:
return (index) if ((self[index+1] <=> higher) >= 0)
low = index + 1
when 1:
return (index - 1) if ((self[index-1] <=> higher) == -1)
high = index - 1
end
end
end
end
a = [5, 6, 7, 8, 9, 10, 14]
p a
puts "6 - 13: #{a.subrange(6,13).inspect}"
puts "5 - 15: #{a.subrange(5,15).inspect}"
puts "5 - 100: #{a.subrange(5, 100).inspect}"
puts "2 - 100: #{a.subrange(2, 100).inspect}"
puts "-1 - 100: #{a.subrange(-1, 100).inspect}"
puts "100 - 150: #{a.subrange(100,150).inspect}"
puts "1 - 2: #{a.subrange(1,2).inspect}"
require 'benchmark'
n = 10_000
Benchmark.bmbm do |x|
x.report("Array subrange") {
n.times {a.subrange(6,13)}
}
end
-----------------------------------------------------------
$ ruby array_subrange.rb
[5, 6, 7, 8, 9, 10, 14]
6 - 13: [7, 8, 9, 10]
5 - 15: [6, 7, 8, 9, 10, 14]
5 - 100: [6, 7, 8, 9, 10, 14]
2 - 100: [5, 6, 7, 8, 9, 10, 14]
-1 - 100: [5, 6, 7, 8, 9, 10, 14]
100 - 150: []
1 - 2: []
Rehearsal --------------------------------------------------
Array subrange 0.220000 0.020000 0.240000 ( 0.274937)
----------------------------------------- total: 0.240000sec
user system total real
Array subrange 0.190000 0.010000 0.200000 ( 0.227276)
Jesus.