805
java也能寫出點點算法-像C++一樣去優化核心並發的代碼例子1
java其實更多用來寫業務代碼，代碼寫得好不好，關鍵看抽象能力如何，不過如果你要用java寫很核心的插件和高並發的片段，那麼可能還是需要注意一些寫法，那種寫法可能會更好，才能使得並發量提高，而且更少的使用CPU和內存；我最近在一段采集係統訪問的java代碼，通過過濾器切入到應用中，遇到的一些小細節的調整，感覺還有點意思，以下為收集信息中碰到的兩個需要判定的地方（對java優化沒有任何要求的，本文純屬扯淡，嗬嗬）：
原始代碼片段1（用於判定是否為靜態資源）：
if(servletPath == null
|| servletPath.endsWith(".gif")
|| servletPath.endsWith(".png")
|| servletPath.endsWith(".jpg")
|| servletPath.endsWith(".bmp")
|| servletPath.endsWith(".js")
|| servletPath.endsWith(".css")
|| servletPath.endsWith(".ico")) return true;
原始代碼片段2（用於判定瀏覽器類型）：
if(StringUtils.isEmpty(userAgent)) return null;
if(userAgent.contains("MetaSr")) return "metasr";
if(userAgent.contains("Chrome")) return "chrome";
if(userAgent.contains("Firefox")) return "firefox";
if(userAgent.contains("Maxthon")) return "maxthon";
if(userAgent.contains("360SE")) return "360se";
if(userAgent.contains("Safari")) return "safari";
if(userAgent.contains("opera")) return "opera";
if(userAgent.contains("MSIE")) return "ie";
貌似一眨眼的樣子，這個代碼沒啥優化的餘地，代碼片段1無非是將出現概率高的放在前麵，就盡快判定成功，片段2也是這樣，但是片段1裏頭其實有很多請求都不是靜態資源，不是靜態資源的話就會將7個endwith全部執行一遍下來了，也就是有很多很多的請求都將遍曆所有的內容。
endWith做什麼？看看源碼，就是將字符串最後那部分截取下來（截取和對比串一樣長的，然後和對比串對比），那麼7個就會發生7次substring，每個substring操作將會生成一個新的java對象（這個大家應該清楚），每個字符串進行對比是按照字符對比的，所以按照4個四個字符進行計算，也就是會發生20多次對比操作（最壞情況），當然說最好的情況就是進行一次substring，4次對比操作（因為對比成功是每個字符對比成功才算成功）。
那麼怎麼優化呢，這個貌似除了調試順序，沒有太多優化的空間，根據數據你會發現一個規律，對比的結束字符有5種可能性，那麼通過結束字符，就可以定位到一到兩個字符串上麵，所以我們第一個考慮就是取出要對比的那個字符串的結束符，看下結束符是那個字符串的結束符，然後就在一兩個字符串上使用endWith，那麼概率就很低了，於是乎，我們對代碼片段1，做第一步優化就是：
if(servletPath == null) return false;
int length = servletPath.length();
char last = servletPath.charAt(length - 1);
if((last == 'f' && servletPath.endsWith(".gif"))
|| (last == 'g' && (servletPath.endsWith(".png") || servletPath.endsWith(".jpg")))
|| (last == 'p' && servletPath.endsWith(".bmp"))
|| (last == 's' && (servletPath.endsWith(".js")|| servletPath.endsWith(".css")))
|| (last == 'o' && servletPath.endsWith(".ico"))) return true;
此時判定完首字母後，就使用最多2個字符串進行endWith操作，經過測試，在上麵最壞的情況下，效率要高出5-8倍，最初的寫法在最好的情況下，和現在速度基本保持一致，但是我們上麵說了，很多請求都不是靜態資源，所以有很多請求都是走的最壞情況。
好了，如果你的代碼不需要極高級別的優化，走到這一步已經夠用了，或者說這個已經非常非常夠用了，雖然優化的思路非常簡單，再寫就寫成C++了；嗬嗬，不過我喜歡鑽牛角尖，我也有點點潔癖，就是要玩什麼，就喜歡玩到我認為的至高境界，所以我又再進行分析，畫個圖看看：
想辦法是否可以去掉subtring的操作，也就是不做字符串截取的操作，我看到就那麼幾個字母，那麼就匹配幾個字母而已嘛！
於是乎代碼有點像C寫的了，做了進一步的改動：
if(servletPath == null) return false;
int length = servletPath.length();
if(length < 3) return false;
char last = servletPath.charAt(length - 1);
char second = servletPath.charAt(length - 2);
char third = servletPath.charAt(length - 3);
char forth;
if(length > 3 && third != '.')
forth = servletPath.charAt(length - 4);
else
forth = 0;
if((last == 'f' && second == 'i' && third == 'g' && forth == '.')
|| (last == 'g' && ((second == 'n' && third == 'p' && forth == '.') || (second == 'p' && third == 'j' && forth == '.')))
|| (last == 'p' && (second == 'm' && third == 'b' && forth == '.'))
|| (last == 's' && ((second == 'j' && third == '.')|| (second == 's' && third == 'c' && forth == '.')))
|| (last == 'o' && (second == 'c' && third == 'i'))) return true;
改動後的代碼，更加像低級語言在寫代碼，嗬嗬，不過效率的確提高了一些，這個時候提高就不是太明顯了，隻是減少substring創創建中間對象生成時間，能到這一步，我想很少有人再去想了，但是但是代碼潔癖超級高的話，還會去想，五個字符，最壞情況要匹配5次才能找到自己想要的入口，有沒有辦法一次性找到，還有，找到後通過路徑直接匹配到內容，回到那個圖上，看到很像圖形結構
首先考慮入口應該如何處理？看到入口全是字母，這些字母的ascii都是數據0-127的，所以我們想直接用字母的ascii作為下標，我們姑且浪費點空間，創建一個長度為128的數組，使用結束字母ascii作為入口位置；
再考慮，進入後該如何算？我們就想通過圖上的路由，最終可以找到最後一個字符的就是成立的，此時設計到子節點的查找，理論上這樣是最快的，但是，實現起來每一層需要循環到自己要的那個路由，循環體本身對CPU的開銷也是有的，而且要構造對象和指針來實現，訪問數據需要通過間接訪問，理論上的最優化，並不是我們想要的最優，但是我們的優化到此結束了嗎？不是，算法行不通，我更喜歡鑽牛角尖了，嗬嗬，
怎麼解決第二步無法完成的情況呢？我考慮到雖然不能按照圖的結構完成，那麼我發現開始字符都是 "."將它拋開算，如果入參不是這樣直接錯誤，另外，剩餘的字符，就隻有1-2個字符，而且這個字符的ascii都是數據0-127的，我驚喜了，0-127就是在byte的範圍內，我可以組織成任何我想要的內容，我此時將兩個字符，按照byte拚接，就可以拚接為2個byte位的數字，也就是short int 類型，因為java在JVM內核實現中其實在局部變量中都是一樣大的，所以我們就直接用int了，如果int和int匹配就是一個compare，而不是按照每個字符去compare了；
再發現，上麵的圖結構中，按照路由向下走，每個入口下麵最多2個可匹配的內容，所以我們就定死一個結構就是一個入口下兩個int，默認為-1，如下（我這裏定義的是內部類，寫成static是為了靜態方法調用）：
static class TempNode {
int c1 = -1;
int c2 = -1;
}
OK，開始嚐試，首先我們初始化我們需要進行對比的信息，就像編譯時完成一些東西一樣：
我們首先初始化一個128長度的數組：
private static TempNode[] tempNode1 = new TempNode[128];
private static void addNode(char []chars) {
int b = (int)chars[0];
TempNode node = tempNode1[b];
if(node == null) {
node = new TempNode();
tempNode1[b] = node;
}
int size = chars.length;
int tmp = 0;
if(size == 2) {
tmp = (int)(chars[1]);
}else if(size == 3) {
tmp = (int)(chars[1] << 8 | chars[2]);
}
if(node.c1 == -1) node.c1 = tmp;
else node.c2 = tmp;
}
static {
addNode(new char[] {'f' , 'i' , 'g'});
addNode(new char[] {'g' , 'n' , 'p'});
addNode(new char[] {'g' , 'p' , 'j'});
addNode(new char[] {'p' , 'm' , 'b'});
addNode(new char[] {'s' , 'j'});
addNode(new char[] {'s' , 's' , 'c'});
addNode(new char[] {'o' , 'c' , 'i'});
}
這部分訪問這個類的時候，就會被初始化掉，初始化的目的就是為了可以被反複使用，而沒有將這部分運算時間拋開掉了；此時怎麼運算呢？代碼描述如下：
1、取出訪問字符最後一個字母，根據ascii到tempNode1取出對象，如果對象為空，則就沒有任何匹配的，直接返回錯誤。
2、倒轉訪問字符，如果長度超過3個，且第三個字符不是“.”，則看第四個字符是不是“.”。
3、上述成立後，根據字符長度拚接處對應的int數據，與取出的TempNode對象中的兩個int值進行匹配，得到boolean類型的值返回。
實際代碼如下：
private static boolean testServletPath(String servletPath) {
int length = servletPath.length();
char last = servletPath.charAt(length - 1);
TempNode node = tempNode1[(int)last];
if(node == null) return false;
char second = servletPath.charAt(length - 2);
char third = servletPath.charAt(length - 3);
char forth;
int tmp = -1;
if(length > 3 && third != '.') {
forth = servletPath.charAt(length - 4);
if(forth != '.') return false;
tmp = (int)(second << 8 | third);
}else if(third != '.') {
return false;
}else {
forth = 0;
tmp = second;
}
return tmp == node.c1 || tmp == node.c2;
}
我想這已經快到極點了，可以看到上麵有進行 ‘.’ 的compare，也就是多進行操作了，那麼是否可以直接將這個字符也放入到int中呢，int本身還有2個byte的空位，是的，可以這樣做，但是會增加一次位偏移操作，所以和多一次判定，所以總體的效率會看不出多大的區別，但是也是可以那樣做的，因為你會發現compare操作會做2次。
也就是隻要能挖，在這種代碼中能挖出很多寶貝，在高並發的應用係統中，如果在極高並發的代碼段，尤其是無論任何程序都會經過的代碼段，而且經過多次的那種，那麼，這種優化就會產生總體上的提升。
最後，我們看看代碼片段2，其實和片段1類似，隻不過第一步是考慮endWith，第二個是contains，contarins其實有可能會更加慢，因為會在內部在到相應的字符做一次匹配；就像對比MSIE這個字符串，如果文本中出現多次M開頭就又要開始匹配，這裏將同一個文本和8種情況對比是很痛苦的事情，其實我們完全可以將上麵8個字符串的第一個字母取出來，後麵字符串作為byte位，最後組成一個long數據，代表一個數字，放在一個小數組中（此時就是用起始字符作為數組下標了）；然後，在使用傳入字符串時，每位進行位偏移，將數字和對應下標下的數組看看是否一致，一致就直接返回那個下標記錄下的常量，若不是就繼續向後了，也就是一遍掃描下來8個字符串可以對比到，而且每次內部對比的時候，就是一個簡單的數字對比而已，這就是一種優化。
不論不論怎麼說，優化還是歸結到能不做的就不做，能少做的就少做，能隻做一次就隻做一次！
最後更新：2017-04-02 22:16:36