ARTS 05

Algorithm [劍指offer] 丑數(shù)

本題是來自牛客網(wǎng)的【劍指Offer】中的丑數(shù)，其在互聯(lián)網(wǎng)公司校招出現(xiàn)概率較大，建議嘗試做一做。

題目描述
把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗|(zhì)因子7。 習(xí)慣上我們把1當(dāng)做是第一個丑數(shù)。求按從小到大的順序的第N個丑數(shù)。

public int GetUglyNumber_Solution(int index) {
        if(index <= 0)
            return 0;
        if(index == 1)
            return 1;
        int t2 = 0, t3 = 0, t5 = 0;
        int [] res = new int[index];
        res[0] = 1;
        
        for(int i = 1; i<index; i++){
            //下一個丑數(shù)肯定出現(xiàn)2 3 5 倍數(shù)中，取最小的
            res[i] = Math.min(res[t2]*2, Math.min(res[t3]*3, res[t5]*5));
            if(res[i] == res[t2]*2) t2++;
            if(res[i] == res[t3]*3) t3++;
            if(res[i] == res[t5]*5) t5++;
            
        }
        return res[index-1];
    }

解題思路
我們只求丑數(shù)，不要去管非丑數(shù)。每個丑數(shù)必然是由小于它的某個丑數(shù)乘以2，3或5得到的，這樣我們把求得的丑數(shù)都保存下來，用之前的丑數(shù)分別乘以2，3，5，找出這三這種最小的并且大于當(dāng)前最大丑數(shù)的值，即為下一個我們要求的丑數(shù)。這種方法用空間換時間，時間復(fù)雜度為O(n)。

Google如何跟蹤您的個人信息

每次互聯(lián)網(wǎng)搜索都包含關(guān)鍵字，而您剛剛輸入Google的關(guān)鍵字則由廣告客戶進(jìn)行爭奪。每個提供與您的關(guān)鍵字相關(guān)的產(chǎn)品的廣告客戶都希望看到并點(diǎn)擊其廣告。

點(diǎn)擊廣告后，您的信息會傳遞給搜索引擎營銷人員，并將其永久存儲在AdWords帳戶中，永遠(yuǎn)不會被刪除。
只要您使用Google，Google一直在為您構(gòu)建“公民資料”。

搜索引擎營銷的圣杯：多設(shè)備歸屬。當(dāng)這項(xiàng)技術(shù)得以實(shí)現(xiàn)時，廣告將無縫地跟蹤搜索者 - 不僅跨渠道（例如，社交，有機(jī)和電子郵件），而且跨設(shè)備（例如，從移動設(shè)備到平板電腦，從筆記本電腦到電視再到桌面）。

在手機(jī)上搜索產(chǎn)品，然后親自走進(jìn)商店。按此順序執(zhí)行此操作，Google可能會使用您手機(jī)的GPS數(shù)據(jù)來關(guān)聯(lián)您的廣告點(diǎn)擊和店內(nèi)購買。

今天，人們告訴谷歌他們在其他地方承認(rèn)的事情 - 不是他們的配偶，醫(yī)生或縮水。但是如果谷歌用戶了解這個兔子洞有多遠(yuǎn)，他們就不會對搜索引擎這么直率。有了我將提供的內(nèi)幕信息，我希望讀者可以回到谷歌不是唯一可以告訴他們的恐懼，遺憾，希望和夢想的地方。

TCP的TIME_WAIT機(jī)制

TIME_WAIT的產(chǎn)生條件：主動關(guān)閉方在發(fā)送四次揮手的最后一個ACK會變?yōu)門IME_WAIT狀態(tài)，保留次狀態(tài)的時間為兩個MSL（linux里一個MSL為30s，是不可配置的）

TCP.jpg

TIME_WAIT兩個MSL的作用：可靠安全的關(guān)閉TCP連接。比如網(wǎng)絡(luò)擁塞，主動方最后一個ACK被動方?jīng)]收到，這時被動方會對FIN開啟TCP重傳，發(fā)送多個FIN包，在這時尚未關(guān)閉的TIME_WAIT就會把這些尾巴問題處理掉，不至于對新連接及其它服務(wù)產(chǎn)生影響。

MSL概念：MSL指的是報(bào)文段的最大生存時間，如果報(bào)文段在網(wǎng)絡(luò)活動了MSL時間，還沒有被接收，那么會被丟棄。

TIME_WAIT占用的資源：少量內(nèi)存（查資料大概4K）和一個fd。

TIME_WAIT關(guān)閉的危害：

  • 1、 網(wǎng)絡(luò)情況不好時，如果主動方無TIME_WAIT等待，關(guān)閉前個連接后，主動方與被動方又建立起新的TCP連接，這時被動方重傳或延時過來的FIN包過來后會直接影響新的TCP連接；

  • 2、 同樣網(wǎng)絡(luò)情況不好并且無TIME_WAIT等待，關(guān)閉連接后無新連接，當(dāng)接收到被動方重傳或延遲的FIN包后，會給被動方回一個RST包，可能會影響被動方其它的服務(wù)連接。

TCP: time wait bucket table overflow產(chǎn)生原因及影響：原因是超過了linux系統(tǒng)tw數(shù)量的閥值。危害是超過閥值后﹐系統(tǒng)會把多余的time-wait socket 刪除掉，并且顯示警告信息，如果是NAT網(wǎng)絡(luò)環(huán)境又存在大量訪問，會產(chǎn)生各種連接不穩(wěn)定斷開的情況。

解決辦法：

  • 可以嘗試縮小它的設(shè)置，比如十秒，甚至一秒，具體設(shè)置成多少合適取決于網(wǎng)絡(luò)情況而定，當(dāng)然也可以參考相關(guān)的案例。

  • TIME_WAIT總是在關(guān)閉發(fā)起方產(chǎn)生，服務(wù)端資源有限，可能同時連接上萬個連接，所以盡量由客戶端發(fā)起關(guān)閉請求，這樣產(chǎn)生的就都在客戶端

  • tcp_tw_recycle：顧名思義就是回收TIME_WAIT連接。可以說這個內(nèi)核參數(shù)已經(jīng)變成了大眾處理TIME_WAIT的萬金油，如果你在網(wǎng)絡(luò)上搜索TIME_WAIT的解決方案，十有八九會推薦設(shè)置它，不過這里隱藏著一個不易察覺的陷阱：
    當(dāng)多個客戶端通過NAT方式聯(lián)網(wǎng)并與服務(wù)端交互時，服務(wù)端看到的是同一個IP，也就是說對服務(wù)端而言這些客戶端實(shí)際上等同于一個，可惜由于這些客戶端的時間戳可能存在差異，于是乎從服務(wù)端的視角看，便可能出現(xiàn)時間戳錯亂的現(xiàn)象，進(jìn)而直接導(dǎo)致時間戳小的數(shù)據(jù)包被丟棄。參考：tcp_tw_recycle和tcp_timestamps導(dǎo)致connect失敗問題。

  • tcp_max_tw_buckets：顧名思義就是控制TIME_WAIT總數(shù)。官網(wǎng)文檔說這個選項(xiàng)只是為了阻止一些簡單的DoS攻擊，平常不要人為的降低它。如果縮小了它，那么系統(tǒng)會將多余的TIME_WAIT刪除掉，日志里會顯示：「TCP: time wait bucket table overflow」。

需要提醒大家的是物極必反，曾經(jīng)看到有人把「tcp_max_tw_buckets」設(shè)置成0，也就是說完全拋棄TIME_WAIT，這就有些冒險了，用一句圍棋諺語來說：入界宜緩。

ConcurrentHashMap1.8實(shí)現(xiàn)

JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對而言，ConcurrentHashMap只是增加了同步的操作來控制并發(fā)，從JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹,相對而言，總結(jié)如下思考:

  • JDK1.8的實(shí)現(xiàn)降低鎖的粒度，JDK1.7版本鎖的粒度是基于Segment的，包含多個HashEntry，而JDK1.8鎖的粒度就是HashEntry（首節(jié)點(diǎn)）
  • JDK1.8版本的數(shù)據(jù)結(jié)構(gòu)變得更加簡單，使得操作也更加清晰流暢，因?yàn)橐呀?jīng)使用synchronized來進(jìn)行同步，所以不需要分段鎖的概念，也就不需要Segment這種數(shù)據(jù)結(jié)構(gòu)了，由于粒度的降低，實(shí)現(xiàn)的復(fù)雜度也增加了
  • JDK1.8使用紅黑樹來優(yōu)化鏈表，基于長度很長的鏈表的遍歷是一個很漫長的過程，而紅黑樹的遍歷效率是很快的，代替一定閾值的鏈表，這樣形成一個最佳拍檔
  • JDK1.8為什么使用內(nèi)置鎖synchronized來代替重入鎖ReentrantLock，我覺得有以下幾點(diǎn):
  1. 因?yàn)榱６冉档土?，在相對而言的低粒度加鎖方式，synchronized并不比ReentrantLock差，在粗粒度加鎖中ReentrantLock可能通過Condition來控制各個低粒度的邊界，更加的靈活，而在低粒度中，Condition的優(yōu)勢就沒有了
  2. JVM的開發(fā)團(tuán)隊(duì)從來都沒有放棄synchronized，而且基于JVM的synchronized優(yōu)化空間更大，使用內(nèi)嵌的關(guān)鍵字比使用API更加自然
  3. 在大量的數(shù)據(jù)操作下，對于JVM的內(nèi)存壓力，基于API的ReentrantLock會開銷更多的內(nèi)存，雖然不是瓶頸，但是也是一個選擇依據(jù)

參考文獻(xiàn)：
理解TIME_WAIT，徹底弄清解決TCP: time wait bucket table overflow
TIME_WAIT原理
TCP/IP詳解--TIME_WAIT狀態(tài)存在的原因
面試總結(jié)之time_wait狀態(tài)產(chǎn)生的原因，危害，如何避免
ConcurrentHashMap1.8實(shí)現(xiàn)
ConcurrentHashMap1.7實(shí)現(xiàn)
為并發(fā)而生的 ConcurrentHashMap（Java 8）

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容