Back to Questions
2.2k
views2
comments
Min and max, shortest code
f#opinion

Hi all!

Tell me please, how can I get the min and max from the array with shortest code (maybe, in one pass)?

I means this (somearray is float[] ):

1
2
3

let minx = Array.min (somearray)

let maxx = Array.max (somearray)

This is too long. Possibly, it makes two pass ower the array. I tried to do this:

let minx, maxx = Array.min, Array.max (somearray)

but got the wrong types. minx has type 'a[]->'a, and I can understand the compiler's opinion :) It wants to bind to minx the only (Array.min).

But, can I do this with only one "somearray" word?

.

Hi

First, the "wrong type" is because you are not applying Array.min to any argument; Array.min has the type 'a[] -> 'a, this is what you are seeing.

If you want to apply two functions to a single argument then define some function like:

1

let apply2 (f,g) x = f x, g x

then

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

let inline min_max x = apply2 (Array.min,Array.max) x

If however you want to do this in one traversal of the array, take a look at how Array.min / max are implemented in the core library.

From there, it should be quite straightforward; you should end up with something like the following:

let inline min_max (array:_[�]) =             


            if array.Length = 0 then invalidArg "array" "Input array empty"


            let mutable mn_acc = array.[�0]


            let mutable mx_acc = array.[�0]


            


            for i = 1 to array.Length - 1 do


                let curr = array.[�i]


                if curr < mn_acc then mn_acc <- curr


                if curr > mx_acc then mx_acc <- curr


            


            mn_acc,mx_acc

You can compare with the following:

1
2
3
4
5
6

#time 

let min1,max1 = Array.min data, Array.max data

let min2,max2 = min_max data

for some suitably defined 'data'.

I ran this for an array of 10,000,000 floats; calling both Array.min and Array.max gives:

1
2
3
4
5
6
7
8

Real: 00:00:00.107, CPU: 00:00:00.109, GC gen0: 0, gen1: 0, gen2: 0

val min1 : float = 1.303851605e-08


val max1 : float = 0.999999912

whereas calling our new function gives:

1
2
3
4
5
6
7

Real: 00:00:00.067, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0

val min2 : float = 1.303851605e-08


val max2 : float = 0.999999912

So a slight speed up. Note that if you try to do the same thing with a more idiomatic Array.fold, you will actually see a slow down relative to applying the Array.min and Array.max functions individually.

Regards,

Michael

By on 4/15/2011 7:43 AM ()

Wow, the great answer!

Thank you a lot!

By on 4/18/2011 5:30 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper