Difference between array elements

Help & Support
1

I have an array of integers.
I want to create an array of the differences (gaps) between the elements.
I then want to find the max of those differences (gaps).

If n is the array of integers, I can do either of these in Ruby.

n.each_cons(2).map{ |a,b| b-a }.max

n.map.with_index(1){|e,i| a[i]-e if a[i] }.compact.max

In Crystal, I get these error message for each case.

Error: wrong number of block arguments (given 2, expected 1)

Error: 'Array(Int32)#map' is expected to be invoked with a block, but no block was given

Seems like map in Crystal is not the same as in Ruby.

How do I do this correctly in Crystal?

2

Hello @jzakiya!

Would something like this work?

new_max = n.each_cons(2).map{ |b| b[1] - b[0] }.max

Someone can explain it better for you, however, I think it’s because each_cons is returning Array(Int32). This is being passed into map. Map applies the given block to the return value. Which in your case is an Array(Int32). map also accepts one block argument, you are giving it 2 (|a,b|).

Thus, you can get the difference by doing b[1] - b[0]

3

Ruby will automatically unpack arrays when passing multiple block arguments. The same is not true for Crystal (it’s only true for tuples because the compiler knows their size at compile time). You can, however, do: |(a, b)| to unpack the elements.

1 Like
4

Thanks @asterite, I keep forgetting about needing the parentheses inside the | |.
This now works for the first case:

n.each_cons(2).map{ |(a,b)| b-a }.max

But the 2nd case still gives an error.

y.map_with_index(1){|e,i| y[i]-e if y[i] }.compact.max
                                     ^-------------
Error: wrong number of arguments for 'Array(Int32)#map_with_index' (given 1, expected 0)

This compiles, but gives an incorrect answer of 0.

y.map_with_index {|e,i| y[i]-e if y[i] }.compact.max
5

maybe map_with_index doesn’t have regular arguments?

6

As @asterite said, Array#map_with_index (docs) doesn’t take any arguments except a block. Both methods below will work:

n = [1, 3, 5, 9, 27]

pp n.each_cons(2).map{ |(a, b)| b - a }.max

pp n.map_with_index {|element, index| n[index + 1] - element if n[index + 1]? }.compact.max

Output:

18
18

(Try it here)

I admittedly took the liberty of interpreting your intent and modifying code in the second approach a little.

7

We should probably add an offset = 0 argument to map_with_index to match that of each_with_index.

8

Thanks to both for the answers. :relaxed:

Why the ? in ...if n[index + 1]?``

9

I just sent an improvement for map_with_index: Add `offset` argument to all `map_with_index` methods by asterite · Pull Request #8264 · crystal-lang/crystal · GitHub

Why the ? in ... if n[index + 1]?`

with [] and index out of bounds raises an exception, with []? it returns nil

10

Thanks again for the answer, and the commit.

As a user, it would be nice to have a method to optimally find array element differences (gaps).
This comes up frequently in statistics, data analysis, number theory, etc, finding the data element gaps.

arry.diffs  or ary.gaps  => [array of all gaps]

Then a user can easily do gap analysis to find the number of different gap sizes as such:

ary.gaps.count(3), etc and ary.gaps.(min|max)

For the task at hand, an optimized max|min gap method wouldn’t create a gaps array, but directly step through the data elements computing gaps and just save the min|max as it goes (saving mem|time). Or create one method that returns both the min|max gaps, to reduce the number of methods.

ary.max_gap  and ary.min_gap

or

ary.min_max_gaps => {min gap, max gap}

a, b = ary.min_max_gaps for both
a, _ = ary.min_max_gaps for min
_, b = ary.min_max_gaps for max

I realize you’re trying to reduce method bloat, but methods like these would make Crystal more attractive (easy and performant) to replace Python and R for certain task in statistics, data analysis, etc.

Thanks for any consideration.

11

Could you provide examples with numbers for gaps? It’s not clear what “gaps” mean.

12

gap is a short way to say “the difference between consecutive array elements”.

So using the example @RespiteSage provided earlier: n = [1, 3, 5, 9, 27] would produce:

n.gaps => [2, 2, 4, 18]

You can also have negative gap values, which tell you the data has changed slope up|down|flat.

[3, 6, 10, 17, 15, 11, 11, 13].gaps => [3, 4, 7, -2, -4, 0, 2]
[9, 2, 0, -2, -5, -1, -5, -13].gaps => [-7, -2, -2, -3, 4, -4, -8]

gap graphs are sometime called trend lines in economics.

So you’re a business, and you want a quick sense of how well you’re doing at any point.
You have daily sales figures (365 days of sales), so you do a trend (gap) analysis of the data.

Positive gaps means more sales (and how big) from the previous period, negative means a drop, and zero mean flat sales. You don’t need the absolute dollar sales, you’re just looking at your sales trends.

Here’s a short conceptualization (can be optimized) for min_max_gaps.
You don’t want an intermediate array (especially for huge data sets) just the min|max gaps.

def min_max_gaps(ary)
   min, max, gap = 0, 0, 0
   (ary.size - 1).times do |i|
      gap = ary[i + 1] - ary[i]
      min = gap if gap < min
      max = gap if gap > max
   end
   {min, max}
end

Again, this kind of data analysis is frequently done in statistics, economics, number theory, etc.

Edit:
Now that there’s multi-threading, you can break the array into sections and parallel process them, and then select the min|max from each thread. Again, this is desirable for processing large data sets.

1 Like
13

I feel like that makes a lot of sense for a stats library, but probably not so much the stdlib. It would require that the array contain types where - makes sense, which is probably only a small percentage of arrays in most programs.

Methods for collections of specific data types are awesome for libraries that revolve around those types. Since Array is an abstract data type, it should really only implement methods that are useful to collections of all types. For example, Array(String)#diffs wouldn’t be useful because strings don’t implement a - method.

14

I think there are tons of existing C libraries that deal with numbers in all and every way possible. Does it pay to do this work again and again, when you could just FFI the one suitable for your needs with very little effort?

15

C libs can add complexity and calling out to dependencies can make that code harder to alter or maintain. I think there are reasons to get this to work in Crystal.

16

I too think gaps could be provided as a shard.

Some simple code to implement it in all forms (array, enumerable and iterator): https://play.crystal-lang.org/#/r/7p4w

The iterator needs a small allocation but at least you don’t need to allocate an entire array. It could be made a struct if you always chain methods (I made it a class because it’s mutable).

With the iterator way implement minmax is almost the most efficient way (except that tiny class allocation).

17

I also did it just for Indexable. It could be made for Enumerable too but I was lazy.

18

Hey thanks @asterite, nice code.

I know this was a quick proof of concept exercise, but I modded gaps to reduce the number of reads from O(2n) to O(n). Now each array element is only read once, not twice. I suspect it could be more nicely/faster written.

https://play.crystal-lang.org/#/r/7pbb

  def gaps
    return [] of T if size < 2
    i, second = 0, self[0]
    elems = self.size - 1
    difs = Array(T).new(elems)
    while  i < elems
      first = self[i + 1]
      difs << first - second
      second = first
      i += 1
    end
    difs
  end