Optimizing an algorithm [compile ready code]

Question

Problem from game perspective (Poker)

The player has 2 green chips (5 points) and 1 blue (10 points). This totals 20 points. Now the player want to buy a ingame icon that costs 16 points. The player has enough money to buy the item. So the player pays 16 points, but what points will he give to the shop to pay correctly.

Now I've written a working example with all of the work done.

Code

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

Some explanation:

• Create combinations

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.

• Filter combinations

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.

• Calculate difference

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.

So what it basically does is: It checks first if the current ChipSet can be used to pay and returns a boolean just like you asked. If it can it doesn't do anything, otherwise it goes through the 3 sub-algorithms and defines the best ChipSet (one to able to use to pay and least different one) and changes the players ChipSet the it

So now what is my question, how would I start to optimize this? I ask this because when there are bigger inputs the algorithm easily uses a few seconds.

Answer 1

Profile the application a few times to see which methods take the most time with accuracy. For example:

Try to optimize those methods which you know are the bottlenecks and reprofile until your bottlenecks are out.

Answer 2

Let me tell you how to find the problem(s). Here's what to do:

Get it running and hit "pause". Display the call stack. Click on each level, and it will show you a line of code where some method/function A calls some B, and the reason why is evident from the context. Put all those reasons together, and you understand completely why that point in time was being spent. Now ask yourself "Is there any way to avoid doing this, at least some of the time?" Now, don't act on that right away. Take a few more pauses and study each one the same way.

Now, if you saw such a thing you could avoid doing, and you saw it on more than just one sample, then you should fix it, and you will see a substantial speedup, guaranteed. Now comes the good news: If you do it all again, you will see that you've exposed something else, that can also give you a speedup. This continues until it stops, and then your code is about as nearly optimal as you can make it. Regarding the picture you posted, I've explained many many times why that does not work.

If you do this, you can find anything profilers can find, and plenty that they can't. The reason is very simple - it comes down to describing things.

• What is inclusive time percent of a function? It is the fraction of call stack samples containing that function.

• What is self time percent of a function? It is the fraction of call stack samples containing that function at the end.

• What is inclusive time percent of a line of code (as opposed to a function)? It is the fraction of call stack samples containing that line of code.

• If you look at a call graph, what is the time percent of a link in the graph between functions A and B? It is the fraction of call stack samples in which A is directly calling B.

• What is CPU time? It is the time you get if you ignore any samples taken during I/O, sleep, or any other such blocking?

So, if you are examining stack samples yourself, you can locate anything a profiler can locate, just by looking. You can also locate things that the profiler cannot, such as:

• Seeing that a large fraction of time is spent allocating memory for objects that a short time later are simply deleted.

• Seeing that a function is being called multiple times with the same arguments, only because the programmer was too lazy to declare a variable to remember the prior result.

• Seeing in a 20-level stack sample that a seemingly innocuous function was being called at the 10th level, that the programmer never imagined would be doing file I/O at the 20th level for some obscure reason that its writer couldn't rule out, but you know is not necessary.

• Seeing that there are a dozen different functions all doing the same thing but they are different functions because their owner classes have been templated.

• Seeing that there is a frequent pattern of function P calling something but then calling R, where P is called from lots of different places, and R calls down to lots of different places.

You can easily see any of these things, and more, just by examining the samples yourself. Now, the average number of samples it takes to see them depends on how big they are. If something takes 50% of time, the average number of samples needed to see it twice is 2/0.5 = 4 samples, so if you take 10 samples you are sure to see it.

Suppose there was another thing taking 25% of time. Now after fixing the first problem and cutting the time in half, the second one takes 50%, not 25%, so it, too, is easy to find.

This is how fixing one speedup exposes the next one. But as soon as you fail to find a speedup that's really there, the whole process stops, because you stop exposing the ones that are initially small but become really important when the bigger ones are removed.

Profilers give you precise measurements, but what are they measurements of? (Actually, that precision is fake. All those measurements have standard errors, which you are not shown.) What are they measurements of? Only very simple stuff, actually. There's no way they can recognize the kind of stuff you can recognize, since you know the code. I have had academic profiler fans insist to me that any problem you can find, you can find with a profiler, but that is not a theorem. There is no justification for it at all, theoretical or practical. There are plenty of problems that can escape from profilers. It's a case of "out of sight - out of mind".

"Gee, I ran the profiler on my code, but I couldn't see any bottlenecks, so I guess there aren't any."

If you're serious about performance, you've got to do better than that.