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.

• Charlie: Check if the input isn't big and let another algorithm handle that ;) if(input<big){ alg0(); } else { alg1(); }
• ManyQuestions: Lol Charlie, are you making fun of me :p
• Charlie: Well, you said "Simple huh", yes, it's really simple
• ManyQuestions: @Brendan I looked up the theory around it and I think you're right. "there is no efficent (better than polynomial time proportional to number of inputs)". Which leaves me with optimizing some bottlenecks. Thanks for all the input guys, I can do quite a while with this.
• ManyQuestions: @Brendan I made one major improvement already, I will post it tomorrow. Thanks for taking the time help someone with 1 year of Java experience (programming in general).

Answer 1

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

enter image description here

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

• Mike Dunlavey: This kind of summary is not what will help you. 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...
• Mike Dunlavey: ... 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. Here's one example.
• ManyQuestions: @MikeDunlavey From what I've been reading, it seems like you know wha you're talking about. Maybe you can copy paste the above text into an answer then I can delete this 'wrong answer'
• Mike Dunlavey: OK, but I' m afraid I "ran on" a bit too much.

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.

• ManyQuestions: Well thanks for the interesting read. Aswell as your other 'articles'. Have you written a book? If not you should.
• Mike Dunlavey: @ManyQuestions: Thanks. I did, actually. It only spends a few pages on this topic. I didn't think there was that much to say. If you have an email, I'll send you a scanned copy. It's about 17mb.
• ManyQuestions: How would I give you my email?
• Mike Dunlavey: @ManyQuestions: well, for instance, mine is on my SO home page, so you could send it to me that way. You can obfuscate it to try to prevent getting spam.
• ManyQuestions: I'd be happy if you'd send it to dubparties (gmail.com) :)