Problem about the used time to sort an array

Thread view:

prado - 27 Jun 2006 08:25 GMT

I have a servlet and in this servlet I have a problem when I sort an
array. If in Tomcat 5.5.4 (on windows) the order is very fast (about 2
seconds) , but in tomcat 5.5.9 is slower (about 25 seconds). I don't
Know why the same code has diferent time. I don't know if I have
something different in the configuration.
The code is the next. The array has 7000 elements.

//////////////////////////////////////////////////////////////////////////////////////////////////////////
java.util.Date datTiempoInicio, datTiempoFin;
java.util.Calendar calTiempoInicio = Calendar.getInstance();
java.util.Calendar calTiempoFin = Calendar.getInstance();
long intTiempoUtilizado;
datTiempoInicio = new java.util.Date();
calTiempoInicio.setTime(datTiempoInicio );

if (astrName.length > 1) {
//ordenacion de los arrays: astrName[intFilaArray]
int i, pasadas;
String strTemp;
double dblIntensityTemp;
double dblBackgroundTemp;
int intComparacion;
for (pasadas = 1; pasadas < astrName.length; pasadas++) {
for (i = 0; i<astrName.length - 1; i++) {
intComparacion = astrName[i].compareTo(astrName[i+1]);
if (intComparacion > 0) {
strTemp = astrName[i];
astrName[i] = astrName[i + 1];
astrName[i + 1] = strTemp;

dblIntensityTemp = adblIntensity1[i];
adblIntensity1[i] = adblIntensity1[i + 1];
adblIntensity1[i + 1] = dblIntensityTemp;

dblIntensityTemp = adblIntensity2[i];
adblIntensity2[i] = adblIntensity2[i + 1];
adblIntensity2[i + 1] = dblIntensityTemp;

dblBackgroundTemp = adblBackground1[i];
adblBackground1[i] = adblBackground1[i + 1];
adblBackground1[i + 1] = dblBackgroundTemp;

dblBackgroundTemp = adblBackground2[i];
adblBackground2[i] = adblBackground2[i + 1];
adblBackground2[i + 1] = dblBackgroundTemp;
} // end if (intComparacion > 0)
} //end for i
} //end for pasadas

} // end if (astrName.length > 1)

datTiempoFin = new java.util.Date();
calTiempoFin.setTime(datTiempoFin );

intTiempoUtilizado = Math.abs( (calTiempoFin.getTimeInMillis() -
calTiempoInicio.getTimeInMillis()) / (1000) );
System.out.println("(ProcessFile) Time = " + intTiempoUtilizado );

////////////////////////////////////////////////////////////////////////////////////////////////

Can You help me?

Reply to this Message

Robert Klemme - 27 Jun 2006 09:31 GMT

> I have a servlet and in this servlet I have a problem when I sort an
> array. If in Tomcat 5.5.4 (on windows) the order is very fast (about 2
> seconds) , but in tomcat 5.5.9 is slower (about 25 seconds). I don't
> Know why the same code has diferent time. I don't know if I have
> something different in the configuration.

Then I suggest you find out.

> The code is the next. The array has 7000 elements.

<snip/>

> Can You help me?

Probably not. Note that this groups language is English and for those
of us who do not speak Spanish (?) it's difficult to read your code.
Also I don't understand why you do not use standard sorting facilities
of Java's std lib or why you do not use a SortedSet.

Kind regards

robert

Reply to this Message

prado - 27 Jun 2006 10:14 GMT

Sorry,
I have to sort an string array. I am using the bubble method to do
this. I don't know why there is this diferent of time in 2 computers.

I think it can be the problem in the compareTo Method.

int intFilas = 6272;
String astrName[] = new String[intFilas];
double adblBackground[] = new double[intFilas];
double adblIntensity[] = new double[intFilas];

double adblBackground1[] = new double[intFilas];
double adblBackground2[] = new double[intFilas];
double adblIntensity1[] = new double[intFilas];
double adblIntensity2[] = new double[intFilas];

//Here load the data in the arrays
......
//Here sort the arrays

if (astrName.length > 1) {
int i, pas;
String strTemp;
double dblIntensityTemp;
double dblBackgroundTemp;
int intComparacion;

for (pas = 1; pas < astrName.length; pas++) {
for (i = 0; i<astrName.length - 1; i++) {

intComparacion = astrName[i].compareTo(astrName[i+1]);
if (intComparacion > 0) {

strTemp = astrName[i];
astrName[i] = astrName[i + 1];
astrName[i + 1] = strTemp;

dblIntensityTemp = adblIntensity1[i];
adblIntensity1[i] = adblIntensity1[i + 1];
adblIntensity1[i + 1] = dblIntensityTemp;

dblIntensityTemp = adblIntensity2[i];
adblIntensity2[i] = adblIntensity2[i + 1];
adblIntensity2[i + 1] = dblIntensityTemp;

dblBackgroundTemp = adblBackground1[i];
adblBackground1[i] = adblBackground1[i + 1];
adblBackground1[i + 1] = dblBackgroundTemp;

dblBackgroundTemp = adblBackground2[i];
adblBackground2[i] = adblBackground2[i + 1];
adblBackground2[i + 1] = dblBackgroundTemp;

} // end if (intComparacion > 0)
} //end for i
} //end for pasadas

} // end if (astrName.length > 1)

Reply to this Message

Patricia Shanahan - 27 Jun 2006 12:35 GMT

> Sorry,
> I have to sort an string array. I am using the bubble method to do
> this. I don't know why there is this diferent of time in 2 computers.

If you really care about the performance difference, check two areas:

1. Are you really sorting EXACTLY the same strings in both cases.
Although you have managed to code it in such a way that it will take the
full number of iterations even for already sorted arrays, it will still
be faster if it does not have to do a lot of swaps.

Given the very large number of string comparisons, the lengths of the
strings, and especially the number of characters before the first
difference in any pair, will matter.

2. Look at cache sizes on the two computers. Bubble sort does repeated
scans over the whole array. It will be faster if the array, with all the
data it references, fits in processor cache.

However, bubble sort is one of the slowest sort methods known. It's best
use, arguably its only valid use, is as an exercise for beginning
programmers learning loops and arrays. Unfortunately, textbooks and
teachers sometimes fail to make it clear that it is just a programming
exercise, not a good sort method.

java.util.Arrays contains a sort method that sorts any array of
references to mutually comparable objects, including String[]. Even if I
did not care about performance, I would use that in preference to
writing my own sort for code simplicity. You could replace:

//Here sort the arrays
through
} // end if (astrName.length > 1)
with
Arrays.sort(astrName);

Patricia

Reply to this Message

prado - 27 Jun 2006 14:00 GMT

Hi,

> //Here sort the arrays
>through
> } // end if (astrName.length > 1)
>with
> Arrays.sort(astrName);
>Patricia

I can not use the sort method because I have the arrays have an
relation. I mean, the first element of astrName have relation with
first element of adblBackground1, adblBackground2, adblItensity1 and
adblItensity2.

Then I can sort each array independently, if I sort an element of
astrName I have to sort the rest of arrays.

Can you tell me a way to do this?

Thanks.

Reply to this Message

Patricia Shanahan - 27 Jun 2006 14:45 GMT

> Hi,
>
[quoted text clipped - 16 lines]
>
> Thanks.

Write a class that wraps the related data together, and have a single
array containing references to objects of that class.

If sorting will always be according to astrName order, make it
Comparable with a compareTo based on astrName. If there are several
reasonable orders, use a Comparator sort, also available in
java.util.Arrays.

Patricia

Reply to this Message

prado - 27 Jun 2006 15:36 GMT

Hi,

> Write a class that wraps the related data together, and have a single
> array containing references to objects of that class.
[quoted text clipped - 5 lines]
>
> Patricia

Can yo put a little example, please?

Reply to this Message

Eric Sosman - 27 Jun 2006 13:17 GMT

> Sorry,
> I have to sort an string array. I am using the bubble method to do
> this. I don't know why there is this diferent of time in 2 computers.
> [...]

Bubble sort is a poor algorithm. First, it has O(N*N)
average complexity, which means that the time to sort is
roughly proportional to the square of the number of items
being sorted: sorting fifty items takes ~25 times as long as
sorting ten. Second, even when compared to other O(N*N)
sorting algorithms, bubble sort is usually slower: all the
running times are roughly proportional to the square of N
but with different proportionality factors, and bubble sort's
is larger than most others.

You mention that the array has ~7000 elements, and this
is far too many for an O(N*N) sort -- it will take about as
much time to sort this array as to sort half a million ten-
element arrays. Java provides implementations of better
sorting methods in the Arrays and Collections classes; use
them, that's why they're there.

Signature

Eric Sosman
esosman@acm-dot-org.invalid

Reply to this Message

Chris Uppal - 27 Jun 2006 13:21 GMT

(Thanks for taking the time to translate your example.)

> I have to sort an string array. I am using the bubble method to do
> this. I don't know why there is this diferent of time in 2 computers.

You may have to sort a string array, but that's no reason to write your own
sort routine when better ones are provided for you. See
java.util.Arrays.sort(Object[]). Since you want to keep your intensity and
background arrays in the same order, you will probably have to create an object
which holds a String name, intensity and background values -- but that's almost
certainly worth doing anyway.

BTW: there is /never/ a valid reason to use Bubble sort in real code -- Insert
sort is just as simple (simpler I'd say) and is twice as fast. So even if you
do need a simple sort (for very small arrays, say), don't use Bubble sort.

Also, this array is /much/ too big for Insert sort to be a suitable choice
/unless/ you know in advance that it is in very nearly sorted order already.

> I think it can be the problem in the compareTo Method.

It's often the case when string comparison takes a lot longer on one system
than another, that it is due to different collation ordering. Some locales
have collation rules which can be implemented very simply and efficiently,
others have complicated rules which can slow down comparison by more than an
order of magnitude.

However that isn't the case for String.compareTo() which is documented (and you
can check the source too) to compare Strings char-by-char using only the
numerical values of he chars. Hence it is not locale-sensitive.

I have no idea why you are seeing this difference. Possibly one Java
installation is running Tomcat with the JIT turned off (-Xint). More likely
(if the two arrays of Strings are not identical) the inherent slowness of
bubble sort is showing up on only one set of inputs.

I would replace your sort code with a call to Arrays.sort() and see if the
problem goes away.

Another BTW, when you are doing millisecond timing, it's a much simpler to use
long now = System.currentTimeMillis();
than messing around creating Date objects (which just gives the same answer for
more work).

-- chris

Reply to this Message

Problem about the used time to sort an array

Free Magazines