優化的算法[編譯準備代碼]從遊戲視角（撲克）

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

一些EXPL anation：

• 創建組合

我們創造一些子方法在爲它的下芯片的芯片貿易。所以 例如黑色= 2藍色。然後我們按順序創建5個循環。 第一個檢查是否還有黑色芯片，如果是的話減少1個黑色 加2個藍色。如果新ChipSet中 芯片的總和等於原始ChipSets值，則將此新組合保存在列表中。循環 繼續，直到沒有黑人了。然後檢查 是否是藍色，並重復相同的過程，直到沒有紅色 了。現在我們列出了所有可能的X值在 芯片中的變化。

• 過濾器組合

您篩選基於 芯片組，如果你可以與他們交X點，而不需更換。我們遍歷所有 在前一部分中創建的ChipSets的可能組合。如果您 可以使用ChipSet支付而無需交換將其添加到ChipSets的filteredList 。結果是隻有有效ChipSets的filered列表。

• 計算差異

對於每個芯片組，我們統計所有顏色的芯片的芯片組 的數量和的。減去芯片的芯片組原數量與它。 你拿這個的絕對值，並把所有那些原來的和組合色差的總和都加上 。現在我們有一個 數字，表示與原始數據的差異。現在我們所有的 所要做的就是比較所有ChipSets的參賽者數量。我們用來分配給玩家的差異最小的一個 。

所以它基本上做的是：它首先檢查當前的ChipSet是否可以用來支付並返回一個布爾值，就像你問的那樣。如果可以的話，它不會做任何事情，否則它會通過3個子算法並定義最好的ChipSet（一個能夠用來支付和最少的一個），並更改播放器ChipSet it

所以現在我的問題是什麼，我將如何開始優化？我這樣問，因爲當有更大的輸入時，算法很容易使用幾秒鐘。

Answer 1

讓我告訴你如何找到問題。這是做什麼：

讓它運行，並點擊「暫停」。顯示調用堆棧。點擊每個級別，它會向您顯示一行代碼，其中某個方法/函數A調用某個B，並且從上下文可以看出原因。把所有這些原因放在一起，你完全理解爲什麼這個時間點正在被花費。現在問自己：「有沒有辦法避免這樣做，至少在某些時候？」現在，不要馬上採取行動。再稍微停頓一下，以同樣的方式研究每一個。

現在，如果你看到了這樣一個你可以避免做的事情，而且你看到的不僅僅是一個樣本，那麼你應該修復它，你會看到一個很大的加速，保證。現在有一個好消息：如果你再次這樣做，你會看到你已經暴露了其他的東西，這也可以讓你加速。這一直持續到它停止，然後你的代碼幾乎是最佳的，因爲你可以做到這一點。關於你發佈的圖片，我多次解釋了很多次why that does not work。

如果你這樣做，你可以找到任何配置文件可以找到，並有很多他們不能。 原因很簡單 - 歸結爲描述事物。

• 什麼是函數的包含時間百分比？它是包含該函數的調用堆棧樣本的一小部分。

• 什麼是函數的自我時間百分比？這是包含末尾處的函數調用堆棧樣本的一小部分。

• 什麼是代碼行的包含時間百分比（而不是函數）？它是包含該行代碼的調用堆棧樣本的一小部分。

• 如果您查看調用圖，函數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

對應用程序進行簡要分析以查看哪些方法的準確度最高。例如：

嘗試優化那些你知道是瓶頸的方法和reprofile，直到你的瓶頸了。