协助确定算法的执行时间

Question

创建以下程序是为了对一组排序的选票执行成对选举。

最终结果是让成对选举在不到 .01 秒的执行时间内完成所有测试用例。

目前程序最终结果时间性能约为 0.02 秒。 需要帮助将时间缩短到 0.01 秒或更短。

程序代码如下：

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 order list of candidates
     *
     * @param votersVotes
     *            an array of rank order 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 ordered 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();
        }
    }
}

感谢帮助！！

Answer 1

当前代码正在调用 getPlacement noCandidates*noCandidates*noVoters*2 次，但调用它 noCandidates*noVoters 次就足够了。

您可以通过预先计算值并像这样存储它们来管理它（不确定它是否正在编译，因为我不在 java 上编程，但我想您可以理解）：

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;
    }

    int[][] placements = new int[noVoters][noCandidates]; // to store precalculated placements

    // go through each of the voters and precalculate the placements of each candidate
    for (int voter = 0; voter<noVoters; voter++) {

        for (int candidate = 0; candidate < noCandidates; candidate++) {

            placements[voter][candidate] = getPlacement(candidate, votes[voter]);
        }
    }

    // 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++) {

                // use precalculated placements
                if (placements[voter][candidate1] < placements[voter][candidate2]) {

                    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;
}