Array數(shù)組的概念和用法

這篇文章主要介紹“Array數(shù)組的概念和用法”，在日常操作中，相信很多人在Array數(shù)組的概念和用法問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Array數(shù)組的概念和用法”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

成都創(chuàng)新互聯(lián)公司是由多位在大型網(wǎng)絡(luò)公司、廣告設(shè)計(jì)公司的優(yōu)秀設(shè)計(jì)人員和策劃人員組成的一個(gè)具有豐富經(jīng)驗(yàn)的團(tuán)隊(duì)，其中包括網(wǎng)站策劃、網(wǎng)頁(yè)美工、網(wǎng)站程序員、網(wǎng)頁(yè)設(shè)計(jì)師、平面廣告設(shè)計(jì)師、網(wǎng)絡(luò)營(yíng)銷人員及形象策劃。承接：成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站改版、網(wǎng)頁(yè)設(shè)計(jì)制作、網(wǎng)站建設(shè)與維護(hù)、網(wǎng)絡(luò)推廣、數(shù)據(jù)庫(kù)開(kāi)發(fā),以高性價(jià)比制作企業(yè)網(wǎng)站、行業(yè)門戶平臺(tái)等全方位的服務(wù)。

數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)筆記。

數(shù)組概念

數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一組連續(xù)的內(nèi)存空間，來(lái)存儲(chǔ)一組具有相同類型的數(shù)據(jù), 并且不支持動(dòng)態(tài)擴(kuò)容。

• 線性表

  線性表就是數(shù)據(jù)排成一條線一樣的數(shù)據(jù)結(jié)構(gòu)，每個(gè)線性表最多只有前后兩個(gè)方向，數(shù)組，鏈表丶隊(duì)列丶棧等都是線性表數(shù)據(jù)結(jié)構(gòu)。

• 非線性表

  非線性表就是數(shù)據(jù)不規(guī)則，與線性表是相對(duì)立的，比如二叉樹丶堆丶等，在非線性表中，數(shù)據(jù)之間并不是簡(jiǎn)單的前后關(guān)系。

數(shù)組隨機(jī)訪問(wèn)

• 公式

  address[i] = base_address + i * data_type_size

  address[i] :下標(biāo) i 的地址值。

  base_address：數(shù)組的首地址。

  data_type_size：數(shù)組中每個(gè)元素的大小，也就是數(shù)據(jù)類型大小(字節(jié))，例如int是4個(gè)字節(jié)。

數(shù)組的增加和刪除

數(shù)組(Array) 在增刪查這三個(gè)動(dòng)作中，查詢是高效的，但是增和刪是低效的，查詢高效是因?yàn)?strong>數(shù)組支持隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度是 O(1),這里就不多贅述了，但是在增加和刪除的動(dòng)作中，因?yàn)闀?huì)涉及數(shù)據(jù)搬移，所以時(shí)間復(fù)雜度是 O(n)，下面來(lái)詳細(xì)講解。

• 低效的"插入"和"刪除"

  	int[] info = new int[6];

  插入

  數(shù)組 info是一個(gè)一維數(shù)組，其內(nèi)容是 33,44,66,77,88現(xiàn)在需要在下標(biāo) 2的位置插入55，將其變成33 44 55 66 77 88的數(shù)組，這其中涉及將下標(biāo) 2到下標(biāo) 4的之間進(jìn)行數(shù)據(jù)進(jìn)行搬移，完成后在下標(biāo) 2的位置插入 55, 其復(fù)雜度是 O(n)， 但如果是在最后進(jìn)行插入的話其復(fù)雜度是 O(1)。

  

  刪除

  還拿數(shù)組 info來(lái)舉例，數(shù)組刪除前其內(nèi)容是 33,44,00,55,66,77現(xiàn)在進(jìn)行刪除操作，刪除下標(biāo)為 2內(nèi)容，這其中涉及將下標(biāo) 3 到 5 的內(nèi)容向前搬移，其操作的時(shí)間復(fù)雜度是 O(n)，如果是是刪除最后一位且后面沒(méi)有內(nèi)容，則其時(shí)間復(fù)雜度是O(1)。

  

  因插入和刪除操作會(huì)涉及到數(shù)據(jù)搬移,所以說(shuō)他是低效的。

  CPU緩存**

  Cpu緩存的最小單位是Cpu緩存行，一個(gè)緩存行大小通常是64字節(jié)(取決于CPU)，試想一下你正在遍歷一個(gè)長(zhǎng)度為 16 的 long 數(shù)組 data[16]，原始數(shù)據(jù)自然存在于主內(nèi)存中，訪問(wèn)過(guò)程描述如下：

  1：訪問(wèn) data[0]，CPU core 嘗試訪問(wèn) CPU Cache，未命中。

  2：嘗試訪問(wèn)主內(nèi)存，操作系統(tǒng)一次訪問(wèn)的單位是一個(gè) Cache Line 的大小 — 64 字節(jié)，這意味著：既從主內(nèi)存中獲取3：到了 data[0] 的值，同時(shí)將 data[0] ~ data[7] 加入到了 CPU Cache 之中，

  4：訪問(wèn) data[1]~data[7]，CPU core 嘗試訪問(wèn) CPU Cache，命中直接返回。

  5：訪問(wèn) data[8]，CPU core 嘗試訪問(wèn) CPU Cache，未命中, 嘗試訪問(wèn)主存，重復(fù)步驟2。

  測(cè)試數(shù)組和Cpu緩存行

  因Cpu緩存最小單位是緩存行(64字節(jié))，我么來(lái)測(cè)試一下二維數(shù)組的橫向遍歷和縱向遍歷的具體時(shí)間和性能。

  代碼

  package com.com.array;
  
  /**
   * @Auther: lantao
   * @Date: 2019-06-24 15:52
   * @Company: 隨行付支付有限公司
   * @maill: lan_tao@suixingpay.com
   * @Description: TODO
   */
  public class ArrayTest {
  
      static long[][] arr;
  
      public static void main(String[] args) {
          long sum = 0L;
          arr = new long[1024 * 1024][10];
          // 橫向遍歷
          long l = System.currentTimeMillis();
          for (int i = 0; i < 1024 * 1024; i++) {
              for (int j = 0; j < 10; j++) {
                  sum += arr[i][j];
              }
          }
          System.out.println("Loop Time 橫向遍歷：" + (System.currentTimeMillis() - l) + "ms");
  
          long l1 = System.currentTimeMillis();
          // 縱向遍歷
          for (int i = 0; i < 10; i++) {
              for (int j = 0; j < 1024 * 1024; j++) {
                  sum += arr[j][i];
              }
          }
          System.out.println("Loop Time 縱向遍歷：" + (System.currentTimeMillis() - l) + "ms");
      }
  }

• 結(jié)果：
  Loop Time 橫向遍歷：14ms
  Loop Time 縱向遍歷：83ms

• 總結(jié)：因橫向遍歷遍歷的是行，然后在循環(huán)行的每一列，Cpu緩存會(huì)緩存64字節(jié)大小的緩存行，所以可以減少cpu和主存之間的交互，直接和高速緩存交互，提升性能，縱向遍歷因每次循環(huán)都是不同的行，所以使緩存行沒(méi)有作用。

到此，關(guān)于“Array數(shù)組的概念和用法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！

分享題目：Array數(shù)組的概念和用法
新聞來(lái)源：http://muchs.cn/article14/gdepge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、移動(dòng)網(wǎng)站建設(shè)、、微信公眾號(hào)、網(wǎng)站建設(shè)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)