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

Question

从游戏角度看问题(扑克)

球员有2个绿色筹码(5分)和1个蓝色(10分)。这总共是20分。现在玩家想买一个花销16分的图标。这位玩家有足够的钱买这个东西。因此，球员支付16分，但他会给商店支付正确的分。

现在，我已经用所有的工作编写了一个工作示例。

码

Program.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.");
        }

    }
}

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

}

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

一些解释：

• 创建组合

我们创造了一些子方法，用一个芯片来换取更低的芯片。例如，黑色=2个蓝色。然后我们按顺序创建5个循环。第一个检查是否仍然有黑色芯片，如果是减少1个黑色加2个蓝调。如果新ChipSet中的芯片之和等于原始ChipSets值，则将此新组合保存在列表中。循环继续，直到不再有黑人。然后，它检查是否有蓝调和重复相同的过程，直到没有红色。现在我们已经列出了芯片中X值的所有可能的变化。

• 滤波器组合

如果您可以在不交换的情况下使用X点支付X点，则可以过滤ChipSets。我们循环处理在前一部分中创建的所有可能的ChipSets组合。如果您可以在不交换的情况下使用ChipSet进行支付，则将其添加到filteredList of ChipSets。结果是一个只有有效ChipSets的文件列表。

• 计算差

对于每个ChipSet，我们计算一个ChipSet中所有颜色的芯片的数量，并用它减去原始芯片组的数目。你取它的绝对值，然后把原始颜色和组合颜色的所有差异相加。现在，我们有了一个数字，表示与原来的差异。现在我们要做的就是比较所有的ChipSets‘差分数’。我们用来分配给玩家的差数最小的那个。

因此，它主要做的是:它首先检查当前的ChipSet是否可以用于支付，并按照您的要求返回一个布尔值。如果它不能做任何事情，那么它将通过三个子算法，定义最好的ChipSet (一个可以用来支付，另一个可以用最少的)，并更改玩家的ChipSet it。

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

Answer 1

让我告诉你如何找出这个问题。以下是该做的事情：

让它运行并点击“暂停”。显示调用堆栈。单击每个级别，它将向您显示一行代码，其中一些方法/函数A调用了一些B，并且从上下文中可以看出原因。把所有这些原因加在一起，你就会完全理解为什么那个时间点被花费了。现在扪心自问：“有没有办法避免这样做，至少在某些时候是这样的？”现在，不要马上采取行动。多休息几次，以同样的方式学习每一个。

现在，如果您看到了这样的事情，您可以避免这样做，并且您在不止一个示例上看到了它，那么您应该修复它，您将看到一个大幅度的加速，保证。好消息来了:如果你再做一次，你会发现你已经暴露了一些其他的东西，这也会让你加速。这种情况一直持续到停止，然后您的代码几乎是您所能做的最优的。关于你发的照片，我已经解释过很多次了，http://archive.today/9r927。

如果你这样做的话，你可以找到任何分析器能找到的东西，也可以找到很多他们找不到的东西。原因很简单--可以归结为描述事物。

• 函数的包含时间百分比是多少？它是包含该函数的调用堆栈示例的一部分。
• 函数的自我时间百分比是多少？它是在末尾包含该函数的调用堆栈示例的一部分。
• 代码行的包含时间百分比(相对于函数)是多少？它是包含这一行代码的调用堆栈示例的一部分。
• 如果你看一个调用图，函数A和B之间的链接的时间百分比是多少？它是A直接调用B的调用堆栈样本的一部分。
• CPU时间是多少？如果你忽略在I/O、睡眠或任何其他阻塞过程中采集的任何样本，那么这就是你得到的时间吗？

所以，如果你自己检查堆栈样本，你可以找到任何一个分析器可以找到的任何东西，只要看看。您还可以找到分析器无法找到的内容，例如：

• 看到很大一部分时间花在为短时间后被删除的对象分配内存时。
• 看到一个函数被用相同的参数多次调用，这只是因为程序员太懒，以至于不能声明变量来记住先前的结果。
• 在一个20层的堆栈示例中，看到一个看似无害的函数在第10层被调用，程序员从未想过会在第20层执行文件I/O，原因不明，它的作者无法排除，但您知道这是不必要的。
• 看到有十几个不同的函数都在做相同的事情，但是它们是不同的函数，因为它们的所有者类已经被模板化了。
• 注意到函数P调用某物的频繁模式，然后调用R，其中P被从许多不同的地方调用，R调用到很多不同的地方。

您可以很容易地看到任何这些东西，甚至更多，只要自己检查样本。现在，看到它们所需的平均样本数量取决于它们的大小。如果某物需要50%的时间，那么两次看到它所需的平均样本数是2/0.5 =4个样本，所以如果你取了10个样本，你肯定会看到它。

假设还有一件事花费了25%的时间。现在，在修复了第一个问题并将时间减半之后，第二个问题只需要50%，而不是25%，所以它也很容易找到。

这是如何修复一个加速比暴露下一个。但是，一旦你找不到真正存在的加速，整个过程就停止了，因为你不再暴露那些最初很小但当较大的那些被删除时变得很重要的那些。

分析器给你精确的测量，但是它们是什么的测量？(实际上，这种精确度是假的。所有这些测量都有标准误差，但没有显示。)他们测量的是什么？其实只是很简单的东西。他们不可能识别出你能识别的东西，因为你知道代码。我曾经有过学术侧写迷对我说，任何你能找到的问题，你都可以用剖析器找到，但这不是一个定理。无论是理论上还是实践上，都没有理由这样做。有很多问题可以从分析器中解脱出来。这是个“看不见-心不在焉”的例子。

“哎呀，我在我的代码上运行了分析器，但是我看不到任何瓶颈，所以我想没有瓶颈。”

如果你是认真的表现，你必须做得更好。

Answer 2

对应用程序进行几次概要分析，以查看哪些方法花费的时间最多，而且精度较高。例如：

​

​

尝试优化那些您知道是瓶颈的方法，并重新配置，直到瓶颈解决为止。