Thread: Program Optimization

I was given a program in one of my 300 level college classes. It supposed to calculate winners of voters voting on candidates in a specific order. The assignment is to look at the code and try to get it to run faster. As of right now it takes hours to run. If anyone could help out it would be great. Thanks in advance.

package edu.iup.cosc310.util;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
/**
 *
 * 
 * Utility class to compute the pairwise winner of elections
 */
public class PairwiseVote {
        /**
         * Get the placement order of a candidate in a rank ordered list of candidates
         *
         * @param votersVotes an array of rank ordered candidates.  First has the highest
         *                    rank.
         */
	public static int getPlacement(int candidate, int[] votersVotes ) {
		for (int placement = 0; placement < votersVotes.length; placement++) {
			if (candidate == votersVotes[placement]) {
				return placement;
			}
		}
		return votersVotes.length + 1;
	}
 
	/**
	 * Get the candidate winner from a set of rank ordered ballots
         *
         * @param votes - a two dimensional array, first dimension is the voter, second dimension
         *                is the rank order ballot of candidates for the given voter
	 */
	public static int getPairwiseWinner(int[][] votes) {
		int noVoters = votes.length;
 
		if (noVoters == 0) {
			return -1;
		}
 
		int noCandidates = votes[0].length;
 
		if (noCandidates == 0) {
			return -1;
		}
 
		// Compare every pair of candidates
		for (int candidate1 = 0; candidate1 < noCandidates; candidate1++) {
			int noTimesCandidate1Wins = 0;
			for (int candidate2 = 0; candidate2 < noCandidates; candidate2++) {
				// Consider a candidate compared with themselves to be a winner
				if (candidate1 == candidate2) {
					noTimesCandidate1Wins++;
					continue;
				}
 
				// Determine count the ballots for each candidate
				int candidate1votes = 0;
				int candidate2votes = 0;
				for (int voter = 0; voter < noVoters; voter++) {
					int placement1 = getPlacement(candidate1, votes[voter]); 
					int placement2 = getPlacement(candidate2, votes[voter]); 
					if (placement1 < placement2) {
						candidate1votes++;;
					} else  {
						candidate2votes++;;						
					}
				}
 
				// determine if candidate1 is the winner if so increment the number of wins
				if (candidate1votes > candidate2votes) {
					noTimesCandidate1Wins++;
				}
			}
 
			// Determine if candidate 1 wins all
			if (noTimesCandidate1Wins == noCandidates) {
				return candidate1;
			}
		}
 
		// No winner
		return -1;
	}
 
	static int electionNo = 0;
 
        /**
         * Main - reads several test elections using the text file votes.txt. Each election
         * begins with two number, the number of voters and the number of candidates, all followed
         * by the ballots of each voter.
         */
	public static void main(String[] args) throws FileNotFoundException {
		int noVoters;
		int noCandidates;
 
		Scanner in = new Scanner(new FileInputStream("votes.txt"));
 
		// read ballots for each election
		for(;;) {
			noVoters = in.nextInt();
			noCandidates = in.nextInt();
 
			if (noVoters == 0 && noCandidates == 0) {
				break;
			}
 
			final int[][] votes = new int[noVoters][noCandidates];
 
                        // Read the ballots
			for (int i = 0; i < noVoters; i++) {
				for (int j = 0; j < noCandidates; j++) {
					votes[i][j] = in.nextInt();
				}
			}
 
			new TimeExec(new Runnable() {
				public void run() {
					int winner = getPairwiseWinner(votes);
					if (winner >= 0) {
						System.out.printf("Winner of election %d is candidate %d\n", electionNo, winner); 
					} else {
						System.out.printf("No winner for election %d\n", electionNo);
					}
				}
			}, "Election " + ++electionNo, System.out).start();		
		}
	}

Please Edit your post and wrap your code with
[code=java]
<YOUR CODE HERE>
[/code]
to get highlighting and preserve formatting.


what's in the file it reads?

Have you tried using a profiler to see where the code is spending its time? The java command has an option that will give a report.

As norm said, try profiling your code first to identify where the slow spots are. It makes no sense to try and highly optimize a piece of code that's not a major resource hog.

If you can, create a smaller test file so you can repeatedly test changes made without having to wait hours for a run to finish.

There is no way to test the code without the contents of the file it reads.
Also the code does not compile because of a missing class.
When I removed the usage of the missing class and fed the Scanner with this:

		Scanner in = new Scanner("2 2 1 2 3 4 5 1 2 3  1 2 3 1 2 3 0 0 0 0 0 0 0 0 0 0"); //new FileInputStream("votes.txt"));

I get the following output very quickly:

No winner for election 0
Winner of election 0 is candidate 0
Winner of election 0 is candidate 0

Did you try profiling the code?

Where is the definition for the missing class?

What does the profiling report look like?

Is that a valid and complete file for testing?
I get this error when I use it:

Exception in thread "main" java.util.NoSuchElementException
at java.util.Scanner.throwFor(Unknown Source)
at java.util.Scanner.next(Unknown Source)
at java.util.Scanner.nextInt(Unknown Source)
at java.util.Scanner.nextInt(Unknown Source)
at PairwiseVote.main(PairwiseVote.java:120)

Did you test the program with that data in a file?
I get this error:
Exception in thread "main" java.util.NoSuchElementException


How many "elections" worth of data are in the complete file?

Can you post some of the output from the program? Say the first 40 lines?

What about the other questions and issues in my last post?

It looks like the last 4 "elections" are the ones to test with.

Have you worked out the algorithm currently being used?
Can you post pseudo code to describe what it is doing?

Have you defined the contents of the data file?
What do all the numbers in it mean?
I see what the lines with a pair of numbers are.
What are the rest?

You seem to miss questions when I ask more than one at a time, so I'll ask them one at a time: From post#14

Have you defined the contents of the data file?

Can you define what goes on each row and in each column?
3 3
0 1 2
1 0 2
2 1 0

Have you worked out the algorithm currently being used?
Can you post pseudo code to describe what it is doing?

the election last until there is a row with 2 numbers.

That doesn't make sense to me.
Can you explain?

How many winners can there be in an election?
Can you post a sample showing winners and explain how you determined who the winner(s) are?

The candidate the beats the most is the winner. So the position in a row of the array determines the number of others that a cand. beats. In a row with 3 columns, the first cand. beats 2, the second cand. beats 1

the middle is 2nd place and the last is 3rd place.

Is the placement important? Or is the number of other cand.s that a cand. beats important?
1 2 3 4 5 6 7 8
With the above voting, would 7 have beaten 1 other cand.?

Sorry, I asked two questions again. I'll have to remember to only ask one at a time.

1 2 3 4 5 6 7 8
With the above voting, would 7 have beaten 1 other cand.?