The Crystal Programming Language Forum

Min and max for multidimensional arrays

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

1 Like
arr.flatten.min
arr.flatten.max
1 Like

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
4 Likes

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
    • For example, at a previous company, we found the minimum of a set of heuristics (implemented as arrays) for a matchmaking algorithm
  • A single min_of will only work for 2-dimensional arrays — deeper nesting requires recursive calls

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

2 Likes

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
1 Like

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:

  • If you know the number of dimensions of your data already, the arr.min_of solution, used to the appropriate depth, will be the absolute fastest and will use no new memory.
  • If you don’t know the number of dimensions of your data…
    • And you care much more about speed than memory usage, the arr.flatten.min solution will probably be the one you want.
    • And you’re fairly concerned about memory usage, the arr.each.flatten.min solution ought to work well

Notes on the code and output:

  • I used 1D, 2D, and 3D arrays each totaling 1 million elements for the benchmarks; the array copy method might be worse as you increase the total number of elements, but I don’t know.
  • The benchmark columns are
name average_iterations_per_second (average_runtime) (percentage_variation_across_runs) memory_usage comparison_to_fastest
1 Like

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.

2 Likes