Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Page 1 of 2 12 LastLast
Results 1 to 25 of 32

Thread: Program Optimization

  1. #1
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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();		
    		}
    	}
    Last edited by dark3stnit3s; September 29th, 2012 at 12:20 PM. Reason: please use [code] tags


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Program Optimization

    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.
    Last edited by Norm; September 29th, 2012 at 11:27 AM.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  4. #4
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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.

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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:
    		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?
    If you don't understand my answer, don't ignore it, ask a question.

  6. #6
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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:
    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)
    Last edited by Norm; September 29th, 2012 at 01:15 PM.
    If you don't understand my answer, don't ignore it, ask a question.

  8. #8
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Program Optimization

    here is the missing class:
    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

  9. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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?
    Last edited by Norm; September 29th, 2012 at 02:00 PM.
    If you don't understand my answer, don't ignore it, ask a question.

  10. #10
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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

  11. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Program Optimization

    What about the other questions and issues in my last post?
    If you don't understand my answer, don't ignore it, ask a question.

  12. #12
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  13. #13
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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

  14. #14
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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?
    Last edited by Norm; September 29th, 2012 at 02:33 PM.
    If you don't understand my answer, don't ignore it, ask a question.

  15. #15
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  16. #16
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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
    If you don't understand my answer, don't ignore it, ask a question.

  17. #17
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  18. #18
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Program Optimization

    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?
    Last edited by Norm; September 29th, 2012 at 03:15 PM.
    If you don't understand my answer, don't ignore it, ask a question.

  19. #19
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  20. #20
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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
    If you don't understand my answer, don't ignore it, ask a question.

  21. #21
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  22. #22
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Program Optimization

    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.?
    If you don't understand my answer, don't ignore it, ask a question.

  23. #23
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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

  24. #24
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default 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.?
    If you don't understand my answer, don't ignore it, ask a question.

  25. #25
    Junior Member
    Join Date
    Sep 2012
    Posts
    15
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Program Optimization

    7 would only beat 8

Page 1 of 2 12 LastLast

Similar Threads

  1. Circular prime checking algorithm optimization.
    By aesguitar in forum Algorithms & Recursion
    Replies: 5
    Last Post: July 26th, 2012, 11:35 AM
  2. Recursive Fibonacci sequence optimization
    By aesguitar in forum Algorithms & Recursion
    Replies: 2
    Last Post: June 24th, 2012, 08:49 AM
  3. Java Quick Sort Optimization
    By javaNewb37 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 4th, 2011, 07:32 AM
  4. A Star Pathfinding algorithm optimization
    By randomcracker in forum Algorithms & Recursion
    Replies: 4
    Last Post: May 18th, 2011, 11:11 PM
  5. Swing app gui optimization
    By nik_meback in forum AWT / Java Swing
    Replies: 1
    Last Post: December 6th, 2010, 12:55 PM