finding min and max of a double[]

Discussion in 'Java' started by jimgardener, Jul 18, 2008.

  1. jimgardener

    jimgardener Guest

    i tried diff ways to find min and max of a double[] .one using for
    loops and the other with Arrays.sort

    public void findmaxdemo1(){
    double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    long start=System.nanoTime();
    double max=testarray[testarray.length-1];
    double min=testarray[0];
    for(int i=0;i<testarray.length;i++){
    max=max>testarray?max:testarray;
    min=min<testarray?min:testarray;
    }
    long end=System.nanoTime();
    debug("min:"+min);
    debug("max:"+max);
    debug("by for loops took:"+(end-start));

    }

    public void findmaxdemo2(){
    double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    long start=System.nanoTime();
    Arrays.sort(testarray);
    double max=testarray[testarray.length-1];
    double min=testarray[0];
    long end=System.nanoTime();
    debug("min:"+min);
    debug("max:"+max);
    debug("by Array took:"+(end-start));
    }

    public static void debug(String msg){
    System.out.println(msg);
    }

    i find that the method using Arrays.sort takes more time than the
    first one..i would like to know if the first one can be made faster?
    I am not familiar with alg.analysis methods.Can someone advise as to
    how i can find the max and min more efficiently

    thanks
    jim
     
    jimgardener, Jul 18, 2008
    #1
    1. Advertising

  2. jimgardener

    voorth Guest

    On Jul 18, 8:55 am, jimgardener <> wrote:
    > i tried diff ways to find min and max of a  double[] .one using for
    > loops and the other with Arrays.sort
    >
    > public void findmaxdemo1(){
    >                 double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    >                 long start=System.nanoTime();
    >                 double max=testarray[testarray.length-1];
    >                 double min=testarray[0];
    >                 for(int i=0;i<testarray.length;i++){
    >                         max=max>testarray?max:testarray;
    >                         min=min<testarray?min:testarray;
    >                 }
    >                 long end=System.nanoTime();
    >                 debug("min:"+min);
    >                 debug("max:"+max);
    >                 debug("by for loops took:"+(end-start));
    >
    >         }
    >
    > public void findmaxdemo2(){
    >                 double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    >                 long start=System.nanoTime();
    >                 Arrays.sort(testarray);
    >                 double max=testarray[testarray.length-1];
    >                 double min=testarray[0];
    >                 long end=System.nanoTime();
    >                 debug("min:"+min);
    >                 debug("max:"+max);
    >                 debug("by Array took:"+(end-start));
    >         }
    >
    > public static void debug(String msg){
    >                 System.out.println(msg);
    >         }
    >
    > i find that the method using Arrays.sort takes more time than the
    > first one..i would like to know if the first one can be made faster?
    > I am not familiar with alg.analysis methods.Can someone advise as to
    > how i can find the max and min more efficiently
    >


    Did you try this with large arrays? Six elements is really not long
    enough to get reliable metrics. Apart from that, I'm not surprised
    that the first method is faster - remember that Arrays.sort() also
    moves all intermediate values.

    One possible improvement is to use explicit "if" statements instead of
    the "?" operator. That will save you some assignments to max:

    if(testarray > max) max = testarray;
    if(testarray < min) min = testarray;

    but I doubt if it's worth the trouble.

    --Henk
     
    voorth, Jul 18, 2008
    #2
    1. Advertising

  3. jimgardener

    GArlington Guest

    On Jul 18, 9:02 am, voorth <> wrote:
    > On Jul 18, 8:55 am, jimgardener <> wrote:
    >
    >
    >
    > > i tried diff ways to find min and max of a double[] .one using for
    > > loops and the other with Arrays.sort

    >
    > > public void findmaxdemo1(){
    > > double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    > > long start=System.nanoTime();
    > > double max=testarray[testarray.length-1];
    > > double min=testarray[0];
    > > for(int i=0;i<testarray.length;i++){
    > > max=max>testarray?max:testarray;
    > > min=min<testarray?min:testarray;
    > > }
    > > long end=System.nanoTime();
    > > debug("min:"+min);
    > > debug("max:"+max);
    > > debug("by for loops took:"+(end-start));

    >
    > > }

    >
    > > public void findmaxdemo2(){
    > > double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    > > long start=System.nanoTime();
    > > Arrays.sort(testarray);
    > > double max=testarray[testarray.length-1];
    > > double min=testarray[0];
    > > long end=System.nanoTime();
    > > debug("min:"+min);
    > > debug("max:"+max);
    > > debug("by Array took:"+(end-start));
    > > }

    >
    > > public static void debug(String msg){
    > > System.out.println(msg);
    > > }

    >
    > > i find that the method using Arrays.sort takes more time than the
    > > first one..i would like to know if the first one can be made faster?
    > > I am not familiar with alg.analysis methods.Can someone advise as to
    > > how i can find the max and min more efficiently

    >
    > Did you try this with large arrays? Six elements is really not long
    > enough to get reliable metrics. Apart from that, I'm not surprised
    > that the first method is faster - remember that Arrays.sort() also
    > moves all intermediate values.
    >
    > One possible improvement is to use explicit "if" statements instead of
    > the "?" operator. That will save you some assignments to max:
    >
    > if(testarray > max) max = testarray;
    > if(testarray < min) min = testarray;
    >
    > but I doubt if it's worth the trouble.
    >
    > --Henk


    And you can put second if inside the 1st if's else part. Again both
    improvements are NOT going to save you much...
     
    GArlington, Jul 18, 2008
    #3
  4. jimgardener

    Tom McGlynn Guest

    On Jul 18, 5:50 am, GArlington <> wrote:
    > On Jul 18, 9:02 am, voorth <> wrote:
    >
    >
    >
    > > On Jul 18, 8:55 am, jimgardener <> wrote:

    >
    > > > i tried diff ways to find min and max of a double[] .one using for
    > > > loops and the other with Arrays.sort

    >
    > > > public void findmaxdemo1(){
    > > > double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    > > > long start=System.nanoTime();
    > > > double max=testarray[testarray.length-1];
    > > > double min=testarray[0];
    > > > for(int i=0;i<testarray.length;i++){
    > > > max=max>testarray?max:testarray;
    > > > min=min<testarray?min:testarray;
    > > > }
    > > > long end=System.nanoTime();
    > > > debug("min:"+min);
    > > > debug("max:"+max);
    > > > debug("by for loops took:"+(end-start));

    >
    > > > }

    >
    > > > public void findmaxdemo2(){
    > > > double[] testarray=new double[]{-1.2,4.3,7,0,2.1,0.0,2.5};
    > > > long start=System.nanoTime();
    > > > Arrays.sort(testarray);
    > > > double max=testarray[testarray.length-1];
    > > > double min=testarray[0];
    > > > long end=System.nanoTime();
    > > > debug("min:"+min);
    > > > debug("max:"+max);
    > > > debug("by Array took:"+(end-start));
    > > > }

    >
    > > > public static void debug(String msg){
    > > > System.out.println(msg);
    > > > }

    >
    > > > i find that the method using Arrays.sort takes more time than the
    > > > first one..i would like to know if the first one can be made faster?
    > > > I am not familiar with alg.analysis methods.Can someone advise as to
    > > > how i can find the max and min more efficiently

    >
    > > Did you try this with large arrays? Six elements is really not long
    > > enough to get reliable metrics. Apart from that, I'm not surprised
    > > that the first method is faster - remember that Arrays.sort() also
    > > moves all intermediate values.

    >
    > > One possible improvement is to use explicit "if" statements instead of
    > > the "?" operator. That will save you some assignments to max:

    >
    > > if(testarray > max) max = testarray;
    > > if(testarray < min) min = testarray;

    >
    > > but I doubt if it's worth the trouble.

    >
    > > --Henk

    >
    > And you can put second if inside the 1st if's else part. Again both
    > improvements are NOT going to save you much...



    I don't think that's right given the way the OP initialized the loop.
    Had the initialization been:

    min = max = testarray[0];

    then you'd be correct, but with

    min = testarray[0]; max = testarray[testarray.length-1];

    the initial conditions of the loop may have min>max. I think the OP
    thought that catering to the case where the original array was ordered
    would be helpful.


    A fairly robust algorithm that incorporates your suggestion and should
    be about as fast as any is

    min=max=Double.NaN;
    if (testarray.length > 0) {

    min=max=testarray[0];

    for (int i=1; i<testarray.length; i += 1) {
    double test = testarray;
    if (test < min) {
    min = test;
    } else if (test > max) {
    max = test;
    }
    }
    }


    One may also need to decide how to handle NaNs when they're
    considering a general algorithm.

    Tom McGlynn
     
    Tom McGlynn, Jul 18, 2008
    #4
  5. jimgardener

    Uwe Schmitt Guest

    On 18 Jul., 08:55, jimgardener <> wrote:
    > i tried diff ways to find min and max of a  double[] .one using for
    > loops and the other with Arrays.sort
    >
    >
    >
    > i find that the method using Arrays.sort takes more time than the
    > first one..i would like to know if the first one can be made faster?


    This is because sorting needs time O(log n), an iterating over
    an array is O(n). As you have to "touch" each element for finding
    max and min you can not find an algorithm which is faster than O(n).

    The following solution should be a little bit faster than your
    solution:

    double max=testarray[0];
    double min=testarray[0];

    for(int i=1; i<testarray.length; i++){

    if (testarray>max)
    max = testarray;

    else if (testarray<min)
    min = testarray;
    }

    Greetings, Uwe
     
    Uwe Schmitt, Jul 18, 2008
    #5
  6. jimgardener

    Uwe Schmitt Guest

    On 18 Jul., 14:31, Uwe Schmitt <> wrote:
    > On 18 Jul., 08:55, jimgardener <> wrote:
    >
    > > i tried diff ways to find min and max of a  double[] .one using for
    > > loops and the other with Arrays.sort

    >
    > > i find that the method using Arrays.sort takes more time than the
    > > first one..i would like to know if the first one can be made faster?

    >
    > This is because sorting needs time O(log n), an iterating over

    ^^^^^^^^
    Wanted to say "O(n log n)"

    Greetings, Uwe
     
    Uwe Schmitt, Jul 18, 2008
    #6
  7. jimgardener

    Roedy Green Guest

    On Thu, 17 Jul 2008 23:55:50 -0700 (PDT), jimgardener
    <> wrote, quoted or indirectly quoted someone who
    said :

    >max=max>testarray?max:testarray;


    Math.max will do this for you.

    e.g. max = Math.math( max, testArray[ i ] );

    If speed is important, code it like this

    if (testArray[i ] > max ){ max = testArray;}
    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Jul 19, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kevin
    Replies:
    8
    Views:
    5,045
    Chris Uppal
    Mar 14, 2006
  2. Lois
    Replies:
    1
    Views:
    3,403
    Ryan Stewart
    Dec 27, 2004
  3. john
    Replies:
    41
    Views:
    1,248
    Chris Theis
    Jan 22, 2004
  4. Sydex
    Replies:
    12
    Views:
    6,644
    Victor Bazarov
    Feb 17, 2005
  5. Camp Fire
    Replies:
    0
    Views:
    338
    Camp Fire
    Nov 2, 2004
Loading...

Share This Page