java - 优化算法 [编译就绪代码]

Question

游戏角度的问题(扑克)

玩家有 2 个绿色筹码(5 分)和 1 个蓝色筹码(10 分)。这总计20分。现在玩家想要购买一个值(value) 16 点的游戏内图标。玩家有足够的钱购买元素。所以玩家支付了16个积分，但是他会给店铺多少积分才能正确支付。

现在，我已经完成了所有工作，并编写了一个工作示例。

代码

程序.java

import java.util.Arrays;

public class Program {

    public static void main(String[] args) {
        // Setting up test environment
        Player player = new Player("Borrie", new int[]{0,0,0,0, 230});
        int itemCost = 16626;
        // Pay for item
        System.out.printf("First we check if the player can pay with it's current ChipSet");
        if (!player.canPayWithChipSet(player.getChips(), 5)) {
            if (player.exchangeChips(5)) {
                System.out.printf("\n\nThe players ChipSet:" + Arrays.toString(player.getChips().chips));
                System.out.printf("\nThe players ChipSet has been succesfully exchanged.");
            } else {
                System.out.printf("\n\nThe players ChipSet:" + Arrays.toString(player.getChips().chips));
                System.out.printf("\nThe players ChipSet was not able to be exchanged.\n");
            }
        } else {
            System.out.printf("\n\nThe player can pay exact with it's original ChipSet. No need to exchange.");
        }

    }
}

播放器.java

import java.util.ArrayList;
import java.util.Arrays;

public class Player {

    private String name;
    private ChipSet chips;
    private int points = 0;

    public Player(String name, int[] chips) {
        this.name = name;
        this.chips = new ChipSet(chips);
        this.points = this.chips.getSum();
    }

    public boolean exchangeChips(int cost) {
        ChipSet newChipSet = exchangePlayerChipSet(this.chips.getChips(), cost);
        if (newChipSet == null) {
            return false;
        }

        this.chips = newChipSet;
        return true;
    }

    public ChipSet exchangePlayerChipSet(int[] originalChipValues, int cost) {
        ChipSet newChipSet = null;

        // Create possible combinations to compare
        ArrayList<ChipSet> chipSetCombos = createCombinations(this.chips.getChips());

        // Filter the chipset based on if it's able to pay without changing chips
        System.out.printf("\n\n---- Filter which of these combinations are able to be payed with without changing chips ----");
        ArrayList<ChipSet> filteredCombos = filterCombinations(chipSetCombos, cost);

        // Compare the filtered chipsets to determine which one has changed the least
        if (!filteredCombos.isEmpty()) {
            newChipSet = compareChipSets(originalChipValues, filteredCombos);
        }
        return newChipSet;
    }

    private ArrayList<ChipSet> createCombinations(int[] array) {
        ArrayList<ChipSet> combos = new ArrayList<>();
        int[] startCombo = array;
        System.out.printf("Player has " + getTotalPoints(startCombo) + " points in chips.");
        System.out.printf("\nPlayer has these chips (WHITE,RED,GREEN,BLUE,BLACK): " + Arrays.toString(startCombo));

        while (startCombo[4] != 0) {
            startCombo = lowerBlack(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[3] != 0) {
            startCombo = lowerBlue(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[2] != 0) {
            startCombo = lowerGreen(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        while (startCombo[1] != 0) {
            startCombo = lowerRed(startCombo);
            if (getTotalPoints(startCombo) == points) {
                combos.add(new ChipSet(startCombo));
            }
        }
        System.out.printf("\n\n---- Creating variations on the players chips ----");
        System.out.printf("\nVariation (all worth " + getTotalPoints(startCombo) + " points):\n");

        int counter = 1;
        for (ChipSet a : combos) {
            System.out.printf("\nCombo " + counter + ": " + Arrays.toString(a.getChips()));
            counter++;
        }
        return combos;
    }

    private ArrayList<ChipSet> filterCombinations(ArrayList<ChipSet> combinations, int cost) {
        ArrayList<ChipSet> filteredChipSet = new ArrayList<>();
        combinations.stream().filter((cs) -> (canPayWithChipSet(cs, cost))).forEach((cs) -> {
            filteredChipSet.add(cs);
        });
        return filteredChipSet;
    }

    // This method has be worked out
    public boolean canPayWithChipSet(ChipSet cs, int cost) {
        ChipSet csOrig = new ChipSet(cs.chips);
        ChipSet csCopy = new ChipSet(cs.chips);
        int counterWhite = 0, counterRed = 0, counterGreen = 0, counterBlue = 0, counterBlack = 0;

        while (20 <= cost && cost > 0 && csOrig.getChips()[4] != 0) {
            csOrig.getChips()[4] -= 1;
            cost -= 20;
            counterBlack++;
        }
        while (10 <= cost && cost > 0 && csOrig.getChips()[3] != 0) {
            csOrig.getChips()[3] -= 1;
            cost -= 10;
            counterBlue++;
        }
        while (5 <= cost && cost > 0 && csOrig.getChips()[2] != 0) {
            csOrig.getChips()[2] -= 1;
            cost -= 5;
            counterGreen++;
        }
        while (2 <= cost && cost > 0 && csOrig.getChips()[1] != 0) {
            csOrig.getChips()[1] -= 1;
            cost -= 2;
            counterRed++;
        }
        while (1 <= cost && cost > 0 && csOrig.getChips()[0] != 0) {
            csOrig.getChips()[0] -= 1;
            cost -= 1;
            counterWhite++;
        }

        if (cost == 0){
            System.out.printf("\nCombo: %s can pay exact. With %d white, %d red, %d green, %d blue an %d black chips", Arrays.toString(csCopy.chips),counterWhite,counterRed,counterGreen,counterBlue,counterBlack);
            return true;
        } else {
            System.out.printf("\nCombo: %s cannot pay exact.\n\n\n", Arrays.toString(csCopy.chips));
            return false;
        }    
    }

    private ChipSet compareChipSets(int[] originalChipValues, ArrayList<ChipSet> chipSetCombos) {
        ChipSet newChipSet;
        int[] chipSetWaardes = originalChipValues; // originele chipset aantal van kleur
        int[] chipSetCombosDifferenceValues = new int[chipSetCombos.size()];
        int counter = 1;

        System.out.printf("\n\n---- Calculate differences between players stack and it's variations ----");
        for (ChipSet cs : chipSetCombos) {
            int amountWhite = cs.getChips()[0];
            int amountRed = cs.getChips()[1];
            int amountGreen = cs.getChips()[2];
            int amountBlue = cs.getChips()[3];
            int amountBlack = cs.getChips()[4];
            int differenceWhite = Math.abs(chipSetWaardes[0] - amountWhite);
            int differenceRed = Math.abs(chipSetWaardes[1] - amountRed);
            int differenceGreen = Math.abs(chipSetWaardes[2] - amountGreen);
            int differenceBlue = Math.abs(chipSetWaardes[3] - amountBlue);
            int differenceBlack = Math.abs(chipSetWaardes[4] - amountBlack);
            int totalDifference = differenceWhite + differenceRed + differenceGreen + differenceBlue + differenceBlack;
            chipSetCombosDifferenceValues[counter - 1] = totalDifference;
            System.out.printf("\nCombo " + counter + ": " + Arrays.toString(cs.getChips()) + " = " + totalDifference);
            counter++;
        }
        newChipSet = chipSetCombos.get(smallestValueOfArrayIndex(chipSetCombosDifferenceValues));
        System.out.printf("\n\nThe least different ChipSet is: " + Arrays.toString(newChipSet.getChips()) + " ");

        return newChipSet;
    }

    private int smallestValueOfArrayIndex(int[] array) {
        int currentValue = array[0];
        int smallestIndex = 0;
        for (int j = 1; j < array.length; j++) {
            if (array[j] < currentValue) {
                currentValue = array[j];
                smallestIndex = j;
            }
        }
        return smallestIndex;
    }

    private int[] lowerBlack(int[] array) {
        return new int[]{array[0], array[1], array[2], array[3] + 2, array[4] - 1};
    }

    private int[] lowerBlue(int[] array) {
        return new int[]{array[0], array[1], array[2] + 2, array[3] - 1, array[4]};
    }

    private int[] lowerGreen(int[] array) {
        return new int[]{array[0] + 1, array[1] + 2, array[2] - 1, array[3], array[4]};
    }

    private int[] lowerRed(int[] array) {
        return new int[]{array[0] + 2, array[1] - 1, array[2], array[3], array[4]};
    }

    private int getTotalPoints(int[] array) {
        return ((array[0] * 1) + (array[1] * 2) + (array[2] * 5) + (array[3] * 10) + (array[4] * 20));
    }

    public String getName() {
        return this.name;
    }

    public int getPoints() {
        return this.points;
    }

    public ChipSet getChips() {
        return chips;
    }

}

芯片组.java

public class ChipSet {

    public static final int WHITE_VALUE = 1;
    public static final int RED_VALUE = 2;
    public static final int GREEN_VALUE = 5;
    public static final int BLUE_VALUE = 10;
    public static final int BLACK_VALUE = 20;

    public static final int[] VALUES = new int[]{WHITE_VALUE, RED_VALUE, GREEN_VALUE, BLUE_VALUE, BLACK_VALUE};

    protected int[] chips;

    public ChipSet(int[] chips) {
        if (chips == null || chips.length != 5) {
            throw new IllegalArgumentException("ChipSets should contain exactly 5 integers!");
        }

        // store a copy of passed array
        this.chips = new int[5];
        for (int i = 0; i < this.chips.length; i++) {
            this.chips[i] = chips[i];
        }
    }

    public int getSum() {
        return chips[0] * WHITE_VALUE
                + chips[1] * RED_VALUE
                + chips[2] * GREEN_VALUE
                + chips[3] * BLUE_VALUE
                + chips[4] * BLACK_VALUE;
    }

    public int[] getChips() {
        return this.chips;
    }
}

一些解释:

• 创建组合

We create some submethods the trade a chip in for it's lower chip. So for example black = 2 blues. Then we create 5 loops in order. The first ones checks if there are still black chips, if so reduce 1 black add 2 blues. Save this new combination in a list if the sum of the chips in the new ChipSet equals the original ChipSets value. Loop continues until there are no blacks anymore. Then it check if there are blues and repeats the same process until there are no reds anymore. Now we have list with all possible variations of X value in chips.

• 过滤器组合

You filter the ChipSets based on if you can pay X points with them without exchanging. We loop over all possible combinations of ChipSets created in the previous part. If you can pay with the ChipSet without exchanging add it to the filteredList of ChipSets. The result is a filered list with only valid ChipSets.

• 计算差异

For each ChipSet we count the number of chips of all colors in a ChipSet and substract the original chipset number of chips with it. You take the absolute value of that and make a sum of all those differences of the original and the combos colors. Now we have a number that represents the difference from the original. Now all we have to do is compare all the ChipSets ´difference number´. The one with the least difference we use to assign to the player.

所以它基本上做的是:它首先检查当前的 ChipSet 是否可以用于支付，然后像你问的那样返回一个 boolean 值。如果可以，它什么都不做，否则它会通过 3 个子算法并定义最佳 ChipSet(一个能够用于支付，另一个最不相同)并更改播放器 ChipSet

那么现在我的问题是什么，我将如何开始优化它？我问这个是因为当有更大的输入时，算法很容易使用几秒钟。

Answer 1

对应用程序进行几次分析，以准确了解哪些方法花费的时间最多。例如:

尝试优化那些你知道是瓶颈的方法并重新分析，直到你的瓶颈被解决。