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

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

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

數(shù)組概念

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

• 線(xiàn)性表

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

• 非線(xiàn)性表

  非線(xiàn)性表就是數(shù)據(jù)不規(guī)則，與線(xiàn)性表是相對(duì)立的，比如二叉樹(shù)丶堆丶等，在非線(xiàn)性表中，數(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ù)類(lèi)型大小(字節(jié))，例如int是4個(gè)字節(jié)。

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

數(shù)組 (Array) 在增刪查這三個(gè)動(dòng)作中，查詢(xún)是高效的，但是增和刪是低效的，查詢(xún)高效是因?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)行插入的話(huà)其復(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)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！