commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Inger, Matthew" <In...@Synygy.com>
Subject RE: [lang] ArrayUtils.isAscending, isDescending
Date Thu, 01 Apr 2004 19:59:42 GMT
I can't speek for collections, but as far as Arrays.binarySearch,
it assumes the array is sorted.  If it's not, you just don't get
back the correct results you're expecting.

public static int binarySearch(char[] a,
                               char key)Searches the specified array of
chars for the specified value using the binary search algorithm. The array
must be sorted (as by the sort method, above) prior to making this call. If
it is not sorted, the results are undefined. If the array contains multiple
elements with the specified value, there is no guarantee which one will be
found.


checking for something already being sorted is probably not a good
idea as it adds unnecessary overhead, required N - 1 comparisons
to verify that any given array is sorted (either ascending or descending).
Add this on top of the O(N) comparisons required to quicksort the array,
and you're somewhere around O(2N) comparisons before you even run the
algorithm expecting the sorted array.




-----Original Message-----
From: Gary Gregory [mailto:ggregory@seagullsw.com]
Sent: Thursday, April 01, 2004 2:50 PM
To: Jakarta Commons Developers List
Subject: RE: [lang] ArrayUtils.isAscending, isDescending


Hmm, I was thinking that /because/ we are talking of primitive arrays
and not Object arrays, this would make things simpler in the sense that
a Comparator is not needed. Does simple like isAscending(double[]) fit
in [lang] and ArrayUtils as opposed to adding something to [primitives]?
Or is this too much of a math-like query and should stay in math?

Of course, one could argue, that starting to add isThisOrThat type of
methods might open the door to other requests that might not belong. 

In the XP way, I would not be against adding the two is- methods for the
primitive datatypes [math] needs, no more, no less. In this case we are
only talking about double?

I'd like to hear what others have to say.

> In a few places in [math] we need to verify that double[] array
> arguments
> > are sorted.  

I did not look at the code but I am wondering: what if the array is not
sorted properly? Does [math] throw an exception, sort the array and
proceed? 

Gary 

> -----Original Message-----
> From: Stephen Colebourne [mailto:scolebourne@btopenworld.com]
> Sent: Thursday, April 01, 2004 11:25
> To: Jakarta Commons Developers List
> Subject: Re: [lang] ArrayUtils.isAscending, isDescending
> 
> Actually I would argue against. I think [lang] can supply methods to
do
> the
> sort, but specific sort test methods doesn't feel right.
> 
> For an Object[], having an
>  isSorted(Object[], Comparator)
> would make sense.
> 
> But there is no easy way to apply that kind of plugin for primitive
> arrays.
> Consider me -0.
> 
> Stephen
> 
> ----- Original Message -----
> From: "Gary Gregory" <ggregory@seagullsw.com>
> It seems quite sensible to me. The best would be for [math] to create
a
> [lang] bugzilla ticket and submit a patch with unit tests.
> 
> Thank you,
> Gary
> 
> > -----Original Message-----
> > From: Phil Steitz [mailto:phil@steitz.com]
> > Sent: Thursday, April 01, 2004 09:17
> > To: Jakarta Commons Developers List
> > Subject: [lang] ArrayUtils.isAscending, isDescending
> >
> > In a few places in [math] we need to verify that double[] array
> arguments
> > are sorted.  Would methods such as these make sense in ArrayUtils?
> > Considering all ordered types and strict vs. = would lead to quite a
> few
> > new methods.
> >
> > For now, we can just code what we need in [math], but I thought I
> would
> > toss this out for [lang] to consider.  Thoughts?
> >
> > Phil
> >
> >
> >
---------------------------------------------------------------------
> > To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> > For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> >
> 
> 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> 
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
> 



---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message