java中reverse的用法，java 變位詞,[Java教程]變位詞的查找（下）

[Java教程]變位詞的查找(下)

0 2017-04-09 12:00:46

本文也同步發表在我的公眾號“我的天空”

實現方案優劣的思考

java中reverse的用法、之前我們的實現方案的優點是一旦目標詞庫的簽名建立后，則變位詞的查找會變得簡單而快速；缺點是由于在生成目標詞庫時，要為每個詞都生成簽名，導致生成詞庫的時間會變慢，同時會消耗空間。對于那些沒有被查找到的字符串的簽名實際上是浪費的。

測試結果：在CPU為Inter Core i3-2328M，內存為6GB的PC上生成數量為1萬的目標詞庫平均時間為377毫秒，查找變位詞的平均時間為11毫秒。

第二種方案

在生成目標詞庫的時候并不生成簽名，而是在查找的時候生成簽名。

function search(str){

var mathstr="";

java transient關鍵字、for(var x in array_str){

//查找時生成簽名，再判斷簽名是否相同

if(get_sign(str)==get_sign(array_str[x])){

mathstr+=mathstr.length==0?array_str[x]:","+array_str[x];

}

}

java怎么查找字符串。return mathstr;? //返回找到的變位詞

}

測試結果：生成數量為1萬的目標詞庫平均時間為130毫秒，查找變位詞的平均時間為530毫秒。

該方案雖然提高了生成目標詞庫的速度，并節省空間，但是查找的速度太慢，與第一種方案相比較慢了約50倍。分析代碼發現每次查找都需要為目標詞庫重新建立一遍簽名，效率太過低下，考慮優化。

第二種方案的優化

針對第二種方案的不足之處，考慮做如下優化：如果兩個詞互為換位詞，那么這兩個詞的長度必定相同，同時組成這兩個詞的字母的asscii編碼之和也必定相同，因此在遍歷目標詞庫時，首先判定這兩個條件，如果滿足則再獲取其簽名來作比較。獲取字母的ascii編碼采用charCodeAt()函數。

java類的修飾詞、function search(str){

var mathstr="";

for(var x in array_str){

//如果兩個詞互為變位詞，那么這兩個詞的長度和各字母的asciicode之和必須相同

if(str.length==array_str[x].length && get_asciicode_total(str)==get_asciicode_total(array_str[x])){

//查找時判斷簽名是否相同

java共詞計算代碼？if(get_sign(str)==get_sign(array_str[x])){

mathstr+=mathstr.length==0?array_str[x]:","+array_str[x];

}

}

}

return mathstr;

Java變量、}

//獲得字符串的ascii碼之和

function get_asciicode_total(str){

var data=str.split("");

var i=0;

for(var x in data){

java中文變量名。i+=data[x].charCodeAt();

}

return i;

}

經測試，優化后的查找速度平均為43毫秒，速度提升還是很有效果的！

總結

java詞法分析。該題主要是偏向于對問題的思考、解決方案的制定、實現與選擇、代碼優化等方面，在實際工作中，往往一個問題的解決會有多套方案，大家應該學會從各方面來衡量、測試，最終選擇解決的問題的最優方案。該題主要涉及到隨機數的操作、排序算法的掌握、ascii編碼的掌握。

當然，以上兩種方案仍有優化的空間，對于第一種，可以考慮將簽名數組按照簽名來排序，這樣就無需每次都遍歷整個簽名數組，如果生成的目標詞庫數量巨大，還可以考慮將簽名數組分段索引，以便能更快的找到簽名；對于第二種，可以將查找中已生成的簽名保存下來，這樣下次查找再遇到該字符串該就無需再生成簽名了，因為在整個程序中，最影響性能的就是生成簽名，我們應盡量減少生成簽名的操作。

示例代碼

https://github.com/panyongwow/anagram

本文網址：http://www.shaoqun.com/a/306839.html

*特別聲明：以上內容來自于網絡收集，著作權屬原作者所有，如有侵權，請聯系我們：admin@shaoqun.com。

0