For your current code, the more Ruby-esque and functional way to write it would be:
def counts(numbers, maxima)
maxima.map do |max|
numbers.count { |n| n <= max }
end
end
Don't mess around with "manual" counting and array-appending when you don't have to.
As for general improvements:
Sort the numbers. If you sort them, you won't have to loop through the whole array, you just have to count up to the first case where the comparison returns false. Or you can use Array#bsearch_index
to find the "split point" in \$O(\log n)\$ time. Better yet, invert the condition and the index you find is also the count you want:
def counts(numbers, maxima)
sorted = numbers.sort
maxima.map do |max|
index = sorted.bsearch_index { |n| n > max } # note inverted condition
index || sorted.size
end
end
The above works because it's using #bsearch_index
in its "find minimum" mode (i.e. find the first index for which the block returns true
), but since the condition is flipped it'll find the first number that shouldn't be counted. And that number's index equals the count of the elements before it. E.g. using your example input, what happens is:
- The numbers get sorted
[2, 10, 5, 4, 8] => [1, 4, 5, 8, 10]
- For a given maximum, we do a binary search for the index
- If the maximum is, say, 7, we'll find index 3 (value 8), since that's the first place where
n > max
(i.e. 8 > 7
).
- And since indices are zero-based, 3 is also the total/count we want.
You can also sort the maxima array from high to low. Start with the highest maximum, and filter the numbers array to only include those that fit the n <= max
condition. The length of the filtered array is the first count. To find the next count, we only need to find a subset of the filtered array because a lower maximum will always result in a smaller array and a lower count. And so on for the next, smaller, maximum. It's a bit trickier, since you still need to output the totals in the original (unsorted) order.
def counts(numbers, maxima)
# create an array of [value, index] tuples, sorted (descending) by value
pairs = maxima.each_with_index.sort_by(&:first).reverse
result = pairs.each_with_object({numbers: numbers, counts: []}) do |(max, index), memo|
memo[:numbers].select! { |n| n <= max } # note in-place modification
memo[:counts] << [memo[:numbers].size, index]
end
# re-sort the counts so they match the original order
result[:counts].sort_by(&:last).map(&:first)
end
which could also be written as:
def counts(numbers, maxima)
pairs = maxima.each_with_index.sort_by(&:first).reverse
# create a copy, since we'll be modifying it
search_space = numbers.dup
counts = pairs.map do |max, index|
search_space.select! { |n| n <= max } # note in-place modification
[search_space.size, index]
end
counts.sort_by(&:last).map(&:first)
end
Or you can do everything: Sort both numbers and maxima, and use bsearch_index
to figure out where to split the numbers array instead of select!
. However, all that sorting and extra busywork might end up being slow.
def counts(numbers, maxima)
pairs = maxima.each_with_index.sort_by(&:first).reverse
search_space = numbers.sort
result = pairs.each_with_object({search_space: search_space, counts: []}) do |(max, index), memo|
count = memo[:search_space].bsearch_index { |n| n > max }
count ||= memo[:search_space].size
memo[:search_space].slice!(0, count)
memo[:counts] << [count, index]
end
result[:counts].sort_by(&:last).map(&:first)
end
And of course, you can memoize the total for a given maximum, so if you encounter the same maximum twice or more, you can just recall a known count without re-searching an array.