sorting an ArrayList by int

[xarax]

YUCK! Hugely inefficient instantiating 2 new Integer
instances, then immediately discarding them.

The Comparator approach is the best way.

Interesting, can you explain how your way is different? What is an
underflow problem?

Arithmetic with integers is subject to wrap-around without
any error or exception thrown. Thus, subtracting one point
from another point could yield the wrong algebraic sign.

Think about what happens if the first point is Integer.MIN_VALUE
and the second point is 1. Integer.MIN_VALUE-1 will wrap
(underflow) around to the Integer.MAX_VALUE.


The safest way is something like this:

public class ClubPointsComparator
implements Comparator
{
public int compare(final Object o1, final Object o2)
{
final Club c1 = (Club) o1;
final Club c2 = (Club) o2;
final int p1 = c1.points;
final int p2 = c2.points;

return ((p1 == p2) ? 0 : ((p1 < p2) ? -1 : 1));
}
}

Then instantiate a singleton instance of ClubPointsComparator
and use that for sorting the array of Club elements. The
implementation of Comparator above is far faster than
instantiating 2 new Integer instances for each array element
comparison.

If your Club class implements Comparable, then it
can only compare instances in one (natural) way.
Using Comparator instances lets you compare Club
instances in a variety of ways.


--
----------------------------
Jeffrey D. Smith
Farsight Systems Corporation
24 BURLINGTON DRIVE
LONGMONT, CO 80501-6906
http://www.farsight-systems.com
z/Debug debugs your Systems/C programs running on IBM z/OS for FREE!

 

[Bent C Dalager]

YUCK! Hugely inefficient instantiating 2 new Integer
instances, then immediately discarding them.

This is not likely to be anything even resembling a problem unless
it's inside of a tight loop.

As it is, I am perfectly happy to take an insignificant performance
hit in exchange for clearer, less error-prone, more maintainable code.
I find that optimising for correctness and maintainability is more
important than optimising for performance in almost all cases.

Cheers
Bent D

 

[Eric Sosman]

YUCK! Hugely inefficient instantiating 2 new Integer
instances, then immediately discarding them.

This is not likely to be anything even resembling a problem unless
it's inside of a tight loop.[/QUOTE]

Read the Subject line again: this comparison will
be used as part of a sort. Thus, it *is* in a tight
loop -- or more accurately, in a loop that is executed
often.

Some people seem to equate "O(N log N) is efficient"
with "O(N log N) is negligible." Do the math: on a 1000-
element array, an N lg N sort needs about 10000 comparisons.
A 10000-element array requires about 133000 comparisons, and
a million comparisons aren't enough for 62747 elements.
O(N log N) may be the best one can do for a comparison-
based general-purpose sort, but it's still superlinear and
far from cheap. It's the best of a bad lot, that's all.

As it is, I am perfectly happy to take an insignificant performance
hit in exchange for clearer, less error-prone, more maintainable code.
I find that optimising for correctness and maintainability is more
important than optimising for performance in almost all cases.

Now, I'll concede that the O.P. posed his problem in
connection with the scores in a sports league, and it's
probably the case that there are significantly fewer than
ten thousand teams in his league. If there are ten teams,
say, an N lg N sort will need only about thirty-three
comparisons, and questions of efficiency scarcely arise.
But one of the biggest promises of the object-oriented
Weltanschauung is code reuse, is it not? Whether the
promise will be (or even can be) kept is a topic for
another day, but it surely will *not* be kept if people
are taught to write code that relies on "N is small" and
can't be extended to "N is moderate," much less "large."

The practice of creating and discarding two useless
objects merely to avoid writing an `if' is, I think,
indefensible.

 

[Michael Borgwardt]

The Club class should not abstract so it seems I cannot include the line
'implements Comparable'

No, that's not what it means. It means you must implement the method
int compareTo(Object) in your class, which provides the comparison on
which the sort order is going to be based.

 

[zcraven]

OK I did that and it works. Next I made a 'top scorer' method which is
basically the same as the league, but instead of comparing clubs by points
scored, it compares players by goals scored. Why doesn't it work?

import java.util.*;

public class ScorersComparator implements Comparator
{
public int compare(Object o1, Object o2)
{
Player p1 = (Player) o1;
Player p2 = (Player) o2;
int retval;
int goals1 = p1.getGoalTally();
int goals2 = p2.getGoalTally();
return goals2 - goals1;
}
}

when I call the method, the arraylist is empty so I get an error.

 

[zcraven]

OK I did that and it works. Next I made a 'top scorer' method which is
basically the same as the league, but instead of comparing clubs by points
scored, it compares players by goals scored. Why doesn't it work?

import java.util.*;

public class ScorersComparator implements Comparator
{
public int compare(Object o1, Object o2)
{
Player p1 = (Player) o1;
Player p2 = (Player) o2;
int retval;
int goals1 = p1.getGoalTally();
int goals2 = p2.getGoalTally();
return goals2 - goals1;
}
}

when I call the method, the arraylist is empty so I get an error.

this is what i have so far (goldenboot means topscorer):

import java.util.*;
import java.lang.*;

public class League
{
// ########### FIELDS #########
public ArrayList league;
public ArrayList goldenboot;
private String leagueName;

// ########## CONSTRUCTORS ########
public League(String league_name)
{
league = new ArrayList();
goldenboot = new ArrayList();
leagueName = league_name;
}

// ########## METHODS ##########
public void sortScorers()
{
Collections.sort(goldenboot, new ScorersComparator());
}

public Player getTopScorer()
{
sortScorers();
return ((Player)goldenboot.get(0));
}

Where do i put the method to search all players and make a new collection of
scorers? At the moment the user is given a player name, and asked to type in
an INT for how many goals they scored. once this is done for the whole team
the players goal tallys are updated. so at that point I could add all
scorers to the leagues goldenboot collection. Or, I could have a method
'getScorers' that searchs all clubs for players that have scored and makes
the goldenboot collection from these.

which is better, and how would the code look?

 

[zcraven]

this is what i have so far (goldenboot means topscorer):

import java.util.*;
import java.lang.*;

public class League
{
// ########### FIELDS #########
public ArrayList league;
public ArrayList goldenboot;
private String leagueName;

// ########## CONSTRUCTORS ########
public League(String league_name)
{
league = new ArrayList();
goldenboot = new ArrayList();
leagueName = league_name;
}

// ########## METHODS ##########
public void sortScorers()
{
Collections.sort(goldenboot, new ScorersComparator());
}

public Player getTopScorer()
{
sortScorers();
return ((Player)goldenboot.get(0));
}

Where do i put the method to search all players and make a new collection of
scorers? At the moment the user is given a player name, and asked to type in
an INT for how many goals they scored. once this is done for the whole team
the players goal tallys are updated. so at that point I could add all
scorers to the leagues goldenboot collection. Or, I could have a method
'getScorers' that searchs all clubs for players that have scored and makes
the goldenboot collection from these.

which is better, and how would the code look?

this is how i did it and it seems to work ok - any comments?

public void updateGoldenboot()
{
for (int i=0; i<league.size(); i++)
{
Club club = (Club)league.get(i);
System.out.println("");
System.out.println("Searching " + club.getClubName());
ArrayList squad = club.getClubSquad();
for (int j=0; j<squad.size(); j++)
{
Player player = (Player)squad.get(j);
if (player.getGoalTally() > 0)
{
goldenboot.add(player);
System.out.println(player.getPlayerName() + " (goaltally
is " + player.getGoalTally() + ") added to goldenboot collection");
}
}
}
}

 

[Bent C Dalager]

Now, I'll concede that the O.P. posed his problem in
connection with the scores in a sports league, and it's
probably the case that there are significantly fewer than
ten thousand teams in his league. If there are ten teams,
say, an N lg N sort will need only about thirty-three
comparisons, and questions of efficiency scarcely arise.
But one of the biggest promises of the object-oriented
Weltanschauung is code reuse, is it not? Whether the
promise will be (or even can be) kept is a topic for
another day, but it surely will *not* be kept if people
are taught to write code that relies on "N is small" and
can't be extended to "N is moderate," much less "large."

This would be the difference between writing a general-purpose
algorithm for use in, say, a wide-spread collections API and writing a
custom algorithm for one specific use that you have complete knowledge
about.

In the case at hand, you could probably get away with using bubble
sort and creating a dozen temporary objects in the compare method. And
if that would make this particular piece of code significantly less
error-prone, more readable or more maintainable, then that is what you
should do.

If you are writing a general-purpose comparator for integers that is
likely to see wide-spread use in a variety of applications over which
you have no control, then this changes. In this case, the importance
of highly optimized performance overshadows the other needs and you
should choose the most effecient implementation possible even if that
does turn out to consist of an unreadable mess of obscure operators.

Cheers
Bent D

 

[zcraven]

I need to update it so that if all values (points, goal difference and goals
scored) are equal, it will sort the clubs by name (alphabetica order).

How do I update this code to include that?

public class ClubPointsComparator implements Comparator
{

public int compare(Object o1, Object o2)
{
Club c1 = (Club) o1;
Club c2 = (Club) o2;
int retval;
int points1 = c1.getPointsTally();
int points2 = c2.getPointsTally();
int gdiffs1 = c1.getGoalDifference();
int gdiffs2 = c2.getGoalDifference();
int gscrs1 = c1.getGoalsScored();
int gscrs2 = c2.getGoalsScored();
// String name1 = c1.getClubName();
// String name2 = c2.getClubName();

if (! (points1 == points2)){
retval = (points1 > points2) ? -1 : 1;}
else if (! (gdiffs1 == gdiffs2)){
retval = (gdiffs1 > gdiffs2) ? -1 : 1;}
else {
retval = (gscrs1 == gscrs2) ? 0 : (gscrs1 > gscrs2) ? -1 : 1;}

return retval;
}

}

 

[Steve Horsley]

I need to update it so that if all values (points, goal difference and goals
scored) are equal, it will sort the clubs by name (alphabetica order).

How do I update this code to include that?

try:

if(points1 != points2) {
return (points1 > points2) ? -1 : 1;
}
if(gdiffs1 != gdiffs2) {
return (gdiffs1 > gdiffs2) ? -1 : 1;
}
if(gscrs1 != gscrs2) {
return (gscrs1 > gscrs2) ? -1 : 1;
}
return name1.compareTo(name2);


Steve

 

[zcraven]

try:

if(points1 != points2) {
return (points1 > points2) ? -1 : 1;
}
if(gdiffs1 != gdiffs2) {
return (gdiffs1 > gdiffs2) ? -1 : 1;
}
if(gscrs1 != gscrs2) {
return (gscrs1 > gscrs2) ? -1 : 1;
}
return name1.compareTo(name2);


Steve

Thanks. This is my code (it doesnt work - it doesnt put them in
alphabetical order if all points are the same :-( ):

import java.util.*;

public class ClubPointsComparator implements Comparator
{

public int compare(Object o1, Object o2)
{
Club c1 = (Club) o1;
Club c2 = (Club) o2;
int retval;
int points1 = c1.getPointsTally();
int points2 = c2.getPointsTally();
int gdiffs1 = c1.getGoalDifference();
int gdiffs2 = c2.getGoalDifference();
int gscrs1 = c1.getGoalsScored();
int gscrs2 = c2.getGoalsScored();
String name1 = c1.getClubName();
String name2 = c2.getClubName();

if (! (points1 == points2)){
retval = (points1 > points2) ? -1 : 1;}
else if (! (gdiffs1 == gdiffs2)){
retval = (gdiffs1 > gdiffs2) ? -1 : 1;}
else if (! (gscrs1 == gscrs2)){
retval = (gscrs1 > gscrs2) ? -1 : 1;}
else {
retval = name1.compareTo(name2);}
return retval;
}

}

 

[zcraven]

my bad - it works fine now (i thought my test data had two equal clubs but i
had changed it a while back)