從 Pulsar Client 的原理到它的監(jiān)控面板
背景前段時(shí)間業(yè)務(wù)團(tuán)隊(duì)偶爾會(huì)碰到一些 Pulsar 使用的問(wèn)題，比如消息阻塞不消費(fèi)了、生產(chǎn)者消息發(fā)送緩慢等各種問(wèn)題。雖然我們有個(gè)監(jiān)控頁(yè)面可以根據(jù) topic 維度查看他的發(fā)送狀態(tài)，
數(shù)據(jù)結(jié)構(gòu)與算法是程序員內(nèi)功體現(xiàn)的重要標(biāo)準(zhǔn)之一，且數(shù)據(jù)結(jié)構(gòu)也應(yīng)用在各個(gè)方面，業(yè)界更有程序=數(shù)據(jù)結(jié)構(gòu)+算法這個(gè)等式存在。各個(gè)中間件開(kāi)發(fā)者，架構(gòu)師他們都在努力的優(yōu)化中間件、項(xiàng)目結(jié)構(gòu)以及算法提高運(yùn)行效率和降低內(nèi)存占用，在這里數(shù)據(jù)結(jié)構(gòu)起到相當(dāng)重要的作用。此外數(shù)據(jù)結(jié)構(gòu)也蘊(yùn)含一些面向?qū)ο蟮乃枷耄蕦W(xué)好掌握數(shù)據(jù)結(jié)構(gòu)對(duì)邏輯思維處理抽象能力有很大提升。
為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法？如果你還是學(xué)生，那么這門(mén)課程是必修的，考研基本也是必考科目。工作在內(nèi)卷嚴(yán)重的大廠中找工作數(shù)據(jù)結(jié)構(gòu)與算法也是面試、筆試必備的非常重要的考察點(diǎn)。如果工作了數(shù)據(jù)結(jié)構(gòu)和算法也是內(nèi)功提升一個(gè)非常重要的體現(xiàn)，對(duì)于程序員來(lái)說(shuō)，想要得到滿意的結(jié)果，數(shù)據(jù)結(jié)構(gòu)與算法是必備功力！
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。
簡(jiǎn)言之，數(shù)據(jù)結(jié)構(gòu)是一系列的存儲(chǔ)結(jié)構(gòu)按照一定執(zhí)行規(guī)則、配合一定執(zhí)行算法所形成的高效的存儲(chǔ)結(jié)構(gòu)。在我們所熟知的關(guān)系數(shù)據(jù)庫(kù)、非關(guān)系數(shù)據(jù)庫(kù)、搜索引擎存儲(chǔ)、消息隊(duì)列等都是比較牛的大型數(shù)據(jù)結(jié)構(gòu)良好的運(yùn)用。當(dāng)然這些應(yīng)用中間件不單單要考慮單純的結(jié)構(gòu)問(wèn)題。還考慮實(shí)際os、網(wǎng)絡(luò)等其他因素。
而對(duì)于數(shù)據(jù)結(jié)構(gòu)與算法這個(gè)專欄。我們程序員更要掌握的首先是在內(nèi)存中運(yùn)行的抽象的數(shù)據(jù)結(jié)構(gòu)。是一個(gè)相對(duì)比較單一的數(shù)據(jù)結(jié)構(gòu)類型，比如線性結(jié)構(gòu)、樹(shù)、圖等等.
在數(shù)據(jù)結(jié)構(gòu)與算法中，數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)很多人搞不清其中的關(guān)系。通過(guò)畫(huà)一張圖來(lái)捋一捋，然后下面舉個(gè)例子給大家分享一下。
用戶信息表users
id | name | sex |
001 | bigsai | man |
002 | smallsai | man |
003 | 菜虛鯤 | woman |
Users的pojo對(duì)象
class User{ //略 int id; String name; String sex;}//list和woman是數(shù)據(jù)List<User>users;//數(shù)據(jù)對(duì)象listList<User>women;//數(shù)據(jù)對(duì)象womenusers.add(new User(001,"bigsai","man"));//添加數(shù)據(jù)元素 一個(gè)user由（001，bigsai，man）三個(gè)數(shù)據(jù)項(xiàng)組成 users.add(new User(002,"smallsai","man"));//數(shù)據(jù)元素users.add(new User(003,"菜虛鯤","woman"));//數(shù)據(jù)元素woman.add(users.get(2));//003,"菜虛鯤","woman"三個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的一個(gè)數(shù)據(jù)元素數(shù)據(jù)：對(duì)客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合總稱。上述表中的三條用戶信息的記錄就是數(shù)據(jù)(也可能多表多集合這里只有一個(gè))。這些數(shù)據(jù)一般都是用戶輸入或者是自定義構(gòu)造完成。當(dāng)然，還有一些圖像、聲音也是數(shù)據(jù)。
數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)構(gòu)成！可認(rèn)為是一個(gè)pojo對(duì)象、或者是數(shù)據(jù)庫(kù)的一條記錄。比如菜虛鯤那條記錄就是一個(gè)數(shù)據(jù)元素。
數(shù)據(jù)項(xiàng)： 而構(gòu)成用戶字段/屬性的有id、name、sex等，這些就是數(shù)據(jù)項(xiàng).數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的最小不可分割字段。可以看作一個(gè)pojo對(duì)象或者一張表(people)的一個(gè)屬性/字段的值。
數(shù)據(jù)對(duì)象：是相同性質(zhì)數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)子集，比如上面的users表、list集合、woman集合都是數(shù)據(jù)對(duì)象。單獨(dú)一張表，一個(gè)集合都可以是一個(gè)數(shù)據(jù)對(duì)象。
總的捋一捋，數(shù)據(jù)范圍最廣，所有數(shù)據(jù)即數(shù)據(jù)，而數(shù)據(jù)對(duì)象僅僅是有相同性質(zhì)的一個(gè)集合，這個(gè)集合是數(shù)據(jù)的子集，但并不是數(shù)據(jù)的基本單位，而數(shù)據(jù)元素才是數(shù)據(jù)的基本單位。舉個(gè)例子表cat和表dog都是數(shù)據(jù)，然后表cat是個(gè)數(shù)據(jù)對(duì)象(因?yàn)槎济枋鯿at這種對(duì)象)，但是數(shù)據(jù)的基本單位并不是貓和狗，而是他們的具體的每一條記錄，比如小貓咪1號(hào)，大貓咪二號(hào)，哈士奇1號(hào)，藏獒2號(hào)這些每一條記錄才是數(shù)據(jù)的基本單位。
還有數(shù)據(jù)類型，抽象數(shù)據(jù)類型也在下面講一講。
數(shù)據(jù)類型
抽象數(shù)據(jù)類型(ADT)：抽象數(shù)據(jù)類型（ADT）是一個(gè)實(shí)現(xiàn)包括存儲(chǔ)數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)以及實(shí)現(xiàn)基本操作的算法。使得只研究和使用它的結(jié)構(gòu)而不用考慮它的實(shí)現(xiàn)細(xì)節(jié)成為可能。比如我們使用List、Map、Set等等只需要了解它的API和性質(zhì)功能即可。而具體的實(shí)現(xiàn)可能是不同的方案，比如List的實(shí)現(xiàn)有數(shù)組和鏈表不同選擇。
邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)就是順序表、鏈表之類。而非線性就是集合、樹(shù)、圖這些結(jié)構(gòu)。
存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(又稱映像，也稱物理結(jié)構(gòu))，存儲(chǔ)結(jié)構(gòu)主要分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列(哈希)存儲(chǔ)，這幾種存儲(chǔ)通過(guò)下面這張圖簡(jiǎn)單了解一下(僅僅為理解不考慮更多)：
數(shù)據(jù)的運(yùn)算：施加在數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn)，運(yùn)算的定義基于邏輯結(jié)構(gòu)，運(yùn)算的實(shí)現(xiàn)基于存儲(chǔ)結(jié)構(gòu)。
在這里容易混淆的是邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的概念。對(duì)于邏輯結(jié)構(gòu)，不難看得出邏輯二字，邏輯關(guān)系也就是兩者存在數(shù)據(jù)上的關(guān)系而不考慮物理地址的關(guān)系，比如線性結(jié)構(gòu)和非線性結(jié)構(gòu)，它描述的是一組數(shù)據(jù)中聯(lián)系的方式和形式，他針對(duì)的是數(shù)據(jù)。看中的是數(shù)據(jù)結(jié)構(gòu)的功能，比如線性表就是前后有序的，我需要一個(gè)有序的集合就可以使用線性表。
而存儲(chǔ)結(jié)構(gòu)就是跟物理地址掛鉤的。因?yàn)橥瑯舆壿嫿Y(jié)構(gòu)采用不同存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)適用場(chǎng)景和性能可能不同。比如同樣是線性表,可能有多種存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方式。比如順序表和鏈表(Arraylist,Linkedlist)它們的存儲(chǔ)結(jié)構(gòu)就不同，一個(gè)是順序存儲(chǔ)(數(shù)組)實(shí)現(xiàn)，一個(gè)是鏈?zhǔn)酱鎯?chǔ)(鏈表)實(shí)現(xiàn)。它關(guān)注的是計(jì)算機(jī)運(yùn)行物理地址的關(guān)系。但通常同一類存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的一些數(shù)據(jù)結(jié)構(gòu)有一些類似的共同點(diǎn)和缺點(diǎn)(線性易查難插、鏈?zhǔn)揭撞咫y查等等)。
上面講了數(shù)據(jù)結(jié)構(gòu)相關(guān)概念，下面對(duì)算法分析的一些概念進(jìn)行描述。
算法的五個(gè)重要特征：有窮性、確定性、可行性、輸入、輸出。這些從字面意思即可理解，其中有窮性強(qiáng)調(diào)算法要有結(jié)束的時(shí)候不能無(wú)限循環(huán)；而確定性是每條指令有它意義，相同的輸入得到相同的輸出；可行性是指算法每個(gè)步驟經(jīng)過(guò)若干次執(zhí)行可以實(shí)現(xiàn)；輸入是0個(gè)或多個(gè)輸入(可0);輸出是1個(gè)或多個(gè)輸出(一定要有輸出)。
而一個(gè)好的算法，通常更要著重考慮的是效率和空間資源占用(時(shí)間復(fù)雜度和空間復(fù)雜度)，通常復(fù)雜度更多描述的是一個(gè)量級(jí)程度而很少用具體數(shù)字描述。
概念：是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))
空間復(fù)雜度其實(shí)在算法的衡量占比是比較低的(我們經(jīng)常使用犧牲空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)和算法)，但是不能忽視空間復(fù)雜度中重要性。無(wú)論在刷題還是實(shí)際項(xiàng)目生產(chǎn)內(nèi)存都是一個(gè)極大額指標(biāo)。對(duì)于Java而言更是如此。本身內(nèi)存就大，如果采用的存儲(chǔ)邏輯不太好會(huì)占用更多的系統(tǒng)資源，對(duì)服務(wù)造成壓力。
而算法很多情況都是犧牲空間換取時(shí)間(效率)。就比如我們熟知的字符串匹配String.contains()方法，我們都知道他是暴力破解，時(shí)間復(fù)雜度為O(n^2),不需要借助額外內(nèi)存。而KMP算法在效率和速度上都原生暴力方法，但是KMP要借助其他數(shù)組(next[])進(jìn)行標(biāo)記儲(chǔ)存運(yùn)算。就用到了空間開(kāi)銷(xiāo)。再比如歸并排序也會(huì)借助新數(shù)組在遞歸分冶的適合進(jìn)行逐級(jí)計(jì)算，提高效率，但增加點(diǎn)影響不大的內(nèi)存開(kāi)銷(xiāo)。
當(dāng)然，算法的空間花銷(xiāo)最大不能超過(guò)jvm設(shè)置的最大值，一般為2G.(2147483645)如果開(kāi)二維數(shù)組多種多維數(shù)據(jù)不要開(kāi)的太大，可能會(huì)導(dǎo)致heap OutOfMemoryError。
概念：計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述了該算法的運(yùn)行時(shí)間。這是一個(gè)關(guān)于代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況。
時(shí)間復(fù)雜度的排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n)
常見(jiàn)時(shí)間復(fù)雜度：對(duì)于時(shí)間復(fù)雜度，很多人的概念是比較模糊的。下面舉例子說(shuō)明一些時(shí)間復(fù)雜度。
O(1): 常數(shù)函數(shù)
O(logn): 對(duì)數(shù)函數(shù)
O(n): 線性函數(shù)
O(nlogn):
O(n^2)
當(dāng)然如果同樣是n=10000.那么不同時(shí)間復(fù)雜度額算法執(zhí)行次數(shù)、時(shí)間也不同。
具體 | n | 執(zhí)行次數(shù) |
O(1) | 10000 | 1 |
O(log2n) | 10000 | 14 |
O( n^1/2) | 10000 | 100 |
O(n) | 10000 | 10000 |
O(nlog2 n) | 10000 | 140000 |
O(n^2) | 10000 | 100000000 |
O(n^3) | 10000 | 1000000000000 |
降低算法復(fù)雜度有些會(huì)靠數(shù)據(jù)結(jié)構(gòu)的特性和優(yōu)勢(shì)，比如二叉排序樹(shù)的查找，線段樹(shù)的動(dòng)態(tài)排序等等，這些數(shù)據(jù)結(jié)構(gòu)解決某些問(wèn)題有些非常良好的性能。還有的是靠算法策略解決，比如同樣是排序，冒泡排序這種笨而簡(jiǎn)單的方法就是O(n2),但快排、歸并等聰明方法就能O(nlogn)。要想變得更快，那就得掌握更高級(jí)的數(shù)據(jù)結(jié)構(gòu)和更精巧的算法。
時(shí)間復(fù)雜度計(jì)算 時(shí)間復(fù)雜度計(jì)算一般步驟：1、找到執(zhí)行次數(shù)最多的語(yǔ)句; 2、計(jì)算語(yǔ)句執(zhí)行的數(shù)量級(jí) ; 3、用O表示結(jié)果。并且有兩個(gè)規(guī)則：
加法規(guī)則： 同一程序下如果多個(gè)并列關(guān)系的執(zhí)行語(yǔ)句那么取最大的那個(gè),eg:
T(n)=O(m)+O(n)=max(O(m),O(n)); T(n)=O(n)+O(nlogn)=max(O(n),O(nlogn))=O(nlogn);乘法規(guī)則：循環(huán)結(jié)構(gòu)，時(shí)間復(fù)雜度按乘法進(jìn)行計(jì)算,eg：
T(n)=O(m)*O(n)=O(mn)T(n)=O(m)*O(m)=O(m^2)(兩層for循環(huán))當(dāng)然很多算法的時(shí)間復(fù)雜度還跟輸入的數(shù)據(jù)有關(guān)，分為還會(huì)有最優(yōu)時(shí)間復(fù)雜度(可能執(zhí)行次數(shù)最少時(shí))，最壞時(shí)間復(fù)雜度(執(zhí)行次數(shù)最少時(shí))，平均時(shí)間復(fù)雜度，這在排序算法中已經(jīng)具體分析，但我們通常使用平均時(shí)間復(fù)雜度來(lái)衡量一個(gè)算法的好壞。
捋過(guò)數(shù)據(jù)結(jié)構(gòu)與算法基本概念的介紹，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法方面，個(gè)人把經(jīng)典的數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)過(guò)程步驟寫(xiě)在下面，希望能給大家一個(gè)參考：
相信看完這篇文章，你應(yīng)該對(duì)數(shù)據(jù)結(jié)構(gòu)與算法有個(gè)不錯(cuò)的認(rèn)知。數(shù)據(jù)結(jié)構(gòu)與算法有著非常密切的關(guān)聯(lián)，數(shù)據(jù)結(jié)構(gòu)是為了實(shí)現(xiàn)某種算法，算法是核心目的。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之前，可以先參考書(shū)本或者博客先了解其功能，再研究其運(yùn)行原理，再動(dòng)手實(shí)戰(zhàn)(編寫(xiě)數(shù)據(jù)結(jié)構(gòu)或者相關(guān)題目)這樣層次漸進(jìn)，想要深入的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法光理解是不行的，需要有大量代碼實(shí)戰(zhàn)才可。并且這條路是沒(méi)有止境的，活到老，學(xué)到老，刷到老。
本文鏈接：http://www.tebozhan.com/showinfo-26-15467-0.html數(shù)據(jù)結(jié)構(gòu)與算法緒論
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： 一文帶你徹底了解JMX
下一篇： 微服務(wù)設(shè)計(jì)必看：深度解析Netflix Eureka的底層實(shí)現(xiàn)
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)