Jul 14

Hunting high and low

by Wolfram Tags: , , ,
Add comments

Here is a nice little challenge, Benjamin came up with some months ago: “From a list of numbers find the smallest and the largest one – but do not use more than 1,5 comparisons per number.”

Dear reader: Try it!

The solution is simple, straight forward and very nice. And I didn’t find it.

I found something else. My approach was to look at the largest-number-so-far (max) and the smallest-number-so-far (min) as the boundaries of a region. A number outside this region must be larger than max or smaller than min and causes that boundary to change.

To check if a number (a) was outside that region a little computation came to my mind:

check = (max - a)*(min - a);

You would expect n to be smaller than max, so (max-n) should be positive.

You would expect n to be larger than min, so (n-min) should be positive, too.

Two positive numbers multiplied result in a positive number again.

So, if n was outside the boundaries, check would become negative. I only had to check which boundary was exceeded and that’s it:

if (check < 0)
    if (a > max)
        max = a;
    else
        min = a;

Using this approach the number of comparisons  converges to 1 when the length of the list grows. So I found a solution that is way better than 1,5 comparisons per number, didn’t I?

Boooooh

No, I didn’t. I cheated. In fact  (max-a) and (min-a) are comparisons, they just don’t use > or <.

(Actually it’s the other way around: To compute < or > most processors do a subtraction and compare the result to 0.)

So – if you count the subtractions as well you get 3+ comparisons per number…

The intended solution to the challenge (and the code you should provide in your exam) is:

a = list[count++];
b = list[count++];

if (a<b)
{
    if (a<min) min = a;
    if (b>max) max = b;
}
else
{
    if (b < min) min = b;
    if (a > max) max = a;                    
}

 

So – what’s the point of this post?

The point is: My silly approach can be faster than the standard solution. Depending on the type and range of the numbers in the list calculating and probing check needs less time than the comparisons in the standard solution.

It may not be much, but sometimes small advantages matter.  For example: For an integer-list of length 10^8 with values from -10.000 to 10.000 my approach is 0.02 seconds faster (on my current laptop). And has less code.

So if you feel like using it – I won’t charge you.

6 Responses to “Hunting high and low”

  1. Franz Antesberger Says:
    October 20th, 2009 at 11:04 pm

    You showed the solution of finding min/max of a list with size n with exactly 1.5 n comparisons of the list members ( you didn’t count the iterator comparisons, I will not count mine, too ).
    But because its very ugly to instanciate Pair or something like that in c#, I quacked my solution in beautiful duck typed python, just to show, that I can.
    I used divide and conquer and you will see, that I need LESS than 1.5 n.
    In the given example with 16 elements, I need only 22 comparisons compared to your 24.

    def minmax( list ):
    if len(list) == 1:
        return ( list[0], list[0] )
    if len(list) == 2:
        minmax.counter = minmax.counter + 1
        if list[0] > list[1]:
            return (list[1], list[0] )
        return (list[0], list[1] )
    mid = len(list) / 2
    left = minmax( list[0:mid] )
    right = minmax( list[mid:])
    min = left[0]
    minmax.counter = minmax.counter + 1
    if right[0]  max:
        max = right[1]
    return (min,max)

minmax.counter = 0
sample = range( 0, 16 )
print minmax( sample )
print minmax.counter

    ( that’s no code fragment, but the hole thing! )
    I leave the proof, that this will always needs LESS that 1.5 n comparisons as an exercise 😉

  2. Franz Antesberger Says:
    October 20th, 2009 at 11:07 pm

    Sorry, this stupid blog software removes all my code formatting! So the script will not run, if you don’t correct the indentation, but I hope, the clear concepts of python make the thing self-quack-describing

  3. Wolfram Bernhardt Says:
    October 20th, 2009 at 11:26 pm

    Hi Franz!

    That looks very interesting. Thanks a lot!
    Unfortunately I am not sure I understand what list[0] means… Could you please provide this example in a reasonable programming language? 🙂

    Greets,
    Wolfram

  4. Wolfram Bernhardt Says:
    October 20th, 2009 at 11:38 pm

    Ah… now I understand… but I have some questions.

    1)
    Doesn’t the part:

    left = minmax( list[0:mid] )
    right = minmax( list[mid:])

    copy the ‘mid’-element?

    This doesn’t influence the result, but results in a bad in influence (more work to do).

    2)
    I think the code isn’t correct.

    left = minmax( list[0:mid] )
    right = minmax( list[mid:])
    min = left[0]
    minmax.counter = minmax.counter + 1
    if right[0]  max:
        max = right[1]

    What about the min-result of right? And the max-result of left?
    So I think

    sample = range( 16, 0 )

    leads to a wrong result.

    Greets,
    Wolfram

  5. Franz Antesberger Says:
    October 22nd, 2009 at 9:58 pm

    To your questions:
    1) no, you are not right. the subrange excludes the upper bound, son the mid element is only in the second array
    2) yes, you are right. With copy/paste i have lost some code. Of course you have to build the min of the mins and the max of the maxes.
    To your first comment: You liked to have some code in a “reasonable” programming language. As I know you, you will not accept prolog or lisp or caml ( or caml light ) or f#, but only in your fetish language c#.
    So I built it in c#:
    [code]

    using System;
using System.Collections.Generic;

namespace MinMax
{
    class Program
    {
        public static int Counter { get; set; }

        public static int[] Range( int fromIncl, int toExcl )
        {
            int inc = fromIncl < toExcl ? 1 : -1;
            var len = Math.Abs(toExcl - fromIncl);
            var result = new int[len];
            for( int pos=0, val=fromIncl; pos < len; ++pos, val+=inc )
                result[pos] = val;
            return result;
        }

        public static int[] Subrange( int[] arr, int fromIncl, int toExcl )
        {
            var len = toExcl - fromIncl;
            var result = new int[len];
            for (int pos = 0; pos < len; ++pos)
                result[pos] = arr[fromIncl + pos];
            return result;
        }

        public static KeyValuePair MinMax( int[] arr )
        {
            if( arr.Length == 1 )
                return new KeyValuePair(arr[0],arr[0]);
            if( arr.Length == 2 )
            {
                Counter = Counter + 1;
                if( arr[0] < arr[1] )
                    return new KeyValuePair(arr[0], arr[1]);
                return new KeyValuePair(arr[1], arr[0]);
            }
            var mid = arr.Length/2;
            var left = MinMax(Subrange(arr, 0, mid));
            var right = MinMax(Subrange(arr, mid, arr.Length));
            Counter = Counter + 2;            
            return new KeyValuePair( Math.Min(left.Key,right.Key), Math.Max(left.Value,right.Value));
        }

        static void Main()
        {
            Counter = 0;
            Console.Out.WriteLine(MinMax(Range(0, 16)));
            Console.Out.WriteLine( "comparisons: " + Counter );
            Counter = 0;
            Console.Out.WriteLine(MinMax(Range(16, 0)));
            Console.Out.WriteLine("comparisons: " + Counter);
        }
    }
}

    [/code]
    I tried to put some lambda and linq in it, but the only reasonable way was:
    var min = arr.Min();
    var max = arr.Max();
    😉

  6. Wolfram Bernhardt Says:
    October 23rd, 2009 at 1:28 pm

    Hi again!

    1) Okay, I see. So I learned something about Python finally… hope I won’t be sent to hell for it.
    2) I would have accepted Prolog or Lisp perfecly… well at least I could have read it…

    Okay, I’ll check out your code soon.

WP Theme & Icons by N.Design Studio
Entries RSS Comments RSS Log in