欣欣客運採華德動能方案,台北市首條純電動巴士聯營路線上路

台北市首條純電動聯營巴士,動物園經信義快速道路來回松山車站的 66 路公車,29 日正式營運!這條由台北市政府規劃、欣欣客運公司經營,採用華德動能電動巴士解決方案的全電動巴士路線,將自 29 日開始,進行為期 3 天的免費試乘活動後,正式成為繼捷運之外台北市木柵地區往來松山車站的第 2 條環保大眾交通路線。

29 日通車典禮由台北市長柯文哲親自致詞。他表示,台北市的大眾交通工具將並持著節能、環保、e 化以及安全的方向進行。未來,還將會擴大辦理全電動巴士的營運。而根據欣欣客運公司的說法,這次 66 路全電動巴士路線的營運,其中不只包括 12 輛全電動巴士的運作而已,包含場站、行控中心的建置等,都是採用全環保的概念建置。

在全電動巴士的部分,這次 66 路全電動巴士是採用上市公司車王電旗下子公司華德動能與日本住友商事所提出的解決方案來打造。除了具備 12 公尺長大型電動巴士中重量最輕、爬坡力最強、時速最高以及續航力最久的優點之外。在關鍵零組件上,華德動能自製比例超過 50% 以上,期望未來能藉此能提升國內的電動產業。

而除了電動巴士本身之外,欣欣客運還在位於木柵動物園附近的場站中,建置全套電動巴士營運架構。除了充電樁、儲能設備之外,還有利用行車紀錄與大數據作業方式的行控中心,以了解行車狀況之外,還掌控車輛耗能、能源轉換率、充電效率等,加以提升營運及駕駛安全。

另外,欣欣客運還在場站的車棚上,架設 302 平方公尺的單晶矽太陽能板。每天藉由太陽能板約能發出 150 度電,在 100 度電提供給行控中心使用之外,其他多餘的電儲存下來後,每隔幾天就能充飽一台巴士 250 度的儲電量,達到環保綠能的目的。

根據規劃,欣欣客運預計在 2018 年年底前將把全電動巴士的數量擴增到 30 部。而且在場站的綠能發電上,還考慮加入風力發電的部分,利用當地冬天風大的優勢,提升綠能電力的發電效益。之後,在逐步擴展到其他的路線上。

(合作媒體:。首圖來源:)

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

※超省錢租車方案

米蘭國際摩托車展直擊,電動機車群雄並起

米蘭國際摩托車展(EICMA)在 2018 年已經邁入第 76 屆,是最有歷史也最具規模的摩托車展會之一,再加上義大利本身就是機車大國,米蘭國際摩托車展的地位不言可喻。科技新報在米蘭摩托車展直擊各國最新款的電動機車,一窺未來電動機車的可能性。

隨著環保意識提升和電動技術的發展,電動機車成為重要的發展方向,許多車廠也搶進電動機車市場。除了國內電動機車市場邁向三足鼎立,海外的電動機車也呈現百家爭鳴的局面。2018 年米蘭國際摩托車展的主題是「我們看見了尚未存在的道路」,廠商們展示出自身預見的摩托車未來發展趨勢,其中電動機車就是相當重要的一環。

Harley-Davidson

以重型機車風靡全球的美國摩托車大廠哈雷(Harley-Davidson)在多年傳聞將生產電動機車之後,終於在米蘭國際摩托車展端出了電動重機 LiveWire。LiveWire 源自於 2014 年的 LiveWire 電動機車計畫,經過四年的時間終於開花結果。LiveWire 會以充電式鋰電池提供動力,哈雷表示所有經銷商都會配有開放使用的充電器。這款電動重機可以利用觸控螢幕進行操作,並透過藍牙連結手機來撥放音樂、接聽電話或進行導航,還能夠設定 7 種騎乘模式。

LiveWire 的詳細規格還有很多尚未透漏的資訊,包括電池續航力和性能等等。LiveWire 電動重機共有紅色、黑色和橘色三種款式,預計在 2019 年 1 月上市,售價和上市範圍則尚未公布。「這是哈雷跨入電動摩托車界的重要一步,但只不過是第一步。」哈雷產品規劃副總裁 Marc Mcallister 這麼說。未來哈雷計畫到 2022 年將會有「全系列的電動摩托車」,這樣的豪語能否成真值得拭目以待。

哈雷電動重機 LiveWire。(圖片來源:)

哈雷產品規劃副總裁 Marc Mcallister。(圖片來源:)

哈雷電動重機 LiveWire。(圖片來源:)

Vespa

旗下擁有知名機車品牌偉士牌(Vespa)的義大利機車集團 Piaggio 自然不會錯過本國的摩托車盛事,展示了電動機車 Vespa Elettrica 和油電混合車 Vespa Elettrica X。Vespa Elettrica 雖然早在兩年前就發表,不過直到 2018 年 10 月才在歐洲市場開放預購。Elettrica 具有 4kW 的電動馬達功率,屬於 50cc 級距。動力採用充電式鋰電池,充滿電需要 4 個小時,充電一次最遠可以騎乘 100 公里,可以使用一般的插座充電。Vespa Elettrica 在歐洲定價為 6,390 歐元起,約相當於 22.5 萬元台幣,價格比燃油車版本高上不少。

Vespa Elettrica X 屬於油電混合動力,為了空出空間放置燃油馬達和油箱,Elettrica X 採用了較小的電池。其中燃油動力能騎乘 150 公里,電池則能提供 50 公里的動力,因此續航距離最長可以達到接近 200 公里。Vespa Elettrica X 預計將會在 2019 年 3 月推出。

Vespa Elettrica。(圖片來源:)

Vespa Elettrica X。(圖片來源:)

Energica

2014 年才成立的義大利公司 Energica 在電動重機領域已經有豐富的經驗,在 2017 年的米蘭國際摩托車展就發表過電動重機 EVA EsseEsse 9。Energica 旗下還有 EGO 和 EVA 兩款性能優異的電動重機,其中 EGO 更成為電動摩托車世界盃(FIM Moto-e World Cup)的指定用車。這次 Energica 的展示品當中最受矚目的並非上述的車款,而是與電子大廠三星(Samsung)聯手打造的新車款 Bolid-E。

Bolid-E 建立在 EVA EsseEsse 9 的基礎上,搭載雙方共同開發的 Smart Ride 智慧系統。透過 Smart Ride 系統能讓 Bolid-E 連結車主的三星智慧手錶(Samsung Galaxy Watch),用手錶的應用程式就能操控摩托車。車主可以在手錶上查看充電情形、地圖、車輛的狀態和附近的充電位置等資訊。而且車主只要配戴智慧手錶靠近 Bolid-E,摩托車就會自動感應並解鎖。Bolid-E 還配備兩塊顯示螢幕智慧後照鏡,即時分析鏡頭所拍攝的後方影像,提醒車主可能的危險,提高駕駛的安全性。雖然 Bolid-E 各種智慧功能相當吸睛,但目前只是概念車,尚無任何上市規劃。

Energica Bolid-E。(圖片來源:)

Energica Bolid-E 有著顯示螢幕智慧後照鏡。(圖片來源:)

Energica Bolid-E。(圖片來源:)

在米蘭國際摩托車展上可以看到各個機車品牌隊投入電動機車所做的嘗試,範圍遍及電動速克達、電動自行車和電動重機等等。除了電動化之外,許多機車也走向智慧化,與智慧型裝置有了更多的連結。或許電動機車的發展還有很長的一段路要走,但從車展眾家品牌的摸索中,可以初窺電動機車的未來樣貌。

(合作媒體:。首圖來源:)

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※南投搬家公司費用需注意的眉眉角角,別等搬了再說!

※教你寫出一流的銷售文案?

中國氫能產業發展迅速,氫燃料電池車突破 2 千輛

中國媒體報導,中國張家口氫能與可再生能源論壇日前召開,根據論壇公布數據顯示,中國在氫能與燃料電池汽車產業方面快速發展,目前已有 2,000 多輛氫燃料電池汽車。

張家口利用自身豐富的風電、光伏可再生能源優勢,藉助 2022 年冬季奧運會由北京舉辦的東風,正大力發展氫能產業。據規劃,到 2020 年張家口市投入使用的燃料電池公交車、物流車、出租車將達到 1,800 輛,建成加氫站 21 座,實現製氫年產 2 萬噸、燃料電池發動機產能 1 萬台、燃料電池客車年產 4,500 輛,初步形成從氫氣製備、儲運、加註到燃料電池發動機和整車研發、生產、檢測的全產業鏈。

另外,自 2016 年以來,中國在氫能與燃料電池汽車產業方面獲得快速發展,形成京津冀、華東、華南、西南、華中、西北、東北等氫能與燃料電池汽車產業集群,建立起相對成熟的產業配套和商業化應用體系。

數據顯示,中國現在已經有 2,000 多輛氫燃料電池汽車和 12 座加氫站。目前,北美、歐洲、日本和韓國的燃料電池汽車產業已進入商業化階段,惟中國仍處於商業化初期。

(本文內容由 授權使用。首圖來源: CC BY 2.0)

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧

第九屆中國國際新能源暨智慧汽車論壇 2019

2019 年 4 月 2-3 日∣中國·上海

新能源時代,攜手智慧化未來

2019 年是實施「十三五」規劃的重要一年,《中共中央關於制定國民經濟和社會發展第十三個五年規劃的建議》把新能源汽車推廣列入國家的重要計畫之中,要求提高電動汽車產業化水準。這表明在「十三五」期間,新能源汽車發展在整個國民經濟和社會發展中將處在十分重要的地位,明確了新能源汽車在國民經濟和社會發展中的戰略定位。「十三五」期間,中國將成為世界最大的新能源汽車市場,成為世界新能源汽車的核心主戰場。

在過去八屆新能源汽車論壇成功舉辦的基礎上,由希邁商務諮詢(上海)有限公司主辦的第九屆中國國際新能源暨智慧汽車論壇 2019 即將於 4 月 2 日- 4 月 3 日在上海隆重舉行。新能源汽車系列論壇成功邀請了包括國家發改委能源研究所、世界電動車協會、亞太電動車協會、世界氫能協會、世界分散式能源聯盟、中國工程院等在內的政府單位與研究機構,以及包括 BMW、賓士、奇瑞捷豹路虎、Volkswagen、奧迪、比亞迪、上汽、北汽,大陸,電裝,LG 等在內的知名整車商及綜合零部件商,共同研討新能源汽車產業政策趨勢、技術路線及難點、基礎設施建設、商業模式等並取得了豐碩的成果,獲得了業內外人士的一致好評。

在即將到來的 2019 年,組委會為感謝業內外人士對系列論壇長期以來的支援和關注,將傾情奉上相比歷屆舉辦規模最大的第九屆新能源汽車論壇,涉及 8 個論壇,CEO TALK,頒獎典禮,一對一洽談及雞尾酒會。屆時將誠邀全球範圍內的整車製造商、動力總成公司、動力電池及燃料電池廠商、充電、儲能企業、零部件供應商、核心技術服務提供者和政府官員等近 900 位產業人士一起,對新能源汽車產業面臨的挑戰,機遇與對策各方面進行為期 2 天更深層次並具有建設和戰略性的探討。

會議亮點

Ø  豐富的內容:

8 大板塊的深度解析

Ø  參會嘉賓:

900+ 高度滿意的企業決策者,200+ 業內知名企業,30+ 國家和地區

Ø  參會嘉賓分析:

17%+ 來自各國政府部門及權威機構,25%+ 來自知名整車商

Ø  演講嘉賓:

70+ 世界新能源汽車產業知名發言嘉賓

Ø  交流機會:

16+ 小時的交流機會:圓桌討論、VIP 午宴和開放式問答

Ø  會議形式:

8 個論壇,1 場雞尾酒晚宴 + 一對一洽談,1 個頒獎典禮,1 個 CEO Talk

 

會議結構

若您對活動有更多要求,請撥打 021-6045 6030 與我們聯繫,謝謝理解和支持!

我們期待與貴單位一起出席於 2019 年 4 月 2 日– 3 日在上海舉辦的第九屆中國國際新能源暨智慧汽車論壇, 以利決策!

 

欲知更多會議詳情,請登陸官方網站:

連絡人:Latika LIU(劉小姐)

電話:021-6045 6030

傳真:021-6047 5887

郵箱:

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

※網頁設計最專業,超強功能平台可客製化

福斯將在美國闢新廠,生產電動車

新版北美自貿協定(NAFTA)再發威!福斯(Volkswagen)揮軍電動車,為了卡位美國市場,打算在美國設立新廠,目前正在尋找合適地點。

路透社報導,福斯 11 月稍早宣布,2023 年前將斥資近 440 億歐元(約 500 億美元)發展電動車、自動駕駛、新移動服務,並探詢和美國車廠福特汽車合作的可能性。福斯計劃 2020 年發售電動車,為了達成此一目標,該公司將先在海外生產,之後改到美國新廠製造。

新上任的福斯美國區執行長 Scott Keogh 28 日表示,福斯 2020 年將推出售價 3 萬至 4 萬美元的電動車,為此需要新的工廠。福斯在美國田納西州已有工廠,生產 Passat 和 Atlas 等車款,田納西廠仍有足夠空間,是新廠可能的落腳地點之一,但是不必然在此設廠。

(本文內容由 授權使用。首圖來源:)

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

哈雷機車大轉型,推出電動機車

說起哈雷機車(HARLEY-DAVIDSON),大部分人心中就響起重機隆隆的引擎聲,這註冊商標般的引擎聲,讓哈雷機車得到猛豬(hog)美譽,形象深植人心到,哈雷連股票交易代碼都用「HOG」代表自己。轟轟隆的哈雷機車引擎聲,是男人的浪漫,然而,不可想像的事情發生了,哈雷機車竟然推出電動機車,電動化也就代表沒有引擎而是以馬達取代,當然就不會有轟隆隆的引擎聲,這樣真的可以嗎?

2018 年 11 月 6~12 日舉辦的米蘭國際機車暨零件展(EICMA),哈雷發表 LiveWire 電動機車,跨出這個讓世人震驚的重大一步。哈雷機車必須全力轉型,吸引全新世代的新消費者,推出電動機車、油電混合機車,是其中不可或缺的一步,即使這代表向過去告別,也在所不惜。

哈雷機車為何做出如此甘冒大不韙的決策,根本原因是:人口學。傳統重機車的消費者年年變老,但是新近世代的年輕消費者卻未加入,這使重機車市場消費者呈現老化結構,美國幾乎半數重機車消費者都已經年過 50,他們或許還老當益壯,但是隨著年紀再更大,會因退休而無法一直購買新車,也會因體力衰老終於不方便騎車,最老的一代更會來到人類壽命的終點。

哈雷機車未雨綢繆,雖然 2018 年第三季季報仍然超越市場預期,但市佔率已開始萎縮,隨著忠實消費族群一年年老化,新消費者再不加入,哈雷遲早要被時代淘汰。因此 2017 年,哈雷訂下了 10 年計畫,預定到 2027 年要吸引 200 萬新車主,包括大力進軍電動機車,甚至輕型機車、電動腳踏車。另一方面,許多新世代只想輕鬆騎車,覺得重機危險麻煩又辛苦,為了打破這種刻板印象,哈雷打算設立許多學校,教導新世代怎麼騎機車。

電動機車其實相對於內燃機機車有許多技術優勢,例如不需換檔,且從靜止開始的加速扭力相對極大,加速過程沒有換檔的中斷時間,更無比順暢。以電動車為例,特斯拉(Tesla)Model S P100D 從靜止加速到時速 60 英哩只要 2.5 秒。這種超快加速力,很適合喜愛機車遠比汽車加速度更快的機車玩家。但很顯然的,電動機車不會有引擎聲,取而代之的是電動傳動系統的馬達聲。

哈雷機車計畫在未來幾年推出數款新機車產品線,LiveWire 是其中之一,預定於 2019 年底,於美國與歐洲精選通路上市,2019 年初就會公布售價。不過,哈雷機車轉型到電動機車之路,還有許多困難,內燃機與電動傳動系統是完全不同的專業領域,哈雷能否專精是一大問題,即使挑戰成功,還有競爭對手的障礙,成立於 2006 年的加州電動機車廠 Zero Motorcycles 已推出 4 款電動機車,還預定 2019 年 10 月發表電動機車新產品線。

無論如何,在老車主逐漸老化凋零的不可逆潮流下,哈雷機車這個響噹噹的品牌,能否繼續存續,還是得看電動化能不能成功了。

(合作媒體:。首圖來源:)

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※FB行銷專家,教你從零開始的技巧

Java 多線程基礎(六)線程等待與喚醒

 Java 多線程基礎(六)線程等待與喚醒

遇到這樣一個場景,當某線程裏面的邏輯需要等待異步處理結果返回后才能繼續執行。或者說想要把一個異步的操作封裝成一個同步的過程。這裏就用到了線程等待喚醒機制。

一、wait()、notify()、notifyAll() 等方法介紹

在 Object 中,定義了 wait()、notify() 和 notifyAll() 等接口。wait() 的作用是讓當前線程進入等待狀態,同時,wait() 也會讓當前線程釋放它所持有的鎖。而 notify() 和 notifyAll() 的作用,則是喚醒當前對象上的等待線程;notify() 是喚醒單個線程,而 notifyAll() 是喚醒所有的線程。

Object類中關於等待/喚醒的API詳細信息如下:

notify()                                       — 喚醒在此對象監視器上等待的單個線程。
notifyAll()                                  — 喚醒在此對象監視器上等待的所有線程。
wait()                                         — 讓當前線程處於“等待(阻塞)狀態”,“直到其他線程調用此對象的 notify() 方法或 notifyAll() 方法”,當前線程被喚醒(進入“就緒狀態”)。
wait(long timeout)                    — 讓當前線程處於“等待(阻塞)狀態”,“直到其他線程調用此對象的 notify() 方法或 notifyAll() 方法,或者超過指定的時間量”,當前線程被喚醒(進入“就緒狀態”)。
wait(long timeout, int nanos)  — 讓當前線程處於“等待(阻塞)狀態”,“直到其他線程調用此對象的 notify() 方法或 notifyAll() 方法,或者其他某個線程中斷當前線程,或者已超過某個實際時間量”,當前線程被喚醒(進入“就緒狀態”)。

二、wait() 和 notify() 示例

public class Demo02 {
    public static void main(String[] args) {
        Thread t1 = new MyThread("t1");
        synchronized (t1) {
            try {
                // 啟動“線程t1”
                System.out.println(Thread.currentThread().getName()+" start t1");
                t1.start();
                // 主線程等待t1通過notify()喚醒。
                System.out.println(Thread.currentThread().getName()+" wait()");
                t1.wait();
                System.out.println(Thread.currentThread().getName()+" continue");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}
class MyThread extends Thread{
    public MyThread(String name) {
        super(name);
    }
    @Override
    public void run() {
        synchronized (this) {
            try {
                System.out.println(Thread.currentThread().getName()+" call notify()");
                notify(); // 喚醒當前的Demo02線程
            }catch(Exception e) {
                e.printStackTrace();
            }
        }
    }
}
// 運行結果
main start t1
main wait()
t1 call notify()
main continue

說明:

①、 注意,圖中”主線程” 代表“主線程main”。”線程t1″ 代表Demo02中啟動的“線程t1”。 而“鎖” 代表“t1這個對象的同步鎖”。
②、“主線程”通過 new ThreadA(“t1”) 新建“線程t1”。隨後通過synchronized(t1)獲取“t1對象的同步鎖”。然後調用t1.start()啟動“線程t1”。
③、“主線程”執行t1.wait() 釋放“t1對象的鎖”並且進入“等待(阻塞)狀態”。等待t1對象上的線程通過notify() 或 notifyAll()將其喚醒。
④、“線程t1”運行之後,通過synchronized(this)獲取“當前對象的鎖”;接着調用notify()喚醒“當前對象上的等待線程”,也就是喚醒“主線程”。
⑤、“線程t1”運行完畢之後,釋放“當前對象的鎖”。緊接着,“主線程”獲取“t1對象的鎖”,然後接着運行。

具體過程圖解

三、wait(long timeout) 和 notify()

public class Demo02 {
    public static void main(String[] args) {
        Thread t1 = new MyThread("t1");

        synchronized(t1) {
            try {
                // 啟動線程t1
                System.out.println(Thread.currentThread().getName() + " start t1");
                t1.start();

                // 主線程等待t1通過notify()喚醒 或 notifyAll()喚醒,或超過3s延時;然後才被喚醒。
                System.out.println(Thread.currentThread().getName() + " call wait ");
                t1.wait(3000);

                System.out.println(Thread.currentThread().getName() + " continue");
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        
    }
}
class MyThread extends Thread{
    public MyThread(String name) {
        super(name);
    }
    public void run() {
        System.out.println(Thread.currentThread().getName() + " run ");
        // 死循環,不斷運行。
        while(true)
            ;
    }
}
// 運行結果
main start t1
main call wait 
t1 run             // 3秒后輸出 main continue
main continue 

 說明:

如下圖,說明了“主線程”和“線程t1”的流程。
①、注意,圖中”主線程” 代表線程main。”線程t1″ 代表MyThread中啟動的線程t1。 而“鎖” 代表“t1這個對象的同步鎖”。
②、主線程main執行t1.start()啟動“線程t1”。
③、主線程main執行t1.wait(3000),此時,主線程進入“阻塞狀態”。需要“用於t1對象鎖的線程通過notify() 或者 notifyAll()將其喚醒” 或者 “超時3000ms之後”,主線程main才進入到“就緒狀態”,然後才可以運行。
④、“線程t1”運行之後,進入了死循環,一直不斷的運行。
⑤、超時3000ms之後,主線程main會進入到“就緒狀態”,然後接着進入“運行狀態”。

 具體過程圖解:

四、wait() 和 notifyAll()

public class Demo02 {
    private static Object obj = new Object();
    public static void main(String[] args) {
        MyThread t1 = new MyThread("t1");
        MyThread t2 = new MyThread("t2");
        MyThread t3 = new MyThread("t3");
        t1.start();
        t2.start();
        t3.start();
        try {
            System.out.println(Thread.currentThread().getName()+" sleep(5000)");
            Thread.sleep(5000); // 休眠5秒
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        synchronized (obj) {
            System.out.println(Thread.currentThread().getName()+" notifyAll()");
            obj.notifyAll();
        }
        
    }
    static class MyThread extends Thread{
        public MyThread(String name) {
            super(name);
        }
        public void run() {
            synchronized (obj) { 
                try {
                    System.out.println(Thread.currentThread().getName() + " run ");
                    obj.wait();
                    System.out.println(Thread.currentThread().getName() + " continue");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}
// 運行結果
t1 run 
t2 run 
main sleep(5000)
t3 run 
main notifyAll()
t3 continue
t2 continue
t1 continue

說明:

①、 主線程中新建並且啟動了3個線程”t1″, “t2″和”t3″。
②、主線程通過sleep(5000)休眠5秒。在主線程休眠3秒的過程中,我們假設”t1″, “t2″和”t3″這3個線程都運行了。以”t1″為例,當它運行的時候,它會執行obj.wait()等待其它線程通過notify()或nofityAll()來喚醒它;相同的道理,”t2″和”t3″也會等待其它線程通過nofity()或nofityAll()來喚醒它們。
③、主線程休眠3秒之後,接着運行。執行 obj.notifyAll() 喚醒obj上的等待線程,即喚醒”t1″, “t2″和”t3″這3個線程。 緊接着,主線程的synchronized(obj)運行完畢之後,主線程釋放“obj鎖”。這樣,”t1”, “t2″和”t3″就可以獲取“obj鎖”而繼續運行了!

具體過程圖解

五、 為什麼notify(), wait()等函數定義在Object中,而不是Thread中

Object中的wait(), notify()等函數,和synchronized一樣,會對“對象的同步鎖”進行操作。

wait()會使“當前線程”等待,因為線程進入等待狀態,所以線程應該釋放它鎖持有的“同步鎖”,否則其它線程獲取不到該“同步鎖”而無法運行!
OK,線程調用wait()之後,會釋放它鎖持有的“同步鎖”;而且,根據前面的介紹,我們知道:等待線程可以被notify()或notifyAll()喚醒。現在,請思考一個問題:notify()是依據什麼喚醒等待線程的?或者說,wait()等待線程和notify()之間是通過什麼關聯起來的?答案是:依據“對象的同步鎖”。

負責喚醒等待線程的那個線程(我們稱為“喚醒線程”),它只有在獲取“該對象的同步鎖”(這裏的同步鎖必須和等待線程的同步鎖是同一個),並且調用notify()或notifyAll()方法之後,才能喚醒等待線程。雖然,等待線程被喚醒;但是,它不能立刻執行,因為喚醒線程還持有“該對象的同步鎖”。必須等到喚醒線程釋放了“對象的同步鎖”之後,等待線程才能獲取到“對象的同步鎖”進而繼續運行。

總之,notify(), wait()依賴於“同步鎖”,而“同步鎖”是對象鎖持有,並且每個對象有且僅有一個!這就是為什麼notify(), wait()等函數定義在Object類,而不是Thread類中的原因。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

iOS開發實踐-OOM治理

概覽

說起iOS的OOM問題大家第一想到的應該更多的是內存泄漏(Memory Leak),因為無論是從早期的MRC還是2011年Apple推出的ARC內存泄漏問題一直是iOS開發者比較重視的問題,比如我們熟悉的 Instruments Leaks 分析工具,Xcode 8 推出的 Memory Graph 等都是官方提供的內存泄漏分析工具,除此之外還有類似於FBRetainCycleDetector的第三方工具。不過事實上內存泄漏僅僅是造成OOM問題的一個原因而已,實際開發過程中造成OOM的原因有很多,本文試圖從實踐的角度來分析造成OOM的諸多情況以及解決辦法。

造成OOM的原因

造成OOM的直接原因是iOS的 Jetsam 機製造成的,在Apple的 Low Memory Reports中解釋了具體的運行情況:當內存不足時,系統向當前運行中的App發起applicationDidReceiveMemoryWarning(_ application: UIApplication) 調用和 UIApplication.didReceiveMemoryWarningNotification 通知,如果內存仍然不夠用則會殺掉一些後台進程,如果仍然吃緊就會殺掉當前App。

關於 Jetsam 實現機制其實蘋果已經開源了XNU代碼,可以在這裏查看,核心代碼在 kern_memorystatus 感興趣可以閱讀,其中包含了很多系統調用函數,可以幫助開發者做一些OOM監控等。

一、內存泄漏

內存泄漏造成內存被持久佔用無法釋放,對OOM的影響可大可小,多數情況下並非泄漏的類直接造成大內存佔用而是無法釋放的類引用了比較大的資源造成連鎖反應最終形成OOM。一般分析內存泄漏的工具推薦使用Leaks,後來Apple提供了比較方便的Memory Graph。

Instruments Leaks

Leaks應該是被所有開發者推薦的工具,幾乎搜索內存泄漏就會提到這個工具,但是很多朋友不清楚其實當前Leaks的作用沒有那麼大,多數時候內存泄漏使用Leaks是分析不出來的。不妨運行下面的一個再簡單不過的泄漏情況(在一個導航控制器Push到下面的控制器然後Pop出去進行驗證):

class Demo1ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        
        self.customView.block = {
            print(self.view.bounds)
        }
        self.view.addSubview(self.customView)
    }
    
    private lazy var customView:CustomView = {
        let temp = CustomView()
        
        return temp
    }()

    deinit {
        print("Demo1ViewController deinit")
    }
}


class CustomView:UIView {
    var block:(()->Void)?
}

上面這段代碼有明顯的循環引用造成的內存泄漏,但是前面說的兩大工具幾乎都無能為力,首先Leaks是:

網絡上有大量的文章去介紹Leaks如何使用等以至於讓有些同學以為Leaks是一個無所不能的內存泄漏分析工具,事實上Leaks在當前iOS開發環境下檢測出來的內存泄漏比較有限。之所以這樣需要先了解一個App的內存包括哪幾部分:

  1. Leaked memory: Memory unreferenced by your application that cannot be used again or freed (also detectable by using the Leaks instrument).

  2. Abandoned memory: Memory still referenced by your application that has no useful purpose.

  3. Cached memory: Memory still referenced by your application that might be used again for better performance.

Leaked memory正是Leaks工具所能發現的內存,這部分內存屬於沒有任何對象引用的內存,在內存活動圖中是是不可達內存。

Abandoned memory在應用內存活動圖中存在,但是因為應用程序邏輯問題而無法再次訪問的內存。和內存泄漏最主要的區別是它的引用(包括強引用和弱引用)是存在的,但是不會再用了。比如上面的循環引用問題,VC被Pop后這部分內存首先還是在內存活動圖中的,但是下次再push我們是創建一個新的VC而非使用原來的VC就造成上一次的VC成了廢棄的內存。

如果是早期MRC下創建的對象忘記release之類的使用Leaks是比較容易檢測的,但是 ARC 下就比較少了,實際驗證過程中發現更多的是引用的一些古老的OC庫有可能出現,純Swift幾乎沒有。

Abandoned memory事實上要比leak更難發現,關於如何使用Instruments幫助開發者進行廢棄的內存分析,參見官方Allocations工具的使用:Find abandoned memory

Memory Graph

當然Xcode 8 的Memory Graph也是一大利器,不過如果你這麼想上面的問題很有可能會失望(如下圖),事實上Memory Graph我理解有幾個問題:第一是這個工具要想實際捕獲內存泄漏需要多運行幾次,往往一次運行過程是無法捕獲到內存泄漏的;第二比如上面的子視圖引起的內存泄漏是無法使用它捕獲內存泄漏信息的,VC pop之後它會認為VC沒有釋放它的子視圖沒有釋放也是正確的,事實上VC就應該是被釋放的,不過調整一下上面的代碼比如刪除self.view.addSubview(self.customView)后儘管還存在循環引用但是卻是可以檢測到的(不過實際上怎麼可能那麼做呢),關於這個玄學問題沒有找到相關的說明文檔來解釋。但是事實上 Memory graph 從來也沒有聲明自己是在解決內存泄漏問題,而是內存活動圖分析工具,如果這麼去想這個問題似乎也不算是什麼bug。

第三方工具

事實上看到上面的情況相信很多同學會想要使用第三方工具來解決問題,比如大家用的比較多的MLeaksFinder和PLeakSniffer,兩者不同之處是後者除了可以默認查出 UIViewController 和 UIView 內存泄漏外還可以查出所有UIViewController屬性的內存泄漏算是對前者的一個補充。當然前者還配合了 Facebook 的FBRetainCycleDetector可以分析出循環引用出現的引用關係幫助開發者快速修復循環引用問題。

不過可惜的是這兩款工具,甚至包括 PLeakSniffer 的 Swift 版本都是不支持 Swift 的(準確的說是不支持Swift 4.2,原因是Swift 4.2繼承自 NSObject 的類不會默認添加 @objc 標記 class_copyPropertyList無法訪問其屬性列表,不僅如此Swift5.x中連添加 @objcMembers 也是沒用的),但是 Swift 不是到了5.x才ABI穩定的嗎?,再次查看 Facebook 的 FBRetainCycleDetector 本身就不不支持Swift,具體可以查看這個issue這是官方的回答,如果稍微熟悉這個庫原理的同學應該也不難發現具體的原因,從目前的情況來看當前 FBRetainCycleDetector 的原理在當前swift上是行不通的,畢竟要獲取對象布局以及屬性在Swift 5.x上已經不可能,除非你將屬性標記為@objc,這顯然不現實,走 SWift 的Mirror當前又無法 setValue,所以研究了一下現在開源社區的情況幾乎沒有類似OC的完美解決方案。

Deubgger的LeakMonitorService

LeakMonitorService是我們自己實現的一個Swift內存泄漏分析工具,主要是為了解決上面兩個庫當前運行在Swift 5.x下的問題,首先明確的是當前 Swift 版本是無法訪問其非 @objc 屬性的,這就無法監控所有屬性,但是試想其實只要這個監控可以解決大部分問題它就是有價值的,而通常的內存泄漏也就存在於 UIViewController 和 UIView 中,因此出發點就是檢測 UIViewController 和其根視圖和子視圖的內存泄漏情況。

如果要檢測內存泄漏就要先知道是否被釋放,如果是OC只要Swizzle dealloc方法即可,但是顯然Swift中是無法Swizzle一個deinit方法的,因為這個方法本身就不是runtime method。最後我們確定的解決方案就是通過關聯屬性進行監控,具體的操作(具體實現後面開源出來):

  1. 使用一個集合Objects記錄要監控存在內存泄漏的對象
  2. 給NSObject添加一個關聯屬性:deinitDetector,類型為 Detector 作為NSObject的代理,Detector是一個class,裏面引用一個block,在 deinit 時調用這個 block 從Objects 中移除監控對象
  3. 在 UIViewController 初始化時給 deinitDetector 賦值進行監控,同時將自身添加到 Objects 數組代表可能會發生內存泄漏,在 UIViewController 的將要釋放時檢測監控(一般稍微延遲一會)檢測Objects是否存在當前對象如果是被正確釋放因為其屬性deinitDetector 會將其從 Objects 移除所以就不會有問題,如果出現內存泄漏deinitDetector的內部block不會調用,此時當前控制器還在 Objects 中說明存在內存泄漏
  4. 使用同樣的方法監控UIViewController的根視圖和子視圖即可

需要說明的是監控UIViewController的時機,通常建議添加監控的時機放到viewDidAppear(),檢測監控的時機放到viewDidDisappear()中。原因是此時子視圖相對來說已經完成布局(避免存在動態添加的視圖沒有被監控到),而檢測監控的時機放到viewDidDisappear()中自然也不是所有調用了viewDidDisappear()的控制器就一定釋放了,可以在viewDidDisappear()中配合isMovingFromParent和isBeingDismissed屬性進行比較精準的判斷。

常見的內存泄漏

經過 LeakMonitorService 檢測確實在產品中發現了少量的內存泄漏情況,但是很有代表性,這裏簡單的說一下,當然普通的block循環引用、NSTimer、NotificationCenter.default.addObserver()等這裏就不在介紹了,產品檢測中幾乎也沒有發現。

1.block的雙重引用問題

先來看一段代碼:

class LeakDemo2ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()

        let customView = CustomView()
        customView.block1 = {
            [weak self] () -> CustomSubView? in
            guard let weakSelf = self else { return nil }
            let customSubview = CustomSubView()
            customSubview.block2 = {
                 // 儘管這個 self 已經是 weak 了但是這裏也會出現循環引用
                print(weakSelf)
            }
            return customSubview
        }
        
        self.view.addSubview(customView)
    }
    
    deinit {
        print("LeakDemo2ViewController deinit")
    }

}

private class CustomView:UIView {
    var block1:(()->CustomSubView?)?
    
    override init(frame: CGRect) {
        super.init(frame: frame)
        
    }
    
    override func layoutSubviews() {
        super.layoutSubviews()
        if let subview = block1?() {
            self.addSubview(subview)
        }
    }
    
    required init?(coder: NSCoder) {
        fatalError("init(coder:) has not been implemented")
    }
}

private class CustomSubView:UIView {
    var block2:(()->Void)?
}

上面的代碼邏輯並不複雜,customView 的 block 內部已經考慮了循環引用將 self 聲明為 weak 是沒有問題的,出問題的是它的子視圖又嵌套了一個 block2 從而造成了 block2 的嵌套引用關係,而第二個 block2 又引用了 weakSelf 從而造成循環引用(儘管此時的self是第一個 block 內已經聲明成 weakSelf)解決的辦法很簡單隻要內部的 block2 引用的 self 聲明成weak就好了(此時形成的是[weak weakSelf]的關係)。那麼為什麼會這樣的,內部 block2 訪問的也不是當前VC的self對象,而是弱引用怎麼會出問題呢?

原因是當前控制器 self 首先強引用了customView,而customView又通過 addSubview() 強引用了customSubView,這樣依賴其實 self 已經對 customSubView形成了強引用關係。但是 customSubview 本身引用的弱引用weakSelf嗎?(注意是弱引用的weakSelf,不是weakSelf的弱引用),但是需要清楚一點就是外部的弱引用是block1對self的弱引用,也就是在weak table(Swift最新實現在Side table)裏面會記錄block1的弱引用關係,但是block2是不會在這個表中的,所以這裏還是一個強引用,最終造成循環引用關係。

Swift中的weakSelf和strongSelf

補充一下OC中的weakSelf和strongSelf的內容,通常情況下常見的做法:

__weak __typeof__(self) weakSelf = self;
[self.block = ^{
    __strong __typeof(weakSelf)strongSelf = weakSelf;
    if (strongSelf) {
        strongSelf.title = @"xxx";
    }
}];

當然你可以用兩個宏簡化上面的操作:

@weakify(self);
[self.block = ^{
	 @strongify(self);
    if (strongSelf) {
        self = @"xxx";
    }
}];

上面 strongSelf 的主要目的是為了避免block中引用self的方法在執行過程中被釋放掉造成邏輯無法執行完畢,swfit中怎麼做呢,其實很簡單(method1和method2要麼都執行,要麼一個也不執行):

self.block = {
    [weak self] in
    if let strongSelf = self {
        strongSelf.method1()
        strongSelf.method2()
    }
}

但是下面的代碼是不可以的(有可能會出現method2不執行,但是method1會執行的情況):

self.block = {
    [weak self] in
    self?.method1()
    self?.method2()
}

2.delay操作

通常大家都很清楚 NStimer 會造成循環引用(儘管在新的api已經提供了block形式,不必引用target了),但是很少注意 DispatchQueue.main.asyncAfter() 所實現的delay操作,而它的返回值是 DispatchWorkItem 類型通常可以用它來取消一個延遲操作,不過一旦對象引用了 DispatchWorkItem 而在block中又引用了當前對象就形成了循環引用關係,比如:

class LeakDemo3ViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        
        self.delayItem = DispatchWorkItem {
            print("asyncAfter invoke...\(self)")
        }
        DispatchQueue.main.asyncAfter(deadline: .now() + .seconds(3), execute: self.delayItem!)
    }
    
    deinit {
        print("LeakDemo3ViewController deinit")
    }
    
    private var delayItem:DispatchWorkItem?

}

3.內部函數

其實,如果是閉包大家平時寫代碼都會比較在意避免循環引用,但是如果是內部函數很多同學就沒有那麼在意了,比如下面的代碼:

class LeakDemo4ViewController: UIViewController {

    var block:(()->Void)?
    
    override func viewDidLoad() {
        super.viewDidLoad()
        
        func innerFunc() {
            print(self)
        }
        
        self.block = {
            [weak self] in
            guard let weakSelf = self else { return }
            innerFunc()
            print(weakSelf)
        }
    }
    
    deinit {
        print("LeakDemo4ViewController deinit")
    }

}

innerfunc() 中強引用了self,而 innerFunc 執行上下文是在block內進行的,所以理論上在block內直接訪問了self,最終造成循環引用。內部函數在swift中是作為閉包來執行的,上面的代碼等價於:

let innerFunc =  {
    print(self)
}

說起block的循環引用這裏可以補充一些情況不會造成循環引用或者是延遲釋放的情況。特別是對於延遲的情況此次在產品中也做了優化,盡可能快速釋放內存避免內存峰值過高。

a.首先pushViewController()和presentViewController()本身是不會引用當前控制器的,比如說下面代碼不會循環引用:

let vc = CustomViewController()
vc.block = {
    print(self)
}
self.present(vc, animated: true) {
    print(self)
}

b.UIView.animation不會造成循環引用

UIView.animate(withDuration: 10.0) {
    self.view.backgroundColor = UIColor.yellow
}

c.UIAlertAction的handler不會引起循環引用(iOS 8 剛出來的時候有問題)

let alertController = UIAlertController(title: "title", message: "message", preferredStyle: UIAlertController.Style.alert)
let action1 = UIAlertAction(title: "OK", style: UIAlertAction.Style.default) { (alertAction) in
    print(self)
}
let action2 = UIAlertAction(title: "Cancel", style: UIAlertAction.Style.cancel) { (alertAction) in
    print(self)
}
alertController.addAction(action1)
alertController.addAction(action2)
self.present(alertController, animated: true) {
    print(self)
}

d.DispatchQueue asyncAfter會讓引用延遲,這裏的引用也是強引用,但是當asynAfter執行結束會得到釋放,但是不及時

DispatchQueue.main.asyncAfter(deadline: .now() + .seconds(10)) {
    print(self)
}

e.網絡請求會延遲釋放

如下在請求回來之前self無法釋放:

guard let url = URL(string:"http://slowwly.robertomurray.co.uk/delay/3000/url/http://www.google.co.uk
") else { return }
let dataTask = URLSession.shared.dataTask(with: url) { (data, response, error) in
    print(self,data)
}
dataTask.resume()

f.其他單例對象有可能延遲釋放,因為單例本身對外部對象強引用,儘管外部對象不會強引用單例,不過釋放是延遲的

class SingletonManager {
    static let shared = SingletonManager()
    
    func invoke(_ block: @escaping (()->Void)) {
        DispatchQueue.global().async {
            sleep(10)
            block()
        }
    }
}

SingletonManager.shared.invoke {
    print(self)
}

Instruments Allocation

前面說過Leaks和Memory Graph的限制,使用監控UIViewController或者UIView的工具對多數內存進行監控,但是畢竟這是多數情況,有些情況下是無法監控到的,那麼此時配合Instruments Allocation就是一個比較好的選擇,首先它可以通過快照的方式快速查對比內存的增長點也就可以幫助分析內存不釋放的原因,另外可以通過它查看當前內存被誰佔用也就有利於幫助我們分析內存佔用有針對性行的進行優化。

首先要了解,當我們向操作系統申請內存時系統分配的內存並不是物理內存地址而是虛擬內存 VM Regions 的地址。每個進程擁有的虛擬內存的空間大小是一樣的,32位的進程可以擁有4GB的虛擬內存,64位進程則更多。當真正使用內存時,操作系統才會將虛擬內存映射到物理內存。所以理論上當兩個進程A和B默認擁有相同的虛擬內存大小,當B使用內存時發現物理內存已經不夠用在OSX上會將不活躍內存寫入硬盤,叫做 swapping out。但是在iOS上面會直接發出內存警告 Memory warning 通知App清理無用內存(事實上也會引入 Compressed memory 壓縮一部分內存,需要的時候解壓)。

當然要使用這個工具之前建議先了解這個工具對內存類別劃分:

  • All Heap Allocations :進程運行過程中堆上分配的內存,簡單理解就是實際分配的內存,包括所有的類實例,比如UIViewController、UIView、Foundation數據結構等。比如:
    • Malloc 512.00KiB: 分配的512k堆內存,類似還有 Malloc 80.00KiB等
    • CTRun: Core Text對象內存
  • All Anonymous VM :主要包含一些系統模塊的內存佔用,以 VM: 開頭
    • VM:CG raster data:(光柵化數據,也就是像素數據。注意不一定是圖片,一塊显示緩存里也可能是文字或者其他內容。通常每像素消耗 4 個字節)
    • VM:Statck:棧內存(比如每個線程都會需要500KB)
    • VM:Image IO:(圖片編解碼緩存)
    • VM:IOSurface:用於存儲FBO、RBO等渲染數據的底層數據結構,是跨進程的,通常在CoreGraphics、OpenGLES、Metal之間傳遞紋理數據。
    • CoreAnimation: 動畫資源佔用內存
    • VM:IOAccelerator:圖片的CVPixelBuffer

需要注意,Allocations統計的 Heap Allocations & Anonymous VM(包括:All Heap Allocations和All Anonymous VM) 並不包括非動態的內存,以及部分其他動態庫創建的VM Region(比如:WebKit,ImageIO,CoreAnimation等虛擬內存區域),相對來說是低於實際運行內存的。

為了進一步了解內存實際分配情況,這裏不妨藉助一下 Instruments VM Tracker 這個工具,對於前面說過虛擬內存,這個工具是可以對虛擬內存實際分配情況有直觀展示的。

Virtual memory(虛擬內存) = Dirty Memory(已經寫入數據的內存) + Clean Memory(可以寫入數據的乾淨的內存) + Compressed Memory(對應OSX上的swapped memory)

Dirty Memory : 包括所有 Heap 中的對象、以上All Anonymous VM以及每個framework的 _DATA 段和 _Dirty_Data 段

Clean Memory:可以寫數據的乾淨的內存,不過對於開發者是read-only,操作系統負責寫入和移除,比如:System Framework、Binary Executable佔用的內存,framework都有_DATA_CONST段(不過當使用framework時會變成 Dirty memory )

Compressed Memory:由於iOS系統是沒有 swapped memory 的,取而代之的是 Compressed Memory ,通過壓縮內存可以降低大概一半的內存。不過遇到內存警告釋放內存的時候情況就複雜了些,比如遇到內存警告后通常可以試圖壓縮內存,而這時開發者會在收到警告后釋放一部分內存,遇到釋放內存的時候內存很可能會從壓縮內存再解壓去釋放反而峰值會增加。

前面提到過 Jetsam 對於內存的控制機制,這裏需要明確它做出內存警告的依據是 phys_footprint,而發生內存警告后系統默認清理的內存是 Clean Memory 而不會清理 Dirty Memory,畢竟有數據的內存系統也不知道是否還有用,無法自動清理。

Resident Memory = Dirty Memory + Clean Memory that loaded in physical memory

Resident Memory:已經被映射到虛擬內存中的物理內存,但是注意只有 phys_footprint 才是真正消耗的物理內存,也正是 Jetsam 判斷內存警告的依據。

Memory Footprint:App 實際消耗的物理內存,Jetsam 判斷內存警告的依據,包括:Dirty Memory 、Compressed Memory、NSCache, Purgeable、IOKit used
和部分加載到物理內存的Clean memory。

如果簡單總結:
Instruments Allocations 的 Heap Allocations & Anonymous VM 是整個App佔用的一部分,它又分為 Heap Allocations 為開發者申請的內存,而 Anonymous VM 是系統分配內存(但是並不是不需要優化)。這部分儘管不是 App 的所有消耗內存但卻是開發者最關注的。

Instruments VM Tracker 的 Dirty Memory 和 Swapped(對應iOS中的 Compressed Memory) 應該是開發者關注的主要內存佔用,比較接近於實際佔用內存,類似的是Xcode Navigator的內存也接近於最終的 Memory Footprint (多了調試佔用的內存而已一般可以認為是 App 實際佔用內存)

關於圖片的內存佔用有必要解釋一下:CGImage 持有原始壓縮格式DataBuffer(DataBuffer佔用本身比較小),通過類似引用計數管理真正的Image Bitmap Buffer,需要渲染時通過 RetainBytePtr 拿到 Bitmap Buffer 塞給VRAM(IOSurface),不渲染時 ReleaseBytePtr 釋 放Bitmap Buffer。通常在使用UIImageView時,系統會自動處理解碼過程,在主線程上解碼和渲染,會佔用CPU,容易引起卡頓。推薦使用ImageIO在後台線程執行圖片的解碼操作(可參考SDWebImageCoder)。但是ImageIO不支持webp。

二、持久化對象

很多時候內存泄漏確實可以很大程度上解決OOM問題,因為類似於UIViewController或者UIView中包含大量UIImageView的情況下,兩者不釋放很可能會有很大一塊關聯的內存得不到釋放造成內存泄漏。但是另一個問題是持久化對象,即使解決了所有內存泄漏的情況也並不代表就真正解決了內存泄漏問題,其中一個重要的因素就是持久化對象。

關於持久化對象這裏主要指的是類似於App進入后在主界面永遠不會釋放的對象,以及某些單例對象。象基本上基本上不kill整個app是無法釋放的,但是如果因為設計原因又在首頁有大量這樣的持久對象那麼OOM的問題理論上更加難以解決,因為此時要修改整個App結構幾乎是不可能的。

這裏簡單對非泄漏OOM情況進行分類:

  1. 首頁及其關聯頁面:比如首頁是UITabbarController相應的tab點擊之後也成為了持久化對象無法釋放
  2. 單例對象:特別是會加載一些大模型的單例,比如說單例中封裝了人臉檢測,如果人臉檢測模型比較大,首次使用人臉識別時加載的模型也會永遠得不到釋放
  3. 複雜的界面層級:Push、Pop是iOS常用的導航操作,但是如果界面設計過於複雜(甚至可以無限Push)那麼層級深了以後前面UINavigationController棧中的對象一直堆疊也會OOM
  4. 耗資源的對象:比如說播放器這種消耗資源的對象,理論上不會在同一個app內播放兩個音視頻,設計成單例反而是比較好的方案
  5. 圖片資源:圖片資源是app內最佔用內存的資源,一個不合適的圖片尺寸就可以導致OOM,比如一張邊長10000px的正方形圖片解碼后的大小是10000 * 10000 * 4 = 381M左右

首先說一下第一種情況,其實在早期iOS中(5.0及其之前的版本)針對以上情況有內存警lunload機制,通常在viewDidUnload()中釋放當前view,同時也是給開發者提供資源卸載的一個比較合適的時機,當UIViewController再次展示時會重新loadView(),而從iOS 6.0之後Apple建議相關操作放到didReceiveMemoryWarning()方法中,主要的原因是因為僅僅釋放當前根視圖並不會帶來大的內存釋放同時又造成了體驗問題,原本一個UITableView已經翻了幾頁了現在又要重新加載一遍。所以結論是在didReceiveMemoryWarning()放一些大的對象釋放操作,而不建議直接釋放view,但是不管怎麼樣一定要做恢復機制。實際的實踐是在我們的MV播放器中做了卸載操作,因為MV的預覽要經過A->B->C的push過程,A、B均包含了MV預覽播放器,而實際測試兩個播放器的內存佔用大概110M上下這是一部分很大的開銷,特別是對於iPhone 6等1g內存的手機。另外針對某個頁面有多個子控制器的情況避免一次加載所有的自控制器的情況,理想的情況是切換到對應的控制器時才會加載對應的控制器。

單例對象是另一種大內存持久對象,通常情況下對象本身佔用內存很有限,做成單例沒有什麼問題,但是這個對象引用的資源才是關注的重點,比如說我們產品中中有個主體識別模塊,依賴於一個AI模型,本身這個模塊也並非App操作的必經路徑,首次使用時加載,但是之後就不會釋放了,這樣一來對於使用過一次的用戶很有可能不再使用就沒必要一直佔用,解決的辦法自然是不用單例。

關於複雜的界面層級則完全是設計上的問題,只能通過界面交互設計進行控制,而對於耗資源對象上面也提到了盡量復用同一個對象即可,這裏不再贅述。

此外,前面說到FBO相關的內存,其實這部分內存也是需要手動釋放的,比如在產品中使用的播放器在用完之後並沒有及時釋放,調用 CVOpenGLESTextureCacheFlush() 及時清理(類似的還有使用基於OpenGL的濾鏡)。

內存峰值飆升

除了持久的內存佔用意外,有時會不恰當的操作會造成內存的飆升出現OOM,儘管這部分內存可能一會會被釋放掉不會長久的佔用內存但是內存的峰值本身就是很危險的操作。

圖片壓縮

首先重點關注一下圖片的內存佔用,圖片應該是最佔用內存的對象資源,理論上UILayer最終展示也會繪製一個bitmap,不過這裏主要說的是UIImage資源。一張圖片要最終展示出來要經過解碼、渲染的步驟,解碼操作的過程就是就是從data到bitmap的過程,這個過程中會佔用大量內存,因為data是壓縮對象,而解碼出來的是實實在在的像素信息。自然在開發中重用一些控件、做圖片資源優化是必要的,不過這些事實上在我們的產品中都是現成的內容,如何進一步優化是我們最關注的的。理論上這個問題可以歸結到第一種情況的範疇,就是如何讓首頁的圖片資源盡可能的小,答案也是顯而易見的:第一解碼過程中盡可能控制峰值,第二能用小圖片的絕不解碼一張大圖片。

比如一個圖片壓縮需求一張巨大的圖片要判斷圖片大小做壓縮處理,假設這張圖片是1280 * 30000的長圖,本來的目的是要判斷圖片大小進行適當的壓縮,比如說超過50M就進行80%壓縮,如果100M就進行50%壓縮,但是遇到的情況是這樣的:本來為了判斷圖片的大小以及保留新的圖片,原圖片A內存佔用大約146M,聲明了一個新對象B保留壓縮后的圖片,但是默認值是A原圖,根據情況給B賦值,實際情況是原圖146M+146M+中間壓縮結果30M左右,當前內存322M直接崩潰。優化這個操作的過程自然是盡量少創建中間變量,也不要賦值默認值,避免峰值崩潰。

關於產品中使用合適的圖片應該是多數app都會遇到的情況,比如首頁默認有10張圖,本來尺寸是比較小的UIImageView也沒有必要使用過大的圖片,不過實際情況很可能是通過後端請求的url來加載圖片。比如說一個64pt * 64pt的UIImageView要展示一個1080 * 1920 pixal的圖片內存佔用達在2x情況下多了126倍之多是完全沒必要的,不過後端的配置自然是不可信的,即使剛開始沒有問題說不準後面運營維護的時候上一張超大的圖片也是很有可能的。解決方式自然是向下採樣,不過這裏建議不要直接使用Core Graphics繪製,避免內存峰值過高,Apple也給了推薦的做法。

常見的壓縮方法:

func compressImage(_ image:UIImage, size:CGSize) -> UIImage? {
        let targetSize = CGSize(width: size.width*UIScreen.main.scale, height: size.height*UIScreen.main.scale)
        UIGraphicsBeginImageContext(targetSize)
        image.draw(in: CGRect(origin: CGPoint.zero, size: targetSize))
        let newImage = UIGraphicsGetImageFromCurrentImageContext()
        UIGraphicsEndImageContext()
        return newImage
    }

推薦的做法:

func downsamplingImage(url:URL, size:CGSize) -> UIImage? {
        let imageSourceOptions = [kCGImageSourceShouldCache:false] as CFDictionary
        guard let imageSource = CGImageSourceCreateWithURL(url as CFURL, imageSourceOptions) else { return nil }
        let maxDimension = max(size.width, size.height) * UIScreen.main.scale
        let downsamplingOptions = [
            kCGImageSourceCreateThumbnailFromImageAlways : true,
            kCGImageSourceShouldCacheImmediately : true ,
            kCGImageSourceCreateThumbnailWithTransform:true,
            kCGImageSourceThumbnailMaxPixelSize : maxDimension
        ] as CFDictionary
        guard let downsampleImage = CGImageSourceCreateThumbnailAtIndex(imageSource, 0, downsamplingOptions) else { return nil }
        let newImage = UIImage(cgImage: downsampleImage)
        return newImage
    }

大量循環操作

此外關於一些循環操作,如果操作本身比較耗內存,通常的做法就是使用 autoreleasepool 確保一個操作完成后內存及時釋放,但是在PHImageManager獲取圖片時這種方法並不是太湊效。比如說下面的一段代碼獲取相冊中30張照片保存到沙盒:

guard let cachePath = NSSearchPathForDirectoriesInDomains(.cachesDirectory, FileManager.SearchPathDomainMask.userDomainMask, true).first else { return }
let assets = getAssets() // top 30
for i in 0..<assets.count {
    let option = PHImageRequestOptions()
    option.isSynchronous = false
    option.isNetworkAccessAllowed = true
    PHImageManager.default().requestImage(for: assets[i], targetSize: CGSize(width: 1080, height: 1920), contentMode: PHImageContentMode.aspectFit, options: option) { (image, info) in
        if info?[PHImageResultIsDegradedKey] as? Bool == true {
            return
        }
        if let image = image {
            do {
                let savePath = cachePath + "/\(i).png"
                if FileManager.default.fileExists(atPath: savePath) {
                    try FileManager.default.removeItem(atPath: savePath)
                }
                try image.pngData()?.write(to: URL(fileURLWithPath: savePath))
            } catch {
                print("Error:\(error.localizedDescription)")
            }
        }
    }
}

實測在iOS 13下面內存峰值85M左右,執行后內存65M,比執行前多了52M而且這個內存應該是會一直常駐,這也是網上很多文章中提到的增加autoreleasepool來及時釋放內存的原因。改造之後代碼:

guard let cachePath = NSSearchPathForDirectoriesInDomains(.cachesDirectory, FileManager.SearchPathDomainMask.userDomainMask, true).first else { return }
let assets = getAssets()
for i in 0..<assets.count {
    autoreleasepool(invoking: {
        let option = PHImageRequestOptions()
        option.isSynchronous = false
        option.isNetworkAccessAllowed = true
        PHImageManager.default().requestImage(for: assets[i], targetSize: CGSize(width: 1080, height: 1920), contentMode: PHImageContentMode.aspectFit, options: option) { (image, info) in
            if info?[PHImageResultIsDegradedKey] as? Bool == true {
                return
            }
            if let image = image {
                do {
                    let savePath = cachePath + "/\(i).png"
                    if FileManager.default.fileExists(atPath: savePath) {
                        try FileManager.default.removeItem(atPath: savePath)
                    }
                    try image.pngData()?.write(to: URL(fileURLWithPath: savePath))
                } catch {
                    print("Error:\(error.localizedDescription)")
                }
            }
        }
    })
}

實測之後發現內存峰值降低到了65M左右,執行之後內存在50M左右,也就是峰值和之後常駐內存都有所降低,autoreleasepool有一定作用,但是作用不大,但是理論上這個常駐內存應該恢復到之前的10M左右的水平才對為什麼多了那麼多呢?原因是Photos獲取照片是有緩存的(注意在iPhone 6及以下設備不會緩存),這部分緩存如果進入後台會釋放(主要是IOSurface)。其實這個過程中內存主要包括兩部分 IOSurface 和 CG raster data ,那麼想要降低這兩部分內存其實針對上述場景最好的辦法是使用 PHImageManager.default().requestImageDataAndOrientation() 而不是 PHImageManager.default().requestImage() 實測上述情況內存峰值 18M 左右並且瞬間可降下來。那麼如果需求場景非要使用 PHImageManager.default().requestImage() 怎麼辦呢?答案是使用串行操作降低峰值。

guard let cachePath = NSSearchPathForDirectoriesInDomains(.cachesDirectory, FileManager.SearchPathDomainMask.userDomainMask, true).first else { return }
let semaphore = DispatchSemaphore(value: 0)
self.semaphore = semaphore
DispatchQueue.global().async {
    let assets = self.getAssets()
    for i in 0..<assets.count {
        print(1)
        autoreleasepool(invoking: {
            let option = PHImageRequestOptions()
            option.isSynchronous = false
            option.isNetworkAccessAllowed = true
            PHImageManager.default().requestImageDataAndOrientation(for: assets[i], options: option) { (data, _, orientation, info) in
                if info?[PHImageResultIsDegradedKey] as? Bool == true {
                    return
                }
                defer {
                    semaphore.signal()
                    print(4)
                }
                do {
                    print(3)
                    let savePath = cachePath + "/\(i).png"
                    if FileManager.default.fileExists(atPath: savePath) {
                        try FileManager.default.removeItem(atPath: savePath)
                    }
                    try data?.write(to: URL(fileURLWithPath: savePath))
                } catch {
                    print("Error:\(error.localizedDescription)")
                }
            }
        })
        print(2)
        _ = semaphore.wait(timeout: .now() + .seconds(10))
        print(5)
        
    }
}

通過串行控制以後內存峰值穩定在16M左右,並且執行之後內存沒有明顯增長,但是相應的操作效率自然是下降了,整體時長增高。

總結

本文從內存泄漏和內存佔用兩個角度分析了解決OOM的問題,也是產品中實際遇到問題的一次徹查結果,列舉了常見引起OOM的原因,也對持久內存佔用給了一些實踐的建議,對於比較難發現的leak情況做了示例演示,也是產品實際遇到的,事實上在我們的產品中通過上面的手段OOM降低了80%以上,整體的App框架也並沒有做其他修改,所以有類似問題的同學不妨試一下。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

※南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

※教你寫出一流的銷售文案?

※超省錢租車方案

如何 SSH 到 Linux 服務器里的特定目錄及執行命令?

你是不是有遇到過這樣的場景?使用 SSH 命令進入到服務器,然後再用 cd 命令進入到對應目錄,再繼續進行你的工作。

這種操作對於新手來講特別常見,良許之前也是這樣。在本文,老司機將帶你來進行更高效的操作,只需一步即可達到你想要的效果。

而且,不僅僅是實現快速進入到 Linux 服務器特定的目錄,還可以實現在連接上服務器的時候即執行一個對應的命令。

低效操作方式

如果你不知道本文介紹的方法,你很可能是分成兩步來操作的:

第一步:使用 SSH 命令進入到遠程服務器

ssh user@remote-system

第二步:使用 cd 命令進入到你想要的目錄

cd <some-directory>

一條命令快速進入到服務器指定目錄

上面提到的這種方式當然是可以的,但過於低效。這樣操作你需要使用兩條命令,但實際上,你完全可以使用一條命令即可實現你想要的效果,比如:

ssh -t pi@192.168.0.116 'cd /home/pi/tests ; bash'

通過這條命令,我們可以直接就進入到樹莓派(遠程服務器)中對應的目錄里(即 /home/pi/tests)。後續你就可以再繼續你的工作了。

在這裏, -t 選項是表示強制偽終端分配,即使標準輸入不是終端。如果不加的話,可能會有如下提示:

Pseudo-terminal will not be allocated because stdin

這裏我們再用一個動畫來直觀地演示這個過程:

除此之外,你還可以使用下面這個命令:

ssh -t pi@192.168.0.116 'cd /home/pi/tests ; exec bash'

或者:

ssh -t pi@192.168.0.116 'cd /home/pi/tests && exec bash -l'

在這裏,-l 選項將這個 bash 設置為登錄 shell。

在上面的三條命令里,最後的參數都是 bash,是因為我的遠程服務器默認的 shell 解釋器是 bash 。如果你不知道你遠程服務器所使用的 shell 解釋器,可以使用以下命令:

ssh -t pi@192.168.0.116 'cd /home/pi/tests && exec $SHELL'

一條命令遠程執行服務器命令

正如本文開頭所講的,我們不僅可以使用一條命令進入到遠程服務器指定目錄,還可以使用一條命令遠程執行服務器命令。甚至,我們還可以使用一條命令進入到遠程服務器的指定目錄,再執行一條命令。

其實所使用的方法都是一樣的,比如我們想進入到樹莓派的 /home/pi/tests 目錄,再執行 ls -al 命令,我們可以這樣輸入命令:

ssh -t pi@192.168.0.116 'cd /home/pi/tests && ls -al && exec $SHELL'

執行的結果如下:

[Alvin.Alvin-computer]  ssh -t pi@192.168.0.116 'cd /home/pi/tests && ls -al && exec $SHELL'
total 48
drwxr-xr-x  4 pi pi 4096 Apr  5 14:36 .
drwxr-xr-x 21 pi pi 4096 Apr 21 19:26 ..
drwxrwxrwx  7 pi pi 4096 Apr  5 17:28 GIC
drwxrwxrwx  3 pi pi 4096 Apr  5 17:37 gitchat
-rw-r--r--  1 pi pi  474 Apr  5 11:21 liangxu.json
-rwxr-xr-x  1 pi pi 8184 Mar 17 15:34 test
-rwxr-xr-x  1 pi pi 8184 Mar 17 15:34 test2
-rwxr-xr-x  1 pi pi 8184 Mar 17 15:34 test3
-rw-r--r--  1 pi pi  131 Mar 17 15:34 test.c

一個折中的方案

如果你覺得這條命令太長了不好敲,非要先進入到服務器,再 cd 到對應的目錄。那麼,我們可以修改遠程服務器的 .bashrc 文件。

vim ~/.bashrc

將你要執行的命令寫在裏面。比如在這個場景下,我們可以這樣加:

cd /home/pi/tests >& /dev/null

然後我們再執行 :wq 保存文件,再執行以下命令使更改生效:

source ~/.bashrc
或者
. ~/.bashrc

這樣,我們一進入到服務器后,就會自動進入到 /home/pi/tests 目錄里。如下動圖所示:

但是,這個有個明顯的弊端,就是我們只能進入到我們指定的目錄,如果要換成其它目錄,那隻能再改 .bashrc 文件了。

公眾號:良許Linux

有收穫?希望老鐵們來個三連擊,給更多的人看到這篇文章

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※南投搬家公司費用需注意的眉眉角角,別等搬了再說!

※教你寫出一流的銷售文案?

【遞歸題】正確的打開方式,面試官聽了都說精闢

前言

遞歸,是一個非常重要的概念,也是面試中非常喜歡考的。因為它不但能考察一個程序員的算法功底,還能很好的考察對時間空間複雜度的理解和分析。

本文只講一題,也是幾乎所有算法書講遞歸的第一題,但力爭講出花來,在這裏分享四點不一樣的角度,讓你有不同的收穫。

  • 時空複雜度的詳細分析
  • 識別並簡化遞歸過程中的重複運算
  • 披上羊皮的狼
  • 適當炫技助我拿到第一份工作

算法思路

大家都知道,一個方法自己調用自己就是遞歸,沒錯,但這隻是理解遞歸的最表層的理解。

那麼遞歸的實質是什麼?

答:遞歸的實質是能夠把一個大問題分解成比它小點的問題,然後我們拿到了小問題的解,就可以用小問題的解去構造大問題的解。

那小問題的解是如何得到的?

答:用再小一號的問題的解構造出來的,小到不能再小的時候就是到了零號問題的時候,也就是 base case 了。

那麼總結一下遞歸的三個步驟:

Base case:就是遞歸的零號問題,也是遞歸的終點,走到最小的那個問題,能夠直接給出結果,不必再往下走了,否則,就會成死循環;

拆解:每一層的問題都要比上一層的小,不斷縮小問題的 size,才能從大到小到 base case;

組合:得到了小問題的解,還要知道如何才能構造出大問題的解。

所以每道遞歸題,我們按照這三個步驟來分析,把這三個問題搞清楚,代碼就很容易寫了。

斐波那契數列

這題雖是老生常談了,但相信我這裏分享的一定會讓你有其他收穫。

題目描述

斐波那契數列是一位意大利的數學家,他閑着沒事去研究兔子繁殖的過程,研究着就發現,可以寫成這麼一個序列:1,1,2,3,5,8,13,21…也就是每個數等於它前兩個數之和。那麼給你第 n 個數,問 F(n) 是多少。

解析

用數學公式表示很簡單:

f(n) = f(n-1) + f(n-2)

代碼也很簡單,用我們剛總結的三步:

  • base case: f(0) = 0, f(1) = 1.
  • 分解:f(n-1), f(n-2)
  • 組合:f(n) = f(n-1) + f(n-2)

那麼寫出來就是:

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        }
        return fib(N-1) + fib(N-2);
    }
}

但是這種解法 Leetcode 給出的速度經驗只比 15% 的答案快,因為,它的時間複雜度實在是太高了!

過程分析

那這就是我想分享的第一點,如何去分析遞歸的過程。

首先我們把這顆 Recursion Tree 畫出來,比如我們把 F(5) 的遞歸樹畫出來:

那實際的執行路線是怎樣的?

首先是沿着最左邊這條線一路到底:F(5) → F(4) → F(3) → F(2) → F(1),好了終於有個 base case 可以返回 F(1) = 1 了,然後返回到 F(2) 這一層,再往下走,就是 F(0),又觸底反彈,回到 F(2),得到 F(2) = 1+0 =1 的結果,把這個結果返回給 F(3),然後再到 F(1),拿到結果后再返回 F(3) 得到 F(3) = 左 + 右 = 2,再把這個結果返上去…

這種方式本質上是由我們計算機的馮諾伊曼體系造就的,目前一個 CPU 一個核在某一時間只能執行一條指令,所以不能 F(3) 和 F(4) 一起進行了,一定是先執行了 F(4) (本代碼把 fib(N-1) 放在前面),再去執行 F(3).

我們在 IDE 里 debug 就可以看到棧裏面的情況:這裏確實是先走的最左邊這條線路,一共有 5 層,然後再一層層往上返回。

時間複雜度分析

如何評價一個算法的好壞?

很多問題都有多種解法,畢竟條條大路通羅馬。但如何評價每種方法的優劣,我們一般是用大 O 表達式來衡量時間和空間複雜度。

時間複雜度:隨着自變量的增長,所需時間的增長情況。

這裏大 O 表示的是一個算法在 worst case 的表現情況,這就是我們最關心的,不然春運搶車票的時候系統 hold 不住了,你跟我說這個算法很優秀?

當然還有其他衡量時間和空間的方式,比如

Theta: 描述的是 tight bound Omega(n):
這個描述的是 best case,最好的情況,沒啥意義

這也給我們了些許啟發,不要說你平時表現有多好,沒有意義;面試衡量的是你在 worst case 的水平;不要說面試沒有發揮出你的真實水平,扎心的是那就是我們的真實水平。

那對於這個題來說,時間複雜度是多少呢?

答:因為我們每個節點都走了一遍,所以是把所有節點的時間加起來就是總的時間。

在這裏,我們在每個節點上做的事情就是相加求和,是 O(1) 的操作,且每個節點的時間都是一樣的,所以:

總時間 = 節點個數 * 每個節點的時間

那就變成了求節點個數的數學題:

在 N = 5 時,

最上面一層有1個節點,
第二層 2 個,
第三層 4 個,
第四層 8 個,
第五層 16 個,如果填滿的話,想象成一顆很大的樹:)

這裏就不要在意這個沒填滿的地方了,肯定是會有差這麼幾個 node,但是大 O 表達的時間複雜度我們剛說過了,求的是 worst case.

那麼總的節點數就是:
1 + 2 + 4 + 8 + 16

這就是一個等比數列求和了,當然你可以用數學公式來算,但還有個小技巧可以幫助你快速計算:

其實前面每一層的節點相加起來的個數都不會超過最後一層的節點的個數,總的節點數最多也就是最後一層節點數 * 2,然後在大 O 的時間複雜度裏面常數項也是無所謂的,所以這個總的時間複雜度就是:

最後一層節點的個數:2^n

空間複雜度分析

一般書上寫的空間複雜度是指:

算法運行期間所需佔用的所有內存空間

但是在公司里大家常用的,也是面試時問的指的是
Auxiliary space complexity:

運行算法時所需佔用的額外空間。

舉例說明區別:比如結果讓你輸出一個長度為 n 的數組,那麼這 O(n) 的空間是不算在算法的空間複雜度里的,因為這個空間是跑不掉的,不是取決於你的算法的。

那空間複雜度怎麼分析呢?

我們剛剛說到了馮諾伊曼體系,從圖中也很容易看出來,是最左邊這條路線佔用 stack 的空間最多,一直不斷的壓棧,也就是從 5 到 4 到 3 到 2 一直壓到 1,才到 base case 返回,每個節點佔用的空間複雜度是 O(1),所以加起來總的空間複雜度就是 O(n).

優化算法

那我們就想了,為什麼這麼一個簡簡單單的運算竟然要指數級的時間複雜度?到底是為什麼讓時間如此之大。

那也不難看出來,在這棵 Recursion Tree 里,有太多的重複計算了。

比如一個 F(2) 在這裏都被計算了 3 次,F(3) 被計算了 2 次,每次還都要再重新算,這不就是狗熊掰棒子嗎,真的是一把辛酸淚。

那找到了原因之後,為了解決這種重複計算,計算機採用的方法其實和我們人類是一樣的:記筆記。

對很多職業來說,比如醫生、律師、以及我們工程師,為什麼越老經驗值錢?因為我們見得多積累的多,下次再遇到類似的問題時,能夠很快的給出解決方案,哪怕一時解決不了,也避免了一些盲目的試錯,我們會站在過去的高度不斷進步,而不是每次都從零開始。

回到優化算法上來,那計算機如何記筆記呢?

我們要想求 F(n),無非也就是要
記錄 F(0) ~ F(n-1) 的值,
那選取一個合適的數據結構來存儲就好了。

那這裏很明顯了,用一個數組來存:

Index 0 1 2 3 4 5
F(n) 0 1 1 2 3 5

那有了這個 cheat sheet,我們就可以從前到后得到結果了,這樣每一個點就只算了一遍,用一個 for loop 就可以寫出來,代碼也非常簡單。

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        }
        if (N== 1) {
            return 1;
        }
        int[] notes = new int[N+1];
        notes[0] = 0;
        notes[1] = 1;
        for(int i = 2; i <= N; i++) {
            notes[i] = notes[i-1] + notes[i-2];
        }
        return notes[N];
    }
}

這個速度就是 100% 了~

但是我們可以看到,空間應該還有優化的餘地。

那仔細想想,其實我們記筆記的時候需要記錄這麼多嗎?需要從幼兒園到小學到初中到高中的筆記都留着嗎?

那其實每項的計算只取決於它前面的兩項,所以只用保留這兩個就好了。

那我們可以用一個長度為 2 的數組來計算,或者就用 2 個變量。

更新代碼:

class Solution {
    public int fib(int N) {
        int a = 0;
        int b = 1;
        if(N == 0) {
            return a;
        }
        if(N == 1) {
            return b;
        }
        for(int i = 2; i <= N; i++) {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return b;
    }
}

這樣我們就把空間複雜度優化到了 O(1),時間複雜度和用數組記錄一樣都是 O(n).

這種方法其實就是動態規劃 Dynamic Programming,寫出來的代碼非常簡單。

那我們比較一下 Recursion 和 DP:

Recursion 是從大到小,層層分解,直到 base case 分解不了了再組合返回上去;
DP 是從小到大,記好筆記,不斷進步。
也就是 Recursion + Cache = DP

如何記錄這個筆記,如何高效的記筆記,這是 DP 的難點。

有人說 DP 是拿空間換時間,但我不這麼認為,這道題就是一個很好的例證。

在用遞歸解題時,我們可以看到,空間是 O(n) 在棧上的,但是用 DP 我們可以把空間優化到 O(1),DP 可以做到時間空間的雙重優化。

其實呢,斐波那契數列在現實生活中也有很多應用。

比如在我司以及很多大公司里,每個任務要給分值,1分表示大概需要花1天時間完成,然後分值只有>1,2,3,5,8這5種,(如果有大於8分的任務,就需要把它 break down 成8分以內的,以便大家在>兩周內能完成。)
因為任務是永遠做不完的而每個人的時間是有限的,所以每次小組會開會,挑出最重要的任務讓大家來>做,然後每個人根據自己的 available 的天數去 pick up 相應的任務。

那有同學可能會想,這題這麼簡單,這都 2020 年了,面試還會考么?

答:真的會。

只是不能以這麼直白的方式給你了。

比如很有名的爬樓梯問題:

一個 N 階的樓梯,每次能走一層或者兩層,問一共有多少種走法。

這個題這麼想:

站在當前位置,只能是從前一層,或者前兩層上來的,所以 f(n) = f(n-1) + f(n-2).

這題是我當年面試時真實被問的,那時我還在寫 python,為了炫技,還用了lambda function:

f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)

遞歸的寫法時間複雜度太高,所以又寫了一個 for loop 的版本

def fib(n)
  a, b = 1, 1
  for i in range(n-1):
    a, b = b, a+b
  return a 

然後還寫了個 caching 的方法:

def cache(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper
@cache
def fibR(n):
    if n==1 or n==2: return 1
    return fibR(n-1) + fibR(n-2)

還順便和面試官聊了下 tail recursion:

tail recursion 尾遞歸:就是遞歸的這句話是整個方法的最後一句話。

那這個有什麼特別之處呢?

尾遞歸的特點就是我們可以很容易的把它轉成 iterative 的寫法,當然有些智能的編譯器會自動幫我們做了(不是說顯性的轉化,而是在運行時按照 iterative 的方式去運行,實際消耗的空間是O(1))

那為什麼呢?

因為回來的時候不需要 backtrack,遞歸這裏就是最後一步了,不需要再往上一層返值。

def fib(n, a=0, b=1):
    if n==0: return a
      if n==1: return b
    return fib(n-1, b, a+b)

最終,拿出了我的殺手鐧:lambda and reduce

fibRe = lambda n: reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])

看到面試官滿意的表情后,就開始繼續深入的聊了…

所以說,不要以為它簡單,同一道題可以用七八種方法來解,分析好每個方法的優缺點,引申到你可以引申的地方,展示自己紮實的基本功,這場面試其實就是你 show off 的機會,這樣才能騙過面試官啊~lol

這就是本文的所有內容了,不知道大家看完感受如何?留言告訴我你的感受吧~

點擊在看,鼓勵下我啊!

瞎寫評論,顯得我很紅啊!

轉發轉發轉發,愛她,就送給她!

還想跟我看更多數據結構和算法題的小夥伴們,記得關注我,我是程序零世界,算法就這麼回事。

作者:小齊本齊

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧