Hi there,
I have a Array like this:
arr = Array.new(3) {Array.new(2) {0}}
arr[0][1] = 42
arr[1][0] = 33
arr # => [[0, 42], [33, 0], [0, 0]]
How can I use min and max on this array?
I want to know what the highest value is in all dimensions.
Thanks.
Bob
arr.flatten.min
arr.flatten.max
Thanks a lot!
That works but it’s inefficient because flatten will create a temporary array.
Here’s a better way:
arr.min_of &.min
arr.max_of &.max
Candidate for min method?
class Array(T)
def min
{{ if T.respond_to(:each) }} # Or check for Enumerable?
min_of &.min
{{ else }}
# Normal min
{{ end }}
Pro: Works with any depth Array.
Con: ?
@Didactic.Drunk I can think of a couple cons:
Array includes Comparable, so arrays are a perfectly legit value for finding a min/max
min_of will only work for 2-dimensional arrays — deeper nesting requires recursive callsIf there were a brand-new method for it and it called itself recursively (like dig does), it might be pretty interesting, but it would probably be worth understanding the use cases a bit more in case it’s not broadly useful.
With 2 dimension they work both.
flatten works fine on 3 dimensions, too.
but this do not
arr.min_of &.min
arr.max_of &.max
Even I do not understand the syntax &.min
Is there some explanation?
It’s a bit of shorthand that can be pretty obscure if you’re not familiar with Ruby, but it’s honestly really great. Consider the following code:
array = [
[1, 2, 3],
[4, 5, 6],
]
array.min_of { |nested_array| nested_array.min }
That last line of code is equivalent to array.min_of(&.min). When you are simply calling a method on the value passed to the block, you can omit the explicit block and its block variables and replace it with &.method_to_call.
So, for example, these two are the exact same:
foo { |x| x.bar }
foo(&.bar)
It comes from a similar concept in Ruby (originally introduced in Rails), where the & method was defined on instances of Symbol to do the same thing:
foo(&:bar)
Crystal’s implementation is more powerful, though, since it allows passing arguments to the called method and even allows method chaining. Ruby’s implementation only allows it for the most trivial call: single method called on the block argument, no arguments, no chaining.
It’s really slick for things like this:
subtotal = cart_items
.select(&.available?)
.map(&.price)
.sum
I’ve done a quick benchmark using the standard library Benchmark module, and these are my results:
Benchmarking 1D array min
Array#min 834.72 ( 1.20ms) (± 0.64%) 0.0B/op fastest
recursive_min_flatten 325.35 ( 3.07ms) (± 1.92%) 12.0MB/op 2.57× slower
recursive_min_iterator 141.90 ( 7.05ms) (± 1.11%) 130B/op 5.88× slower
---
Benchmarking 2D array min
Array#min_of(&.min) 794.68 ( 1.26ms) (± 2.13%) 0.0B/op fastest
recursive_min_flatten 272.01 ( 3.68ms) (± 3.28%) 12.0MB/op 2.92× slower
recursive_min_iterator 151.35 ( 6.61ms) (± 0.60%) 56.1kB/op 5.25× slower
---
Benchmarking 3D array min
Array#min_of(&.min_of(&.min)) 625.27 ( 1.60ms) (± 1.57%) 0.0B/op fastest
recursive_min_flatten 270.10 ( 3.70ms) (± 0.55%) 12.0MB/op 2.31× slower
recursive_min_iterator 132.91 ( 7.52ms) (± 1.99%) 509kB/op 4.70× slower
code, compiled with --release
Assuming I’ve done my coding correctly (if you’re not careful, the compiler will optimize the code too much in a benchmark block and you’ll get invalid results), your best option varies:
arr.min_of solution, used to the appropriate depth, will be the absolute fastest and will use no new memory.arr.flatten.min solution will probably be the one you want.arr.each.flatten.min solution ought to work wellNotes on the code and output:
name average_iterations_per_second (average_runtime) (percentage_variation_across_runs) memory_usage comparison_to_fastest
Nice benchmark write-up. It’s also interesting that the ‘B/opp’ for ‘recursive_min_iterator’ is between the two but increases as the dimensions increase… and of course will vary depending on specific use case.
I’ve found an ideal solution for arrays in an unknown number of dimensions! It’s as fast as the #min/#min_of solution for each dimension I benchmarked and allocates no new memory. The only downside is that there’s more code:
def paired_recursive_min(arr : Array(Array))
arr.min_of { |internal_arr| paired_recursive_min internal_arr }
end
def paired_recursive_min(arr : Array)
arr.min
end
It’s pretty simple to read, though. It’s essentially the same as a recursive method where we check each time whether our array contains arrays, except that by making it two methods the type system handles it for us.
Here are my new benchmarks (the rest of the code is the same, just with the new methods defined and added to the benchmarks):
Benchmarking 1D array min
Array#min 556.10 ( 1.80ms) (± 2.51%) 0.0B/op 1.01× slower
recursive_min_flatten 279.08 ( 3.58ms) (± 3.67%) 12.0MB/op 2.02× slower
recursive_min_iterator 141.01 ( 7.09ms) (± 0.65%) 129B/op 4.00× slower
paired_recursive_min 564.05 ( 1.77ms) (± 1.43%) 0.0B/op fastest
---
Benchmarking 2D array min
Array#min_of(&.min) 799.79 ( 1.25ms) (± 1.04%) 0.0B/op fastest
recursive_min_flatten 247.37 ( 4.04ms) (± 1.05%) 12.0MB/op 3.23× slower
recursive_min_iterator 151.20 ( 6.61ms) (± 0.94%) 56.1kB/op 5.29× slower
paired_recursive_min 776.60 ( 1.29ms) (± 3.81%) 0.0B/op 1.03× slower
---
Benchmarking 3D array min
Array#min_of(&.min_of(&.min)) 585.47 ( 1.71ms) (± 5.17%) 0.0B/op 1.06× slower
recursive_min_flatten 237.42 ( 4.21ms) (± 5.30%) 12.0MB/op 2.62× slower
recursive_min_iterator 126.27 ( 7.92ms) (± 2.88%) 509kB/op 4.92× slower
paired_recursive_min 621.22 ( 1.61ms) (± 2.82%) 0.0B/op fastest
I can put the new code somewhere if anyone is interested, but I figure this provides enough info for reference.