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

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

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

數(shù)組概念

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

• 線性表

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

• 非線性表

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

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

• 公式

  address[i] = base_address + i * data_type_size

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

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

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

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

數(shù)組(Array) 在增刪查這三個動作中，查詢是高效的，但是增和刪是低效的，查詢高效是因為數(shù)組支持隨機(jī)訪問，時間復(fù)雜度是 O(1),這里就不多贅述了，但是在增加和刪除的動作中，因為會涉及數(shù)據(jù)搬移，所以時間復(fù)雜度是 O(n)，下面來詳細(xì)講解。

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

  	int[] info = new int[6];

  插入

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

  

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

  CPU緩存**

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

  1：訪問 data[0]，CPU core 嘗試訪問 CPU Cache，未命中。

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

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

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

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

  因Cpu緩存最小單位是緩存行(64字節(jié))，我么來測試一下二維數(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緩存會緩存64字節(jié)大小的緩存行，所以可以減少cpu和主存之間的交互，直接和高速緩存交互，提升性能，縱向遍歷因每次循環(huán)都是不同的行，所以使緩存行沒有作用。

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

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

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

廣告

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