Program Optimization

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• September 29th, 2012, 10:54
dark3stnit3s
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.
Code java:

```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(); } }```
• September 29th, 2012, 11:22
Norm
Re: Program Optimization
[code=java]
[/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.
• September 29th, 2012, 12:21
dark3stnit3s
Re: Program Optimization
the infile is just a sequence that equates to an "election". Basically I just need any kind of tips on how to reduce the amount of for loops in order to speed this program up because as of right now it takes hours to run.
• September 29th, 2012, 12:25
helloworld922
Re: Program Optimization
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.
• September 29th, 2012, 12:26
Norm
Re: Program Optimization
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:
Code :

` 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:
Quote:

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?
• September 29th, 2012, 13:11
dark3stnit3s
Re: Program Optimization
here is a bit of the infile:
3 3
0 1 2
1 0 2
2 1 0
3 3
0 1 2
1 2 0
2 0 1
4 5
0 1 2 3 4
0 1 2 3 4
4 3 2 1 0
4 3 2 1 0
10 5

but i think I know where it gets hung up at. It is getting hung up at where it is comparing every candidate to another. Please keep in mind that the infile I have is much bigger and was too big to post here. Here is a sample and if you have any ideas of how to get the for loop outside of the the other for loop that would be great.
• September 29th, 2012, 13:13
Norm
Re: Program Optimization
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:
Quote:

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)
• September 29th, 2012, 13:39
dark3stnit3s
Re: Program Optimization
here is the missing class:
Code java:

```import java.io.OutputStream; import java.io.PrintStream;   /** * * A utility class used to time the execution of a Runnable */ public class TimeExec { private Runnable runnable; private String message; private OutputStream log;   /** * Contructor that creates a TimeExec * @param runnable the runnable to execute * @param message the message to be displayed when the run completes * @param log the stream to which the message is logged */ public TimeExec(Runnable runnable, String message, OutputStream log) { this.runnable = runnable; this.message = message; this.log = log; }   /** * Start the TimeExec. This will execute the runnable and log * the execution time (in secs) to the log. */ public void start() { PrintStream out = new PrintStream(log); long startTime = System.currentTimeMillis(); runnable.run(); long stopTime = System.currentTimeMillis(); out.println("TimeExec: " + message + ": " + ((stopTime - startTime) / 1000.0) + "s"); } }```

I mistakenly gave too much of the input file. I apologize here is what it should be:
3 3
0 1 2
1 0 2
2 1 0
3 3
0 1 2
1 2 0
2 0 1
4 5
0 1 2 3 4
0 1 2 3 4
4 3 2 1 0
4 3 2 1 0
• September 29th, 2012, 13:54
Norm
Re: Program Optimization
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?
• September 29th, 2012, 14:04
dark3stnit3s
Re: Program Optimization
here is some of the output I get when I run but after this it takes about an hour to get the next result due to the vastness of infile and the poor algorithm.
Winner of election 1 is candidate 1
TimeExec: Election 1: 0.015s
No winner for election 2
TimeExec: Election 2: 0.0s
No winner for election 3
TimeExec: Election 3: 0.0010s
Winner of election 4 is candidate 3
TimeExec: Election 4: 0.0s
No winner for election 5
TimeExec: Election 5: 0.0010s
Winner of election 6 is candidate 0
TimeExec: Election 6: 0.0010s
Winner of election 7 is candidate 2085
TimeExec: Election 7: 7.447s
Winner of election 8 is candidate 0
TimeExec: Election 8: 0.0010s
Winner of election 9 is candidate 2
TimeExec: Election 9: 0.0s
Winner of election 10 is candidate 7
TimeExec: Election 10: 0.0010s
Winner of election 11 is candidate 9
TimeExec: Election 11: 0.0s
Winner of election 12 is candidate 23
TimeExec: Election 12: 0.07s
Winner of election 13 is candidate 103
TimeExec: Election 13: 0.26s
No winner for election 14
TimeExec: Election 14: 0.273s
No winner for election 15
TimeExec: Election 15: 0.224s
Winner of election 16 is candidate 42
TimeExec: Election 16: 0.128s
Winner of election 17 is candidate 75
TimeExec: Election 17: 0.209s
No winner for election 18
TimeExec: Election 18: 0.425s
Winner of election 19 is candidate 106
TimeExec: Election 19: 0.344s
No winner for election 20
TimeExec: Election 20: 0.246s
Winner of election 21 is candidate 34
TimeExec: Election 21: 0.071s
• September 29th, 2012, 14:06
Norm
Re: Program Optimization
What about the other questions and issues in my last post?
• September 29th, 2012, 14:26
dark3stnit3s
Re: Program Optimization
I know that the search cannot be linear. I think I just need to compare the winner like if 0 beats 1 then don't compare 2 to 1 compare 2 to zero because if two beats zero it will also have more votes then one but I'm not quite sure how to do it.
• September 29th, 2012, 14:27
dark3stnit3s
Re: Program Optimization
here is the whole output... There are a total of 25 "elections"
Winner of election 1 is candidate 1
TimeExec: Election 1: 0.0050s
No winner for election 2
TimeExec: Election 2: 0.0010s
No winner for election 3
TimeExec: Election 3: 0.0s
Winner of election 4 is candidate 3
TimeExec: Election 4: 0.0010s
No winner for election 5
TimeExec: Election 5: 0.0s
Winner of election 6 is candidate 0
TimeExec: Election 6: 0.0s
Winner of election 7 is candidate 2085
TimeExec: Election 7: 7.577s
Winner of election 8 is candidate 0
TimeExec: Election 8: 0.0010s
Winner of election 9 is candidate 2
TimeExec: Election 9: 0.0s
Winner of election 10 is candidate 7
TimeExec: Election 10: 0.0010s
Winner of election 11 is candidate 9
TimeExec: Election 11: 0.0s
Winner of election 12 is candidate 23
TimeExec: Election 12: 0.074s
Winner of election 13 is candidate 103
TimeExec: Election 13: 0.279s
No winner for election 14
TimeExec: Election 14: 0.275s
No winner for election 15
TimeExec: Election 15: 0.238s
Winner of election 16 is candidate 42
TimeExec: Election 16: 0.132s
Winner of election 17 is candidate 75
TimeExec: Election 17: 0.215s
No winner for election 18
TimeExec: Election 18: 0.433s
Winner of election 19 is candidate 106
TimeExec: Election 19: 0.36s
No winner for election 20
TimeExec: Election 20: 0.256s
Winner of election 21 is candidate 34
TimeExec: Election 21: 0.07s
No winner for election 22
TimeExec: Election 22: 6115.777s
Winner of election 23 is candidate 1977
TimeExec: Election 23: 4746.472s
Winner of election 24 is candidate 410
TimeExec: Election 24: 980.273s
No winner for election 25
TimeExec: Election 25: 6199.193s
• September 29th, 2012, 14:30
Norm
Re: Program Optimization
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?
• September 29th, 2012, 14:42
dark3stnit3s
Re: Program Optimization
right now, I think it compares the first candidate to every other candidate. Then it moves to the second and compares... But what I think will be the fastest if it could store the positions of the candidates into an array and then subscript from there instead of doing a linear search. The main goal of this is to make the program O(1) or as close to it as possible.
• September 29th, 2012, 15:03
Norm
Re: Program Optimization
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
• September 29th, 2012, 15:10
dark3stnit3s
Re: Program Optimization
the 3 3 equates to the number of voters and number of candidates
the 1st row is how the first voter would rank the candidates - ie. 0 1 2 (0 would win followed by 1 and last 2).
each row is a different voter and the election last until there is a row with 2 numbers.
• September 29th, 2012, 15:12
Norm
Re: Program Optimization
Have you worked out the algorithm currently being used?
Can you post pseudo code to describe what it is doing?

Quote:

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?
• September 29th, 2012, 15:26
dark3stnit3s
Re: Program Optimization
The algorithm currently being used is that the first candidate is compared to every candidate in the list. Then the second is compared to everyone in the list and so on to determine what position the candidates fall into.
I don't know what to out for pseudo code.

In the infile there are rows of 2 numbers and subsequent rows of more than two numbers.
In the rows of 2 numbers marks the beginning of an election.

There can only be 1 winner or no winners.
In the first election:

3 3 < 3 voters, 3 candidates
0 1 2 < 1st voter, 0 beats 1 and 2, 1 beats 2 and 2 is in last.
1 0 2 < 2nd voter, 1 beats 0, 0 beats 2, and 2 is last.
2 1 0 < 3rd voter, 2 beats 1, 1 beats 0, and 0 is in last.

From this "election" we can determine that 1 is the winner because he beats 0 twice and 2 twice.
• September 29th, 2012, 15:37
Norm
Re: Program Optimization
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
• September 29th, 2012, 15:42
dark3stnit3s
Re: Program Optimization
I don't know if I quite understand your last statement but to clarify in a row with 3 columns, the first number is the first place position and it beast the last two, the middle is 2nd place and the last is 3rd place.
• September 29th, 2012, 15:53
Norm
Re: Program Optimization
Quote:

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.?
• September 29th, 2012, 15:55
dark3stnit3s
Re: Program Optimization
it is important to a degree because I am trying to find the winner...but as i said before there is a possibility of no winner
• September 29th, 2012, 15:57
Norm
Re: Program Optimization
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.?
• September 29th, 2012, 16:05
dark3stnit3s
Re: Program Optimization
7 would only beat 8
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last