標籤: 小三通快遞

據悉，寶馬高層最新證實，i品牌的第三款車型i5將會是一台電動車，而非之前所傳聞的燃料電池車或者是插電式混合動力車。不過他也表示，i5除了純電動版本，也會像i3那樣擁有一款增程車型。

寶馬全新i5假想圖

至於i5的車身形式目前仍然是一個迷，但從各方消息以及寶馬高層的暗示來看，這是一台家庭定位的車型，所以它選擇SUV造型的可能性應該是最大的。

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

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

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

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

※小三通海運與一般國際貿易有何不同?

※小三通快遞通關作業有哪些?

why 樹形結構

• 順序存儲

順序存儲的特點是各個存儲單位在邏輯和物理內存上都是相鄰的,典型的就是代表就是數組,物理地址相鄰因此我們可以通過下標很快的檢索出一個元素

我們想往數組中添加一個元素最快的方式就是往它的尾部添加.如果往頭部添加元素的話,效率就很低,因為需要將從第一個元素開始依次往後移動一位,這樣就能空出第一位的元素,然後才能我們指定的數據插入到第一個的位置上

• 鏈式存儲

鏈式存儲的特點是,各個節點之間邏輯是相鄰的,但是物理存儲上不相鄰,每一個節點都存放一個指針或者是引用用來指向它的前驅或者後繼節點, 因此我們想插入或者刪除一個元素時速度就會很塊,只需要變動一下指針的指向就行

但是對鏈表來說查找是很慢的, 因此對任意一個節點來書,他只知道自己的下一個節點或者是上一個節點在哪裡,再多的他就不不知道了,因此需要從頭結點開始遍歷…

• 樹

樹型存儲結構有很多種,比如什麼二叉樹,滿二叉樹,紅黑樹,B樹等, 對於樹形結構來說,它會相對中和鏈式存儲結構和順序存儲結構的優缺點 (其中二叉排序樹最能直接的體會出樹中和鏈式存儲和線性存儲的特性,可以通過右邊的導航先去看看二叉排序樹)

樹的概述

如上圖是一個二叉樹, 當然樹還能有三叉,四叉等等…

• 根節點: 最頂上的節點 即A
  層: 根節點在第一層 BE在第二層
  高度: 最大的層數
  森林: 多個樹的組合
  權: 節點上的值 如根節點的權是 A
  恭弘=叶 恭弘子節點: 下層上的節點是上一層的恭弘=叶 恭弘子節點
  雙親節點: 上層的節點是下層的節點的雙親節點(單個節點又是爸又是媽)
  路徑: 找到C的路徑是 A-B-C
  度: 就是直接子節點的個數

普通二叉樹

• 什麼是二叉樹?

顧名思義就是度最大為2的樹就是二叉樹.而且對二叉樹來說,是嚴格區分左子樹和右子樹的,看上圖,雖然兩個樹的根節點都是1,但是他們的左右子樹不同,因此他們並不是相同的樹

• 什麼是滿二叉樹?

像上圖這樣,所有的恭弘=叶 恭弘子節點都在最後一層,所有的且除了最後一層其他層的節點都有兩個子節點

二叉樹的全部節點計算公式是 2^n-1 , n是層數

• 什麼是完全二叉樹?

像上圖這樣, 所有的恭弘=叶 恭弘子點都在最後一層或者是倒數第二層, 並且從左往右數是連續的

java&二叉樹

• 封裝二叉樹節點

public class TreeNode {
    // 權
    private int value;
    // 左節點
    private TreeNode leftNode;
    // 右節點
    private TreeNode rightNode;
}

• 封裝二叉樹

public class BinaryTree {
    TreeNode root;

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public TreeNode getRoot() {
        return this.getRoot();
    }
}

遍歷

像這樣一顆二叉樹,通過不同的書序遍歷會得到不同的結果

前中后的順序說的是root節點的順序,前序的話就是先遍歷父節點, 中序就是左父右 後續就是左右父

• 前序遍歷

 public void frontShow() {
        System.out.println(this.value);
        if (leftNode != null)
            leftNode.frontShow();

        if (rightNode != null)
            rightNode.frontShow();
    }

• 中序遍歷

    public void middleShow() {
        if (leftNode != null)
            leftNode.middleShow();

        System.out.println(value);

        if (rightNode != null)
            rightNode.middleShow();
    }

• 後續遍歷

    public void backShow() {
        if (leftNode != null)
            leftNode.backShow();

        if (rightNode != null)
            rightNode.backShow();

        System.out.println(value);
    }

查找

其實有了上面三種遍歷的方式, 查找自然存在三種, 一遍遍歷一遍查找

    public TreeNode frontSeach(int num) {
        TreeNode node = null;
        // 當前節點不為空,返回當前節點
        if (num == this.value) {
            return this;
        } else {
            // 查找左節點
            if (leftNode != null) {
                node = leftNode.frontSeach(num);
            }
            if (node != null)
                return node;
            // 查找右節點
            if (rightNode != null)
                node = rightNode.frontSeach(num);
        }
        return node;
    }

刪除節點

刪除節點也是, 不考慮特別複雜的情況, 刪除節點就有兩種情況, 第一種要刪除的節點就是根節點, 那麼讓根節點=null就ok, 第二種情況要刪除的節點不是根節點,就處理它的左右節點, 左右節點還不是需要刪除的元素的話那麼就得遞歸循環這個過程

   // 先判斷是否是根節點,在調用如下方法
    
   public void deleteNode(int i) {
        TreeNode parent = this;
        // 處理左樹
        if (parent.leftNode!=null&&parent.leftNode.value==i){
            parent.leftNode=null;
            return;
        }
        // 處理左樹
        if (parent.rightNode!=null&&parent.rightNode.value==i){
            parent.rightNode=null;
            return;
        }
        // 遞歸-重置父節點
        parent=leftNode;
        if (parent!=null)
            parent.deleteNode(i);
        // 遞歸-重置父節點
        parent=rightNode;
        if (parent!=null)
            parent.deleteNode(i);

    }

順序存儲二叉樹

文章一開始剛說了, 順序存儲的數據結構的典型代表就是數組, 就像這樣

[1,2,3,4,5,6,7]

什麼是順序存儲的二叉樹呢? 其實就是將上面的數組看成了一顆樹,就像下圖這樣

數組轉換成二叉樹是有規律的, 這個規律就體現在他們的 下標的關聯上, 比如我們想找2節點的左子節點的下標就是 2*n -1 = 3 , 於是我們從數組中下標為3的位置取出4來

• 第n個元素的左子節點是 2n-1
• 第n個元素的右子節點是 2n-2

• 第n個元素的父節點是 (n-1)/2

• 遍歷順序存儲的二叉樹

    public void frontShow(int start){
        if (data==null||data.length==0){
            return;
        }
        // 遍歷當前節點
        System.out.println(data[start]);
        // 遍歷左樹
        if (2*start+1<data.length)
            frontShow(2*start+1);
        // 遍歷右樹
        if (2*start+2<data.length)
            frontShow(2*start+2);
    }

線索二叉樹

假設我們有下面的二叉樹, 然後我們可以使用中序遍歷它, 中序遍歷的結果是 4,2,5,1,3,6 但是很快我們就發現了兩個問題, 啥問題呢?

• 問題1: 雖然可以正確的遍歷出 4,2,5,1,3,6 , 但是當我們遍歷到2時, 我們是不知道2的前一個是誰的,(哪怕我們剛才遍歷到了它的前一個節點就是4)

• 問題2: node4,5,6,3的左右節點的引用存在空閑的情況

針對這個現狀做出了改進就是線索化二叉樹, 它可以充分利用各個節點中剩餘的node這個現狀…線索化后如下圖

• 如果這個節點的右節點為空,我們就讓它讓它指向自己的後繼節點, 例如上圖的紅線
• 如何節點的左節點為空, 就讓這個空閑的節點指向它的前驅節點,例如上圖的藍色線

這樣的話, 就實現了任意獲取出一個節點我們都能直接的得知它的前驅節點后後繼節點到底是誰

java&中序化二叉樹;

思路: 按照原來中序遍歷樹的思路,對樹進行中序遍歷,一路遞歸到4這個節點, 檢查到它的左節點為空,就將他的左節點指向它的前驅節點, 可是4本來就是最前的節點,故4這個節點的左節點自然指向了null

然後看它的右節點也為空,於是將他的右節點指向它的後繼節點, 可是這時依然沒獲取到2節點的引用怎麼辦呢? 於是先找個變量將4節點臨時存起來, 再往後遞歸,等遞歸到2節點時,取出臨時變量的4節點, 4節點.setRightNode(2節點)

然後重複這個過程

    // 臨時保存上一個節點
    private TreeNode preNode;

    // 中序線索化二叉樹
    void threadNode(TreeNode node) {
        if (node == null)
            return;

        // 處理左邊
        threadNode(node.getLeftNode());

        // 左節點為空,說明沒有左子節點, 讓這個空出的左節點指向它的上一個節點
        if (node.getLeftNode() == null) {
            // 指向上一個節點
            node.setLeftNode(preNode);
            // 標識節點的類型
            node.setLeftType(1);
        }

        // 處理前驅節點的右指針
        // 比如現在遍歷到了1, 1的上一個節點是5, 5的右邊空着了, 於是讓5的有節點指向1
        if (preNode != null && preNode.getRightNode() == null) {
            preNode.setRightNode(node);
            preNode.setRightType(1);
        }

        // 每次遞歸調用一次這個方法就更新前驅節點
        preNode = node;
        // 處理右邊
        threadNode(node.getRightNode());
    }

遍歷二叉樹

    public void threadIterator() {
        TreeNode node = root;
        while (node != null) {
            // 循環找
            while (node.getLeftType() == 0)
                node = node.getLeftNode();
            // 打印當前節點
            System.out.println(node.getValue());
            // 如果當前的節點的右type=1說明它有指針指向自己的前一個節點
            // 比如現在位置是4, 通過下面的代碼可以讓node=2
            while (node.getRightType() == 1) {
                node = node.getRightNode();
                System.out.println(node.getValue());
            }

            // 替換遍歷的節點, 可以讓 node從2指向 5, 或者從3指向1
            node = node.getRightNode();
        }

    }

赫夫曼樹(最優二叉樹)

定義: 什麼是赫夫曼樹

赫夫曼樹又稱為最優二叉樹

定義: 在N個帶權的恭弘=叶 恭弘子節點的所組成的所有二叉樹中,如果你能找出那個帶權路徑最小的二叉樹,他就是赫夫曼樹

一說起來赫夫曼樹,其實我們可以只關心它的恭弘=叶 恭弘子節點, 權, 路徑這三個要素

• 什麼是恭弘=叶 恭弘子節點的帶權路徑?

所謂權,其實就是節點的值, 比如上圖中node4的權是8 , node5的權是6 ,node3的權是1, 而且我們只關心恭弘=叶 恭弘子節點的權

啥是帶權路徑呢? 比如上圖中 node4的帶權路徑是 1-2-4

• 樹的帶權路徑長度(weight path length) 簡稱 WPL

其實就是這個樹所有的恭弘=叶 恭弘子節點的帶權路徑長度之和,

計算左樹的WPL =2*8+2*6+1*1 = 29

計算左樹的WPL =2*1+2*6+1*8 = 22

總結: 權值越大的節點,離根節點越近的節點是最優二叉樹

### 實戰: 將數組轉換為赫夫曼樹

• 思路:

假設我們現在已經有了數組 [3,5,7,8,11,14,23,29], 如何將這個數組轉換成赫夫曼樹呢?

取出這裏最小的node3 和 倒數第二小的node5 ,構建成新的樹, 新樹的根節點是 node3,5的權值之和, 將構建完成的樹放回到原數組中

重複這個過程, 將最小的node7,node8取出,構建新樹, 同樣新樹的權重就是 node7,8的權重之和, 再將構建完成的樹放回到原數組中

如此往複,最終得到的樹就是huffman樹

• java實現:

封裝TreeNode, 看上面的過程可以看到,需要比較權重的大小,因此重寫它的compareTo方法

public class TreeNode implements Comparable{
    // 權
    private int value;
    private TreeNode leftNode;
    private TreeNode rightNode;

    @Override
    public int compareTo(Object o) {
        TreeNode node = (TreeNode) o;
        return this.value-node.value;
    }

構建赫夫曼樹, 思路就是上圖的過程, 將數組中的各個元素轉換成Node. 然後存放在List容器中,每輪構建新樹時需要排序, 當集合中僅剩下一個節點,也就是根節點時完成樹的構建

    // 創建赫夫曼樹
    private static TreeNode buildHuffmanTree(int[] arr) {
        // 創建一個集合,存放將arr轉換成的二叉樹
        ArrayList<TreeNode> list = new ArrayList<>();
        for (int i : arr) {
            list.add(new TreeNode(i));
        }
        // 開始循環, 當集合中只剩下一棵樹時
        while (list.size() > 1) {
            // 排序
            Collections.sort(list);
            // 取出權值最小的數
            TreeNode leftNode = list.get(list.size() - 1);
            // 取出權值次要小的數
            TreeNode rightNode = list.get(list.size() - 2);
            // 移除取出的兩棵樹
            list.remove(leftNode);
            list.remove(rightNode);

            // 創建新的樹根節點
            TreeNode parentNode = new TreeNode(leftNode.getValue() + rightNode.getValue(), leftNode, rightNode);
            // 將新樹放到原樹的集合中
            list.add(parentNode);
        }
        return list.get(0);
    }

實戰: 赫夫曼樹與數據壓縮

通過上面的介紹我們能直觀的看出來,赫夫曼樹很顯眼的特徵就是它是各個節點能組成的樹中,那顆WPL,帶權路徑長度最短的樹, 利用這條性質常用在數據壓縮領域, 即我們將現有的數據構建成一個赫夫曼樹, 其中出現次數越多的字符,就越靠近根節點, 經過這樣的處理, 就能用最短的方式表示出原有字符

假設我們有這條消息can you can a can as a canner can a can.

數據對計算機來說不過是0-1這樣的数字, 我們看看將上面的字符轉換成01這樣的二進制數它長什麼樣子

1. 將原字符串的每一個char強轉換成 byte == ASCII
99 97 110 32 121 111 117 32 99 97 110 32 97 32 99 97 110 32 97 115 32 97 32 99 97 110 110 101 114 32 99 97 110 32 97 32 99 97 110
    
2. 將byte toBinaryString 轉換成01串如下:
1100011110000111011101000001111001110111111101011
0000011000111100001110111010000011000011000001100
0111100001110111010000011000011110011100000110000
1100000110001111000011101110100000110001111000011
1011101101110110010111100101000001100011110000111
011101000001100001100000110001111000011101110101110

也就是說,如果我們不對其進行壓縮時, 它將會轉換成上面那一大坨在網絡上進行傳輸

使用赫夫曼進行編碼:

思路: 我們將can you can a can as a canner can a can. 中的每一個符號,包括 點 空格,全部封裝進TreeNode

TreeNode中屬性如下: 包含權重: 也就是字符出現的次數, 包含data: 字符本身

public class TreeNode implements Comparable{
    // 存放權重就是字符出現的次數
    private int weight;
    // 存放英文數值
    private Byte data; //
    private TreeNode leftNode;
    private TreeNode rightNode;

封裝完成后, 按照權重的大小倒序排序,各個節點長成這樣:

a:11  :11   n:8   c:7   o:1  .:1  y:1   e:1  u:1  s:1  r:1  

將赫夫曼樹畫出來長這樣:

特徵,我們讓左側的路徑上的值是0, 右邊是1. 因此通過這個赫夫曼樹其實我們可以得到一張赫夫曼編碼錶,

比如像下面這樣:

n: 00
 : 01
a: 10
c: 111
// 每一個字符的編碼就是從根節點到它的路徑

有了這樣編碼錶, 下一步就是對數據進行編碼, 怎麼編碼呢? 不就是做一下替換嗎? 我們現在開始循環遍歷一開始的字符串, 挨個取出裏面的字符, 比如我們取出第一個字符是c, 拿着c來查詢這個表發現,c的編碼是111,於是我們將c替換成111, 遍歷到第二個字符是a, 拿着a查詢表,發現a的值是10, 於是我們將a替換成10, 重複這個過程, 最終我們得到的01串明顯比原來短很多

怎麼完成解碼呢? 解碼也不複雜, 前提也是我們得獲取到huffman編碼錶, 使用前綴匹配法, 比如我們現在接收到了

1111000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

使用前綴就是先取出1 去查查編碼錶有沒有這個數? 有的話就返回對應的字符, 沒有的話就用11再去匹配

大家可以看看上面的那顆霍夫曼樹, 所有的data都在恭弘=叶 恭弘子節點上,所以使用前綴匹配完全可以,絕對不會出現重複的情況

• 使用java實現這個過程

思路概覽:

1. 將原生的字節數組轉化成一個個的TreeNode
2. 取出所有的TreeNode封裝成赫夫曼樹
3. 通過赫夫曼樹踢去出赫夫曼編碼錶
4. 使用這個編碼錶進行編碼
5. 解碼

  private static byte[] huffmanZip(byte[] bytes) {
        // 先統計每個byte出現的次數,放入集合中
        List<TreeNode> treeNodes = buildNodes(bytes);
        // 創建赫夫曼樹
        TreeNode node = createHuffmanTree(treeNodes);
        // 創建huffman編碼錶
        Map<Byte, String> codes = createHuffmanCodeTable(node);
        // 編碼, 將每一個byte替換成huffman編碼錶中的V
        byte[] encodeBytes = encodeHuffmanByte(bytes, codes);
        
        // 使用huffman編碼進行解碼
        byte[] decodeBytes = decode(encodeBytes);
        return decodeBytes;
    }

將原生的byte數組,封裝成一個個的TreeNode節點,保存在一個容器中,並且記錄下這個節點出現的次數, 因此我們需要將出現次數多的節點靠近根節點

    /**
     * 將byte轉換成node集合
     *
     * @param bytes
     * @return
     */
    private static List<TreeNode> buildNodes(byte[] bytes) {
        ArrayList<TreeNode> list = new ArrayList<>();
        HashMap<Byte, Integer> countMap = new HashMap<>();
        // 統計每一個節點的出現的次數
        for (byte aByte : bytes) {
            Integer integer = countMap.get(aByte);
            if (integer == null) {
                countMap.put(aByte, 1);
            } else {
                countMap.put(aByte, integer + 1);
            }
        }
        // 將k-v轉化成node
        countMap.forEach((k, v) -> {
            list.add(new TreeNode(v, k));
        });
        return list;
    }

構建赫夫曼樹

  /**
     * 創建huffman樹
     *
     * @param treeNodes
     * @return
     */
    private static TreeNode createHuffmanTree(List<TreeNode> treeNodes) {
        // 開始循環, 當集合中只剩下一棵樹時
        while (treeNodes.size() > 1) {
            // 排序
            Collections.sort(treeNodes);
            // 取出權值最小的數
            TreeNode leftNode = treeNodes.get(treeNodes.size() - 1);
            // 取出權值次要小的數
            TreeNode rightNode = treeNodes.get(treeNodes.size() - 2);
            // 移除取出的兩棵樹
            treeNodes.remove(leftNode);
            treeNodes.remove(rightNode);

            // 創建新的樹根節點
            TreeNode parentNode = new TreeNode(leftNode.getWeight() + rightNode.getWeight(), leftNode, rightNode);
            // 將新樹放到原樹的集合中
            treeNodes.add(parentNode);
        }
        return treeNodes.get(0);
    }

從赫夫曼樹中提取出編碼錶, 思路: 下面是完了個遞歸, 我們規定好左樹是0,右邊是1, 通過一個SpringBuilder, 每次迭代都記錄下原來走過的路徑,當判斷到它的data不為空時,說明他就是恭弘=叶 恭弘子節點,立即保存這個節點曾經走過的路徑,保存在哪裡呢? 保存在一個map中, Key就是byte value就是走過的路徑

  static StringBuilder stringBuilder = new StringBuilder();
  static Map<Byte, String> huffCode = new HashMap<>();

    /**
     * 創建huffman便編碼錶
     *
     * @param node
     * @return
     */
    private static Map<Byte, String> createHuffmanCodeTable(TreeNode node) {
        if (node == null)
            return null;
        getCodes(node.getLeftNode(), "0", stringBuilder);
        getCodes(node.getRightNode(), "1", stringBuilder);
        return huffCode;
    }

    /**
     * 根據node, 獲取編碼
     *
     * @param node
     * @param code
     * @param stringBuilder
     */
    private static void getCodes(TreeNode node, String code, StringBuilder stringBuilder) {
        StringBuilder sb = new StringBuilder(stringBuilder);
        sb.append(code);
        // 如果節點的data為空,說明根本不是恭弘=叶 恭弘子節點,接着遞歸
        if (node.getData() == null) {
            getCodes(node.getLeftNode(), "0", sb);
            getCodes(node.getRightNode(), "1", sb);
        } else {
            // 如果是恭弘=叶 恭弘子節點,就記錄它的data和路徑
            huffCode.put(node.getData(), sb.toString());
        }
    }

根據赫夫曼編碼錶進行編碼:

思路:

舉個例子: 比如,原byte數組中的一個需要編碼的字節是a

a的ASCII==97

97正常轉成二進制的01串就是 0110 0001

但是現在我們有了編碼錶,就能根據97從編碼錶中取出編碼: 10

換句話說,上面 0110 0001 和 10 地位相同

若干個需要編碼的數append在一起,於是我們就有了一個比原來短一些的01串, 但是問題來了,到這裏就結束了嗎? 我們是將這些01串轉換成String, 在getBytes()返回出去嗎? 其實不是的,因為我們還需要進行解碼,你想想解碼不得編碼map中往外取值? 取值不得有key? 我們如果在這裏將這個01串的byte數組直接返回出去了,再按照什麼樣的方式將這個byte[]轉換成String串呢? ,因為我們要從這個String串中解析出key

然後這裏我們進行約定, 將現在得到的01串按照每8位為一組轉換成int數, 再將這個int強轉成byte, 解碼的時候我們就知道了.就按照8位一組進行解碼. 解析出來數組再轉換成01串,我們就重新拿到了這個編碼后的01串,它是個String串

每遇到8個0或者1,就將它強轉成Int, 再強轉成type, 經過這樣的轉換可能會出現負數,因此01串的最前面有個符號位,1表示負數

比如說: 如果你打印一下面代碼中的encodeByte,你會發現打印的第一個數是-23, 這個-23被保存在新創建的byte數組的第一個位置上, 後續解碼時,就從這個byte數組中的第一個位置上獲取出這個-23, 將它轉換成01二進制串

怎麼轉換呢? 比如不是-23, 而是-1
真值 1
原碼:1,0001
補碼: 2^(4+1) +1 = 100000 + (-1) = 1,1111
我們獲取到的結果就是1111

 /**
     * 進行編碼
     *
     * @param bytes
     * @param codes
     * @return
     */
    private static byte[] encodeHuffmanByte(byte[] bytes, Map<Byte, String> codes) {
        StringBuilder builder = new StringBuilder();
        for (byte aByte : bytes) {
            builder.append(codes.get(aByte));
        }

        // 將這些byte按照每8位一組進行編碼
        int length = 0;
        if (builder.length() % 8 == 0) {
            length = builder.length() / 8;
        } else {
            length = builder.length() / 8 + 1;
        }
        // 用於存儲壓縮后的byte
        byte[] resultByte = new byte[length];
        // 記錄新byte的位置
        int index = 0;
        // 遍歷新得到的串
        for (int i = 0; i < builder.length(); i += 8) {
            String str = null;
            if (i + 8 > builder.length()) {
                str = builder.substring(i);
            } else {
                str = builder.substring(i, i + 8);
            }
            // 將八位的二進制轉換成byte
            // 這裏出現負數了....  涉及到補碼的問題
            byte encodeByte = (byte) Integer.parseInt(str, 2);
            // 存儲起來
            resultByte[index] = encodeByte;
            index++;
        }
        return resultByte;
    }

解碼: 前面我們知道了,約定是按照8位轉換成的int 再轉換成type[] , 現在按照這個約定,反向轉換出我們一開始的01串

/**
     * 按照指定的赫夫曼編碼錶進行解碼
     *
     * @param encodeBytes
     * @return
     */
    private static byte[] decode(byte[] encodeBytes) {
        List<Byte> list = new ArrayList();
        StringBuilder builder = new StringBuilder();
        for (byte encodeByte : encodeBytes) {
            // 判斷是否是最後一個,如果是最後一次不用用0補全, 因此最後一位本來就不夠8位
            boolean flag = encodeByte == encodeBytes[encodeBytes.length - 1];
            String s = byteToBitStr(!flag, encodeByte);
            builder.append(s);
        }
        // 調換編碼錶的k-v
        Map<String, Byte> map = new HashMap<>();
        huffCode.forEach((k, v) -> {
            map.put(v, k);
        });
        // 處理字符串
        for (int i = 0; i < builder.length(); ) {
            int count = 1;
            boolean flag = true;
            Byte b = null;
            while (flag){
                String key = builder.substring(i,i+count);
                b=map.get(key);
                if (b==null){
                    count++;
                }else {
                    flag=false;
                }
            }
            list.add(b);
            i+=count;
        }

        // 將list轉數組
        byte[] bytes = new byte[list.size()];
        int i=0;
        for (Byte aByte : list) {
            bytes[i]=aByte;
            i++;
        }
        return bytes;
    }

    /**
     * 將byte轉換成二進制的String
     *
     * @param b
     * @return
     */
    public static String byteToBitStr(boolean flag, byte b) {
        /**
         * 目標: 全部保留八位.正數前面就補零, 負數前面補1
         * 為什麼選256呢?  因為我們前面約定好了, 按照8位進行分隔的
         * 256的二進製表示是  1 0000 0000
         * 假設我們現在是 1
         * 計算              1 0000 0000
         *               或  0 0000 0001
         *              ----------------------
         *                   1 0000 0001
         *                   結果截取8位就是 0000 0001
         *
         * 假設我們現在是   -1
         * 轉換成二進制:    1111 1111 1111 1111 1111 1111 1111 1111
         *
         * 計算                            1 0000 0000
         * 或  1111 1111 1111 1111 1111 1111 1111 1111
         *              ----------------------
         *                        1 1111 1111
         *                   結果截取8位就是 1111 1111
         *
         *
         */
        int temp = b;
        if (flag) {
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }

    }

二叉排序樹

二叉排序樹, 又叫二叉搜索樹 , BST (Binary Search Tree)

• 線性存儲和鏈式存儲的優缺點

比如我們有一個數組 [7,3,10,12,5,1,9]

雖然我們可以直接取出下標為幾的元素,但是卻不能直接取出值為幾的元素, 比如,我們如果想取出值為9的元素的話,就得先去遍歷這個數組, 然後挨個看看當前位置的數是不是9 , 就這個例子來說我們得找7次

假設我們手裡的數組已經是一個有序數組了 [1,3,5,7,9,11,12]

我們可以通過二分法快速的查找到想要的元素,但是對它依然是數組,如果想往第一個位置上插入元素還是需要把從第一個位置開始的元素,依次往後挪. 才能空出第一個位置,把新值放進去

假設我們將這一行數轉換成鏈式存儲, 確實添加, 刪除變的異常方便, 但是查找還是慢, 不管是查詢誰, 都得從第一個開始往後遍歷

• 我們的主角: 二叉搜索樹

二叉排序樹有如下的特點:

• 對於二叉排序樹中的任意一個非恭弘=叶 恭弘子節點都要求他的左節點小於自己, 右節點大於自己
• 空樹也是二叉排序樹

將上面的無序的數組轉換成二叉排序樹長成下圖這樣

如果我們按照中序遍歷的話結果是: 1 3 5 7 9 11 12 , 正好是從小到大完成排序

再看他的特徵: 如果我們想查找12 , 很簡單 7-10-12 , 如果我們想插入也很簡單,它有鏈表的特性

java&二叉排序樹

封裝Node和Tree

// tree
public class BinarySortTree {
    Node root;
}

// node
public class Node {
    private int value;
    private Node leftNode;
    private Node rightNode;
}

構建一顆二叉排序樹, 思路是啥呢? 如果沒有根節點的話,直接返回,如果存在根節點, 就調用根節點的方法,將新的node添加到根節點上, 假設我們現在遍歷到的節點是NodeA. 新添加的節點是NodeB, 既然想添加就得比較一下NodeA和NodeB的值的大小, 將如果NodeB的值小於NodeA,就添加在NodeA的右邊, 反之就添加在NodeA的左邊

-----------BinarySortTree.class--------------- 
/**
     * 向二叉排序樹中添加節點
     */
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

-------------Node.class------------
/**
     * 添加節點
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null)
            return;
        //判斷需要添加的節點的值比傳遞進來的節點的值大還是小
        // 添加的節點小於當前節點的值
        if (node.value < this.value) {
            if (this.leftNode == null) {
                this.leftNode = node;
            } else {
                this.leftNode.add(node);
            }
        } else {
            if (this.rightNode == null) {
                this.rightNode = node;
            } else {
                this.rightNode.add(node);
            }
        }
    }

刪除一個節點

刪除一節點如如下幾種情況, 但是無論是哪種情況,我們都的保存當前節點的父節點, 通過他的父節點對應節點=null實現節點的刪除

情況1: 如圖

這是最好處理的情況, 就是說需要刪除的元素就是單個的子節點

情況2: 如圖

這種情況也不麻煩,我們讓當前比如我們想上刪除上圖中的3號節點, 我們首先保存下node3的父節點 node7, 刪除node3時發現node3有一個子節點,於是我們讓 node7 的 leftNode = node3

情況3: 如圖

比如我們想刪除7, 但是7這個節點還有一個子樹 按照中序遍歷這個樹的順序是 1,3,5,7,9,11,13, 想刪除7的話,其實

1. 臨時存儲node9
2. 刪除node9
3. 用臨時存儲的node9替換node7

如果node9還有右節點怎麼辦呢?

1. 臨時保存node9
2. 刪除node9
3. 讓node9的右節點替換node9
4. 讓臨時存儲的node9替換node7

/**
     * 刪除一個節點
     *
     * @param value
     * @return
     */
    public void delete(int value) {
        if (root == null) {
            return;
        } else {
            // 找到這個節點
            Node node = midleSearch(value);
            if (node == null)
                return;
            // 找到他的父節點
            Node parentNode = searchParent(value);

            // todo 當前節點是恭弘=叶 恭弘子節點
            if (node.getLeftNode() == null && node.getRightNode() == null) {
                if (parentNode.getLeftNode().getValue() == value) {
                    parentNode.setLeftNode(null);
                } else {
                    parentNode.setRightNode(null);
                }
                // todo 要刪除的節點存在兩個子節點
            } else if (node.getLeftNode() != null && node.getRightNode() != null) {
                // 假設就是刪除7
                //1. 找到右子樹中最小的節點,保存它的值,然後刪除他
                int minValue = deleteMin(node.getRightNode());
                //2.替換被刪除的節點值
                node.setValue(minValue);

            } else { // todo 要刪除的節點有一個左子節點或者是右子節點
                // 左邊有節點
                if (node.getLeftNode() != null) {
                    // 要刪除的節點是父節點的左節點
                    if (parentNode.getLeftNode().getValue() == value) {
                        parentNode.setLeftNode(node.getLeftNode());
                    } else {// 要刪除的節點是父節點的右節點
                        parentNode.setRightNode(node.getLeftNode());
                    }
                } else { // 右邊有節點
                    // 要刪除的節點是父節點的右節點
                    if (parentNode.getLeftNode().getValue() == value) {
                        parentNode.setLeftNode(node.getRightNode());
                    } else {// 要刪除的節點是父節點的右節點
                        parentNode.setRightNode(node.getRightNode());
                    }
                }
            }
        }
    }

 /**
     * 刪除並保存以當前點為根節點的樹的最小值節點
     * @param node
     * @return
     */
    private int deleteMin(Node node) {
        // 情況1: 值最小的節點沒有右節點
        // 情況2: 值最小的節點存在右節點
        // 但是下面我們使用delete,原來考慮到了
        while(node.getLeftNode()!=null){
            node=node.getLeftNode();
        }
        delete(node.getValue());
        return node.getValue();
    }

    /**
     * 搜索父節點
     *
     * @param value
     * @return
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

缺點

二叉排序樹其實對節點權是有要求的, 比如我們的數組就是[1,2,3,4] 那麼畫成平衡二叉樹的話長下面這樣

它不僅沒有二叉排序樹的優點,而且還不如單鏈表的速度快

AVL樹（平衡二叉樹)

定義: 什麼是平衡二叉樹

平衡二叉樹的出現就是為了 解決上面二叉排序樹[1,2,3,4,5,6]這樣成單條鏈的略勢的情況,它要求,每個樹的左子樹和右子樹的高度之差不超過1, 如果不滿足這種情況了,馬上馬對各個節點進行調整,這樣做保證了二叉排序樹的優勢

如何調整

• 情況1: 對於node1來說, 它的左邊深度0 , 右邊的深度2 , 於是我們將它調整成右邊的樣子

• 情況2: 在1234的情況下, 添加node5,導致node2不平衡, 進行如下的調整

• 情況3: 在12345的基礎上添加node6,導致node4不平衡, 對node4進行調整, 其實就和情況1相同了

• 情況4: 在1234567的情況下,進行添加8. 打破了node5的平衡, 因此進行旋轉

一個通用的旋轉規律

看這個典型的有旋轉的例子

node4的出現,使用node8的平衡被打破, 因此我們需要進行調整, 按照下面的步驟進行調整

下面說的this是根節點node8, 按照下面的步驟在紙上畫一畫就ok

1. 創建新node, 使新node.value = this.value
2. 新節點的rightNode = this.rightNode
3. 新節點的leftNode = this.leftNode.rightNode
4. this.value = this.LeftNode.value
5. this.leftNode = this.leftNode .leftNode
6. this.leftNode = 新創建的node

需要注意的情況:

新添加6使得node8不再平衡,但是如果你按照上面的步驟進行旋轉的話,會得到右邊的結果, 但是右邊的結果中對於node4還是不平衡的,因此需要預處理一下

再進行右旋轉時,提前進行檢驗一下,當前節點的左子樹是否存在右邊比左邊高的情況, 如果右邊比較高的話,就先將這個子樹往左旋轉, 再以node8為根,整體往右旋轉

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※想知道網站建置、網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計及後台網頁設計

※不管是台北網頁設計公司、台中網頁設計公司，全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置，台北網頁設計，各種案例分享

※小三通物流營運型態?

※快速運回,大陸空運推薦?

今天周末，和大家聊聊學習這件事情。

在如今這個社會，我們的時間被各類 APP 撕的粉碎。

刷知乎、刷微博、刷朋友圈；

看論壇、看博客、看公號；

等等形形色色的信息和知識獲取方式一個都不錯過。

貌似學了很多，但是卻感覺沒什麼用。

要解決上面這些問題，首先要分清楚一點，什麼是信息，什麼是知識。

• 那什麼是信息呢？

你一切聽到的、看到的，都是信息，比如微博上的明星出軌、微信中的表情大戰、抖音上的段子視頻。

• 那什麼是知識呢？

就是指那些被驗證過的、正確的、被人們相信的概念、規律、方法論。

概念是什麼很好理解，我們上學的時候做的最多的一件事情就是背概念。

規律是事物背後的運行法則，例如當市場上某一種貨物供應量減少后，就會導致價格的上升。

方法論俗稱【套路】，解決某一類問題的時候，有效的解決方案。

信息有真假，有時效，而知識有積累、有迭代。我們要學習的是知識，而不是信息。

時間複利

再說一個概念，複利。

這個大家都應該知道，比較多的應該是在銀行存錢或者是購買理財產品的時候，比如下圖的銀行複利增長曲線：

或者是下面這個公式：

1.01^365 = 37.8

隨公式還附贈一句雞湯：

如果一個人每天都能進步 1%，一年之後他的能力會提升 38 倍。

這句話雖然聽起來很雞湯，但是卻想不到有什麼問題，對吧？

反過來想一下這句話的前提，一個人都想要每天都能進步 1% ，這可能么？當然排除一些極端情況，對於看到我文章的大多數人來說，這是一件不可能的事情。

每天會形形色色的事情去阻止我們進步這 1% ，比如：

• 今天上班被領導批了，心情不好，不想學習了
• 今天工作太忙了，下班后時間都比較晚了，想要休息了
• 今天和朋友一起出去玩了，玩的很開心
• …

等等，然後我們看到身邊優秀的人的時候：

• 看到他們隨隨便便就考試考出來好成績
• 看到他們隨手寫的文章就是網絡爆文
• 看到他們對於某一項技術非常精通的時候

是不是會有一種無力感，好像他們平時和我們一樣，該吃吃該喝喝該玩玩，但是人家就是很厲害的樣子。

於是，就產生了強烈的焦慮感，要學習，要提高自己，開始看更多的信息，關注更多的學習圈子，焦慮感加重，負向循環開始了。

但是，如果你肯相信時間複利的效應，就不會焦慮。

Why？

你現在看到身邊的人的成績，看到他輕輕鬆松做到的事情，即使你拼盡全力也不可能做到。

從一開始你就錯了，他們已經完成了自己的原始積累，他們已經到達了這件事情的複利拐點 。

什麼是複利拐點？

圖中這個小人站的位置就是複利拐點，

如果一個人到達複利拐點（圖中小人站的地方），那他的收益，會急劇增長，可能比之前所有時間的收益總和還要多。

這裏的收益可以是錢，是能力，是認知。

知識

上面我們介紹了如何區分信息和知識，這裏再分享一個個人理解，有效知識。

判斷一個知識是否有效，就要看這個知識和你之前的已有的知識是否能產生聯繫。

如果可以產生聯繫，那麼你對這個新的知識理解速度會非常的快。

就好比編程語言，小編的本職工作是一名 Java 軟件工程師，但是當小編去學習 Python 的相關基礎知識的時候，速度是非常快的，用旁人的視角看起來就好像小編的學習效率非常的高效。

當然，我們不可能只學習和自己已有知識相關方向的知識，可能會接觸一些完全陌生的領域，那麼這個時候如何還能保持效率較高的學習？

在進入一個新的領域的時候，所有的知識都是一個點一個點的，好像是散落在沙子里的石頭，中間是毫無關聯的，這個時間段的學習是非常痛苦的，小編一般稱為原始積累階段。

很多人在原始積累的階段因為過程過於痛苦，就慢慢的放棄了。

在痛苦的原始積累階段，很多時候看不到盡頭，之前的學習感覺都學過，但是仔細一想，又好像什麼都沒學。

這時，我們可以藉助工具去加強知識之間的關聯和加深自己的記憶——思維導圖。

這個工具小編也經常在用的，比如很多人可能都見過我的公眾號上小編自己整理的 Java 進階相關的思維導圖。

當學習一個新的領域的時候，每當一些基礎的概念能產生聯繫的時候，就可以去畫這麼一張思維導圖，思維導圖能讓我們更清晰直觀的理解不同的事物之間的內在聯繫。

長時間的原始積累太過痛苦怎麼辦？

這個是所有人都會遇到的問題，做一件事情，尤其是學習，當我們無法取得一些成果的時候，對興趣和自信的打擊都會非常的大。

首先在做這件事情之前，你需要為自己找到足夠開始這件事情的理由，也就是要有強大的內驅力。

就好比考研這件事情，如果是身邊的人要考，所以你也要考，那麼我覺得你到底要不要考研這件事情值得再思考一下。

但如果是說你想通過考研，來改變自己的人生軌跡，想要獲得更高的起點，那麼，我覺得這個事兒十有八九你是能堅持下去的。

好比學習 Python ，好像身邊的人都在學，那我也要了解一下，和那種我想要學 Python 來換一份工作，擺脫目前的工作狀態，獲取更高的薪水。

大家可能看着沒什麼感覺，但是想一想，自己的人生中，到底有沒有過堅持某一件事情，並最終獲得了一個還不錯的結果，最後收穫的這份快感，是不是無與倫比的。

當然，除了強大的內驅力以外，小編還可以友情提供一點小技巧。

獲取階段性的正向反饋。

如果一件事情需要耗費較長的時間，那麼再大的內驅力也可能會被時間的流逝給磨平了。

靜靜思考下放棄的原因，沒有獲得成就感。

還是拿考研舉例子，一般考研需要準備大半年到一年左右的時間，很多人都堅持不過半年時間就放棄掉了，為什麼，因為他們看不到成效，看不到曙光。但是高三的高考很多人還是能堅持下來的，為什麼？

因為高三有月考啊，每次月考完，都能準確的知道自己的水平提升了多少，自己一個月的努力是沒有白費的，自己一個月的努力是真真實實的化成了卷子上的分數。

所以，做一件需要長時間奮戰的事情，最好能提前為自己設定一些階段性的成果檢驗方式。

時間管理

時間管理是一個繞不開的話題，這裏小編其實也沒資格談這件事情，因為小編本身的時間管理也做的並不好，小編也是人，加完班也會感覺到累，回到家也會只想着休息，人非聖賢，對吧。

還是分享一些經驗吧。

嘗試將自己一天做的事情和耗費的時間列一個表格出來（小編之前列舉過，時間有些久遠，找不到了，這裏就不放圖了）。

當這個表格列出來以後，不管多麼自律的人，肯定會發現，一天之中，有相當部分的時間是被浪費掉的，比如刷朋友圈，刷抖音，刷微博。

在生活中，肯定會經常性的出現這樣事情。

“再玩5分鐘手機就睡覺！”

結果12點了還在玩手機。

周末早晨起來，“先玩一局遊戲，在做xxx”。

結果就是玩到了下午。

相信我，那些墮落的人，並不是一開始就想墮落的。

他們只是在被生活中形形色色的誘惑給誘惑到了，因為現在的社會，各個 APP 在掏空了心思去搶佔用戶的留存時長，它們費勁心力的去討好用戶，讓用戶用最簡單最不需要付出的方式去獲得這種毫無意義的低成本的快樂。

所以，開始記錄自己的時間，是做時間管理的第一步。

當然，並不是要我們完全的放棄娛樂時間，這不可能，人不是機器，不可能是只要有電，就能工作，人也是需要休息的，記錄時間只是為了讓我們在面臨選擇的時候，做出正確的選擇。

第一次寫這種長篇內容分享，有內容不當的地方請各位同學海涵。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

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

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

※小三通海運與一般國際貿易有何不同?

※小三通快遞通關作業有哪些?

Redis 提供了兩種持久化方式，一種是基於快照形式的 RDB，另一種是基於日誌形式的 AOF，每種方式都有自己的優缺點，本文將介紹 Redis 這兩種持久化方式，希望閱讀本文後你對 Redis 的這兩種方式有更加全面、清晰的認識。

RDB 快照方式持久化

先從 RDB 快照方式聊起，RDB 是 Redis 默認開啟的持久化方式，並不需要我們單獨開啟，先來看看跟 RDB 相關的配置信息：

################################ SNAPSHOTTING  ################################
#
# Save the DB on disk:
#
#   save <seconds> <changes>
#
#   Will save the DB if both the given number of seconds and the given
#   number of write operations against the DB occurred.
#
#   In the example below the behaviour will be to save:
#   after 900 sec (15 min) if at least 1 key changed
#   after 300 sec (5 min) if at least 10 keys changed
#   after 60 sec if at least 10000 keys changed
#   save ""
# 自動生成快照的觸發機制 中間的是時間，單位秒，後面的是變更數據 60 秒變更 10000 條數據則自動生成快照
save 900 1
save 300 10
save 60 10000

# 生成快照失敗時，主線程是否停止寫入
stop-writes-on-bgsave-error yes

# 是否採用壓縮算法存儲
rdbcompression yes

# 數據恢復時是否檢測 RDB文件有效性
rdbchecksum yes

# The filename where to dump the DB
# RDB 快照生成的文件名稱
dbfilename dump.rdb

# 快照生成的路徑 AOF 也是存放在這個路徑下面
dir .

關於 RDB 相關配置信息不多，需要我們調整的就更少了，我們只需要根據自己的業務量修改生成快照的機制和文件存放路徑即可。

RDB 有兩種持久化方式：手動觸發 和 自動觸發，手動觸發使用以下兩個命令：

• save：會阻塞當前 Redis 服務器響應其他命令，直到 RDB 快照生成完成為止，對於內存 比較大的實例會造成長時間阻塞，所以線上環境不建議使用

• bgsave：Redis 主進程會 fork 一個子進程，RDB 快照生成有子進程來負責，完成之後，子進程自動結束，bgsave 只會在 fork 子進程的時候短暫的阻塞，這個過程是非常短的，所以推薦使用該命令來手動觸發

除了執行命令手動觸發之外，Redis 內部還存在自動觸發 RDB 的持久化機制，在以下幾種情況下 Redis 會自動觸發 RDB 持久化：

• 在配置中配置了 save 相關配置信息，如我們上面配置文件中的 save 60 10000 ，也可以把它歸類為“save m n”格式的配置，表示 m 秒內數據集存在 n 次修改時，會自動觸發 bgsave。

• 在主從情況下，如果從節點執行全量複製操作，主節點自動執行 bgsave 生成 RDB 文件併發送給從節點

• 執行 debug reload 命令重新加載 Redis 時，也會自動觸發 save 操作

• 默認情況下執行 shutdown 命令時，如果沒有開啟 AOF 持久化功能則自動執行 bgsave

上面就是 RDB 持久化的方式，可以看出 save 命令使用的比較少，大多數情況下使用的都是 bgsave 命令，所以這個 bgsave 命令還是有一些東西，那接下來我們就一起看看 bgsave 背後的原理，先從流程圖開始入手：

bgsave 命令大概有以下幾個步驟：

• 1、執行 bgsave 命令，Redis 主進程判斷當前是否存在正在執行的 RDB/AOF 子進程，如果存在， bgsave 命令直接返回不在往下執行。
• 2、父進程執行 fork 操作創建子進程，fork 操作過程中父進程會阻塞，fork 完成後父進程將不在阻塞可以接受其他命令。
• 3、子進程創建新的 RDB 文件，基於父進程當前內存數據生成臨時快照文件，完成後用新的 RDB 文件替換原有的 RDB 文件，並且給父進程發送 RDB 快照生成完畢通知

上面就是 bgsave 命令背後的一些內容，RDB 的內容就差不多了，我們一起來總結 RDB 持久化的優缺點，RDB 方式的優點：

• RDB 快照是某一時刻 Redis 節點內存數據，非常適合做備份，上傳到遠程服務器或者文件系統中，用於容災備份
• 數據恢復時 RDB 要遠遠快於 AOF

有優點同樣存在缺點，RDB 的缺點有：

• RDB 持久化方式數據沒辦法做到實時持久化/秒級持久化。我們已經知道了 bgsave 命令每次運行都要執行 fork 操作創建子進程，屬於重量級操作，頻繁執行成本過高。
• RDB 文件使用特定二進制格式保存，Redis 版本演進過程中有多個格式 的 RDB 版本，存在老版本 Redis 服務無法兼容新版 RDB 格式的問題

如果我們對數據要求比較高，每一秒的數據都不能丟，RDB 持久化方式肯定是不能夠滿足要求的，那 Redis 有沒有辦法滿足呢，答案是有的，那就是接下來的 AOF 持久化方式

AOF 持久化方式

Redis 默認並沒有開啟 AOF 持久化方式，需要我們自行開啟，在 redis.conf 配置文件中將 appendonly no 調整為 appendonly yes，這樣就開啟了 AOF 持久化，與 RDB 不同的是 AOF 是以記錄操作命令的形式來持久化數據的，我們可以查看以下 AOF 的持久化文件 appendonly.aof

*2
$6
SELECT
$1
0
*3
$3
set
$6
mykey1
$6
你好
*3
$3
set
$4
key2
$5
hello
*1
$8

大概就是長這樣的，具體的你可以查看你 Redis 服務器上的 appendonly.aof 配置文件，這也意味着我們可以在 appendonly.aof 文件中國修改值，等 Redis 重啟時將會加載修改之後的值。看似一些簡單的操作命令，其實從命令到 appendonly.aof 這個過程中非常有學問的，下面時 AOF 持久化流程圖：

在 AOF 持久化過程中有兩個非常重要的操作：一個是將操作命令追加到 AOF_BUF 緩存區，另一個是 AOF_buf 緩存區數據同步到 AOF 文件，接下來我們詳細聊一聊這兩個操作：

1、為什麼要將命令寫入到 aof_buf 緩存區而不是直接寫入到 aof 文件？

我們知道 Redis 是單線程響應，如果每次寫入 AOF 命令都直接追加到磁盤上的 AOF 文件中，這樣頻繁的 IO 開銷，Redis 的性能就完成取決於你的機器硬件了，為了提升 Redis 的響應效率就添加了一層 aof_buf 緩存層， 利用的是操作系統的 cache 技術，這樣就提升了 Redis 的性能，雖然這樣性能是解決了，但是同時也引入了一個問題，aof_buf 緩存區數據如何同步到 AOF 文件呢？由誰同步呢？這就是我們接下來要聊的一個操作：fsync 操作

2、aof_buf 緩存區數據如何同步到 aof 文件中？

aof_buf 緩存區數據寫入到 aof 文件是有 linux 系統去完成的，由於 Linux 系統調度機制周期比較長，如果系統故障宕機了，意味着一個周期內的數據將全部丟失，這不是我們想要的，所以 Linux 提供了一個 fsync 命令，fsync 是針對單個文件操作（比如這裏的 AOF 文件），做強制硬盤同步，fsync 將阻塞直到寫入硬盤完成后返回，保證了數據持久化，正是由於有這個命令，所以 redis 提供了配置項讓我們自行決定何時進行磁盤同步，redis 在 redis.conf 中提供了appendfsync 配置項，有如下三個選項：

# appendfsync always
appendfsync everysec
# appendfsync no

• always：每次有寫入命令都進行緩存區與磁盤數據同步，這樣保證不會有數據丟失，但是這樣會導致 redis 的吞吐量大大下降，下降到每秒只能支持幾百的 TPS ，這違背了 redis 的設計，所以不推薦使用這種方式
• everysec：這是 redis 默認的同步機制，雖然每秒同步一次數據，看上去時間也很快的，但是它對 redis 的吞吐量沒有任何影響，每秒同步一次的話意味着最壞的情況下我們只會丟失 1 秒的數據， 推薦使用這種同步機制，兼顧性能和數據安全
• no：不做任何處理，緩存區與 aof 文件同步交給系統去調度，操作系統同步調度的周期不固定，最長會有 30 秒的間隔，這樣出故障了就會丟失比較多的數據。

這就是三種磁盤同步策略，但是你有沒有注意到一個問題，AOF 文件都是追加的，隨着服務器的運行 AOF 文件會越來越大，體積過大的 AOF 文件對 redis 服務器甚至是主機都會有影響，而且在 Redis 重啟時加載過大的 AOF 文件需要過多的時間，這些都是不友好的，那 Redis 是如何解決這個問題的呢？Redis 引入了重寫機制來解決 AOF 文件過大的問題。

3、Redis 是如何進行 AOF 文件重寫的？

Redis AOF 文件重寫是把 Redis 進程內的數據轉化為寫命令同步到新 AOF 文件的過程，重寫之後的 AOF 文件會比舊的 AOF 文件占更小的體積，這是由以下幾個原因導致的：

• 進程內已經超時的數據不再寫入文件
• 舊的 AOF 文件含有無效命令，如 del key1、hdel key2、srem keys、set a111、set a222等。重寫使用進程內數據直接生成，這樣新的AOF文件只保 留最終數據的寫入命令
• 多條寫命令可以合併為一個，如：lpush list a、lpush list b、lpush list c可以轉化為：lpush list a b c。為了防止單條命令過大造成客戶端緩衝區溢 出，對於 list、set、hash、zset 等類型操作，以 64 個元素為界拆分為多條。

重寫之後的 AOF 文件體積更小了，不但能夠節約磁盤空間，更重要的是在 Redis 數據恢復時，更小體積的 AOF 文件加載時間更短。AOF 文件重寫跟 RDB 持久化一樣分為手動觸發和自動觸發，手動觸發直接調用 bgrewriteaof 命令就好了，我們後面會詳細聊一聊這個命令，自動觸發就需要我們在 redis.conf 中修改以下幾個配置

auto-aof-rewrite-percentage 100
auto-aof-rewrite-min-size 64mb

• auto-aof-rewrite-percentage：代表當前 AOF文件空間 （aof_current_size）和上一次重寫后 AOF 文件空間（aof_base_size）的比值，默認是 100%，也就是一樣大的時候
• auto-aof-rewrite-min-size：表示運行 AOF 重寫時 AOF 文件最小體積，默認為 64MB，也就是說 AOF 文件最小為 64MB 才有可能觸發重寫

滿足了這兩個條件，Redis 就會自動觸發 AOF 文件重寫，AOF 文件重寫的細節跟 RDB 持久化生成快照有點類似，下面是 AOF 文件重寫流程圖：

AOF 文件重寫也是交給子進程來完成，跟 RDB 生成快照很像，AOF 文件重寫在重寫期間建立了一個 aof_rewrite_buf 緩存區來保存重寫期間主進程響應的命令，等新的 AOF 文件重寫完成后，將這部分文件同步到新的 AOF 文件中，最後用新的 AOF 文件替換掉舊的 AOF 文件。需要注意的是在重寫期間，舊的 AOF 文件依然會進行磁盤同步，這樣做的目的是防止重寫失敗導致數據丟失，

Redis 持久化數據恢復

我們知道 Redis 是基於內存的，所有的數據都存放在內存中，由於機器宕機或者其他因素重啟了就會導致我們的數據全部丟失，這也就是要做持久化的原因，當服務器重啟時，Redis 會從持久化文件中加載數據，這樣我們的數據就恢復到了重啟前的數據，在數據恢復這一塊Redis 是如何實現的？我們先來看看數據恢復的流程圖：

Redis 的數據恢複流程比較簡單，優先恢復的是 AOF 文件，如果 AOF 文件不存在時則嘗試加載 RDB 文件，為什麼 RDB 的恢復速度比 AOF 文件快，但是還是會優先加載 AOF 文件呢？我個人認為是 AOF 文件數據更全面並且 AOF 兼容性比 RDB 強，需要注意的是當存在 RDB/AOF 時，如果數據加載不成功，Redis 服務啟動會失敗。

最後

目前互聯網上很多大佬都有 Redis 系列教程，如有雷同，請多多包涵了。原創不易，碼字不易，還希望大家多多支持。若文中有所錯誤之處，還望提出，謝謝。

歡迎掃碼關注微信公眾號：「平頭哥的技術博文」，和平頭哥一起學習，一起進步。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

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

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

※小三通海運與一般國際貿易有何不同?

※小三通快遞通關作業有哪些?

福特（Ford）執行長 Mark Fields 於 4 月 28 日對外表示，福特正在開發能與特斯拉（Tesla） Model 3 與雪佛蘭（Chevrolet ） Bolt 純電動車匹敵的長程電動車，目標是要達到單次充電續航里程 200 英里，在越來越多車廠投入電動車製造的同時，福特打算「成為其中的佼佼者」，甚至是「坐上傲視群雄的位置」。此話一出，向電動車市場其他車廠宣戰的意味濃厚。

雖然 Fields 並未透露太多細節，但這還是福特高層第一次直接對外證實，公司正在研擬向特斯拉與雪佛蘭挑戰的電動車開發計畫。Fields 未提及確切的上市時間，僅表示該電動車將會取名為「Model E」，計畫將於 2019 年在福特本月初宣布要在墨西哥中部興建的新工廠進行組裝，該工廠預計於 2018 年投產。   有別於特斯拉 Model 3 及雪佛蘭 Bolt 為純電動車款，據研究公司 AutoForecast Solutions 指出，福特的 Model E 打算提供 3 種車型，包括油電混合動力車、插電式混合動力車與純電動車，且福特已經以 Model E 名稱申請商標註冊。   回溯至 2015 年 12 月，當時 Fields 曾對外宣布，福特將斥資 45 億美元推動電動車市場，要在 2020 年前，在產品陣容中，加入 13 款油電混合動力車或電動車型，且屆時福特所出產的車輛中，多達 40% 將會是電力驅動的車輛。   福特先前宣布將在 2017 年推出的電動車 Focus Electric 車型續航里程僅能達到 76 英里，即便將在今年秋季增加到 100 英里，不過，仍遠低於將於今年底推出的雪佛蘭 Bolt，以及預計 2 年內交車的特斯拉 Model 3 單次充電續航里程數。

（首圖來源： CC BY 2.0）

（本文授權轉載自《》─〈〉）

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

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

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

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

※小三通海運與一般國際貿易有何不同?

※小三通快遞通關作業有哪些?

電動車大廠特斯拉（Tesla）Model 3 於 2016 年 3 月預售開始後銷售勢如破竹，首周預購量突破 32.5 萬輛，造成產業界轟動，特斯拉高層戴爾穆德‧歐康納（Diarmuid O’Connell）於阿姆斯特丹參與電動車會議時表示，這波預購熱潮正向產業界發送訊息──電動車有極大市場需求。許多市場人士認為特斯拉已經到了「iPhone 時刻」，因為就預購與首發銷售數字比較，特斯拉 Model 3 在 2 天內預購數就達 23.2 萬輛，已經逼近初代 iPhone 在 2 天內銷售 27 萬支的成績，而在汽車史上則根本沒有可以相提並論的例子。拿「iPhone 時刻」來比擬 Model 3，可看出市場 Model 3 預售成績的驚豔轉變成期待：期望像 iPhone 啟動智慧型手機取代傳統手機的浪潮，就此讓電動車躍居主流，引爆換車巨大商機。

台灣產業界也對此風潮樂觀其成，近年來台灣電子產業鏈過度仰賴蘋果供應鏈，眼看就要隨著蘋果產品市場逐漸飽和而沉淪，如今特斯拉接到大量訂單後需要量產交貨，許多產業界人士認為台灣供應鏈最擅長規模量產、降低成本，可望在電動車零組件有新供應鏈成形。   談起特斯拉、台廠與台灣供應鏈，就不禁讓人聯想起台灣電動機車品牌 Gogoro。Gogoro 總部位於林口，其電動機車零組件除了電池與 Panasonic 合作以外，多數均由台廠供應鏈供應，而眾多歐美媒體將之譽為「二輪特斯拉」，與特斯拉相提並論。不過，相對於特斯拉不僅成為全球熱門話題，也同時成為台灣產業界注目的焦點，Gogoro 近來則似乎有點在國內媒體雷達上消失。  
Gogoro 立足台灣  打響國際知名度   儘管在國內關注熱度大不如首發之前，Gogoro 在國際舞台上倒是持續發聲。2015 年 10 月時，《富比士》（Forbes）評選 2015 年全球物聯網新創企業百強（Top 100 Internet Of Things Startups For 2015），台灣只有 Gogoro 唯一一家公司上榜，且位於前十之列的第 8 名。   2015 年 12 月，各國領袖及重量級企業雲集巴黎氣候峰會（COP21），台灣受限於 COP21 為聯合國活動，未能取得觀察員身分，官方代表無法參加，只能靠民間企業為國發聲，台達電與 Gogoro 受邀氣候峰會解決方案大展，台達電展出綠建築、Gogoro 展示電動機車與換電池站。Gogoro 也受邀參加 50 國、750 位代表與會的永續創新論壇，執行長陸學森成為 60 位登上論壇分享的代表之一。   Gogoro 之所以能有機會參與巴黎峰會，前駐法大使呂慶龍也助了一臂之力，呂慶龍曾經以台灣布袋戲向法國行銷台灣而聞名，卸任前更留下「大家忘掉呂大使也沒關係，只要記得台灣，我就算成功了」的名言。呂慶龍在 2015 年 10 月時參觀 Gogoro 信義區的體驗中心，認為十分適合向歐洲發展，之後積極協助安排，在短短 2 個月內讓 Gogoro 擠進巴黎氣候高峰會。無獨有偶，特斯拉執行長馬斯克在巴黎峰會期間，身為電動車產業領袖，也於 2015 年 12 月 2 日在巴黎第一大學發表演講，探討碳排放、氣候變遷，以及停用化石燃料等議題。

 
（Source：Gogoro）   2016 年 1 月的國際消費性電子大展（CES）上，Gogoro 也再度受邀於 Panasonic 展區設攤，因而成為唯一設展於 CES 主展館的台灣企業，Gogoro 在 Panasonic 展區的「鄰居」，正是也與 Panasonic 電池合作的特斯拉，展出其 Model S 電動車，這個因緣際會，使得 Gogoro 在國際大展場合上再度與特斯拉平起平坐，落實了前一年 CES 上多家歐美科技媒體將之比擬為「二輪特斯拉」的稱譽。  
順應全球綠能潮流  善用台灣供應鏈優勢   相對於特斯拉目前的絕頂風光，Gogoro 若拿來相提並論似乎有點失色，不過其實特斯拉也並非從開始就一帆風順，兩家企業的歷程，有許多有趣的比較之處。   首先，就資金面而言，特斯拉成立於 2003 年，至 2007 年，前 4 輪募資總計募得 1.05 億美元；Gogoro 於 2011 年成立，在 2015 年 11 月 13 日完成第二輪增資募得 1.3 億美元，投資者包括合作夥伴 Panasonic，總募資額達 1.8 億美元。也就是說，Gogoro 募資的速度與金額，其實還勝過特斯拉草創初期。   台灣企業往往資本規模遠小於歐美同業，更不用提新創企業的初期資本額只是其他產業的「百分之一」，但 Gogoro 卻能逆勢而行，取得超過特斯拉初期的資本，除了身為後進者，受惠於產業風向往電動車、電動機車發展的潮流更加明顯之外，也還有其產業鏈上的因素。兩公司之後的歷程證明，善用台灣供應鏈的確有其優勢。   特斯拉研發時程相當長，2008 年 5 月時，媒體甚至戲謔的推出「特斯拉死亡倒數時鐘」，因為特斯拉當時若得不到進一步的資金就要倒閉。其第一款電動車 Roadster 於 2008 年起出貨，至 2009 年 7 月才總算為公司帶來獲利。此後，特斯拉也一直以出貨延遲聞名，Roadster 本身就延遲 9 個月交貨，Model S 延遲超過 6 個月，Model X 更延遲超過 18 個月。   相對的，陸學森最初規劃 Gogoro 研發時程要到 2018 年才推出產品，但由於台廠供應鏈成熟，設計研發速度超前，在 2015 年就正式上市，此後出貨也相對順暢，至 2016 年 3 月 1 日累計銷售突破 6,000 輛，尚未有明顯的交貨延遲現象。相較之下，特斯拉第一款產品 Roadster 當年的總出貨量則不過 2,450 輛。

 
（Source：Gogoro）   從 Gogoro 經驗來看，台灣產業能取得的資金規模與國際相當，所在產業供應鏈的成熟度高，加上特斯拉的供應鏈想像空間，並搭上全球綠能風潮，電動車、電動機車相關產業是台灣有機會發展的產業。  
政策失靈  電動車、電動機車發展陷停滯   然而，目前國內電動車、電動機車產業發展，可說「聊勝於無」，電動機車直到 Gogoro 上市後引起正反兩方熱議，使得競爭者回應，能見度才逐漸提高。如中華車為了回應 Gogoro 的威脅，電動機車車款 EM50 推出電池續航力升級版新車；又因應 Gogoro 進軍家樂福，中華車也積極透過異業結盟加速多元化布局，可說是「有競爭才有進步」。   過去政府輔導電動車產業，被稱為越扶越倒，產業界耳語，抱怨一切政策都以裕隆為優先，但裕隆研發完全失敗後，電動車政策也跟著形同停擺，許多流言直指裕隆是國內發展電動車最大障礙。至今全台電動小客車掛牌數寥寥無幾，經濟部又轉向打算改為輔導電動中大型巴士，訂下 10 年 1 萬輛目標，目前已有許多台廠在全球市場出貨電動巴士，包括中國市場在內，但業者對回流經營台灣市場都表示興趣缺缺，指出政策上綁手綁腳，在國外經營得好好的，何必回國自找麻煩。   台灣車輛密集，若積極發展電動車、電動機車，市場潛力不小，結果產業鏈卻是期待美國的特斯拉來帶動供應鏈成形，可說是相當諷刺。另一方面，因為無法以電動車、電動機車取代汽機車污染源，又制定許多不切實際的政策打壓，尤其是針對機車族，造成許多民怨。  
解決空污問題  應以減少機車排放展開布局   2016 年 1 月 3 日，台北市長柯文哲帶頭對機車宣戰，下達三大狠招，就是要打擊機車沒得商量，包括要強力執行對機車停車格收費、增加自行車道來減少機車道消滅機車行駛空間，另外輔以調降公共運輸費率的「推力與拉力」來吸引機車族放棄機車，政策一出，全台北市機車族嘩然。   柯文哲的政策並非他的創見，事實上，幾十年來，上至中央交通部，一直到各縣市交通局，整個政府的一貫政策就是將機車視為眼中釘，想盡辦法消滅。以台北市而言，前任市長郝龍斌任內，以改造機車彎的名義，實質上大量減少機車停車格，也是消滅機車的一環。為何要消滅機車？其主要的因素之一：機車是重要的都市空氣污染排放源，尤其近年來民眾關切 PM2.5 問題，機車的排放更是遭放大檢視。   消滅機車是整個國家的既定政策，柯文哲只不過是「比較白目」把這個政策公開講出來而已。但是，這些制定政策的官員，卻從未站在民眾的角度思考為何生活中非機車不可，只想著用「推力與拉力」強逼民眾繳出更多的停車費、罰款，壓縮路權，讓民眾「騎不下去」，卻不知民眾是有非騎不可的苦衷，政策無法消滅機車，只是在製造人民的痛苦。   不過，機車污染問題也是貨真價實，以台北市環保局公布的數據，有 58% 的 PM2.5 來自於本地，其中又有 35% 的 PM2.5 來自於汽機車廢氣。在全台灣約 2,000 萬輛汽機車之中，機車佔了約 1,400 萬輛，其中高污染的二行程機車雖然逐年淘汰中，但即使是四行程機車，排放廢氣中 PM2.5 所佔比率也高達 86.5%，廢氣集中在道路上，使得機車騎士本身暴露於 PM2.5 的程度遠高於平均值，以台北市而言，PM2.5 平均值 19.6 μg/m3，但是台北都會區機車族暴露的 PM2.5 平均濃度高達 161.6 μg/m3，許多機車族因此會戴上口罩，但是很不幸的，PM2.5 小到連呼吸道中的纖毛都攔不住，口罩當然也沒有辦法過濾，戴上口罩只是純粹「求心安」。

 
（Source：台北市政府環保局。製圖：科技新報）   但民眾有使用機車的實際需求，如台北市巷弄多，公車不可能鑽進每個小巷，柯文哲市長試圖用腳踏車來填補「最後一哩」，卻忘了不是每個人都與他一樣有著能「一日雙塔」的腳力，此外更有載貨需求，用腳踏車要如何滿足？除非整個交通系統有革命性的改變，譬如小型無人車普及並結合分享服務，在那之前，台灣人就是需要機車，不可能予以打壓消滅。   唯一的辦法，不是消滅機車，而是消滅機車產生的污染，若機車能多數改為電動機車，自然沒有排氣中 PM2.5 對健康的威脅，那麼政府就不需千方百計消滅機車。事實上，包括 Gogoro 在內的各電動機車廠與各級政府相關部門討論電動車、電動機車相關規範事宜時，相關官員曾表示，若電動機車真能普及取代燃油機車，「那就不用打壓機車了」。  
跳脫產業侷限  成為智慧能源試金石   Gogoro 與特斯拉最大的相同點，或許在於對自己的定義都不只是車廠。特斯拉已經逐漸顯示其發展核心為 Gigafactory，也就是定位於以鋰電池為主的能源領域，Gogoro 則自始就強調其願景為「更自主更智慧的個人能源使用方式」。   由於 Gogoro 採用換電站方式運行，現已有 177 座 GoStation 電池交換站，未來更將加速拓展新城市擴充布站據點，期望達成一公里一站的目標。若日後換電站能遍布各處，城市電網與換電站之間又能彼此聯繫智慧調控，將可在供電緊繃時減緩換電站中充飽電池的速度，在電力有餘裕的時候加速充電，以達需求反應調節的效果，更進一步，則可能利用換電站中的電池做為分散式能源儲存資源使用。

 
▲ 目前所有 GoStation 電池交換站（含興建中）的服務範圍（點選查看互動地圖）。   台灣未來積極發展綠能、智慧電網，若已有多家同樣以換電站方式運行的電動車、電動機車民間企業，建立廣布的分散式能源儲存資源，將可望節省可觀的建置時間與預算。發展電動車、電動機車產業，不僅可為供應鏈找出路，減少 PM2.5 污染問題，也能對未來先進智慧能源系統發展有所助益。   然而，台灣的發展狀態可說相當尷尬，目前國內電動機車的銷售主要由 Gogoro 帶動，3 月時 Gogoro 宣布在重點城市市佔率高達 92%，但是即使是 Gogoro，與傳統機車銷售量相比較，也還是小巫見大巫，尚未發揮取代傳統機車的作用。   而政府在各政策之間向來缺乏完整的整體思惟與彼此配套，在針對機車與污染相關政策的時候也一樣，2015 年 12 月，立院通過行政院函請審議的貨物稅條例第 12 條之 5 條文修正草案，其重點是希望以減稅優惠補貼，來促進民眾汰換 6 年以上老舊汽車或 4 年以上老舊機車，只要民眾報廢或出口符合條件的中古汽機車，可在購買新車時享貨物稅減稅優惠，汽車減 5 萬元、機車減 4 千元。   這個方案是因為行政院想以消費刺激經濟，又認為老舊汽機車排氣的空污較嚴重，因此鼓勵舊換新，單獨來看立意尚佳，但考慮到政府也正在希望推動電動車、電動機車，以更徹底的減少交通空污，政府一邊計劃發展電動車、補貼電動機車，卻又一邊補貼汽油車與機車，兩個策略的方向彼此抵消，施政可說毫無整體性可言。   過去政府對於電動車、電動機車的政策只能以「七零八落」形容，對機車則是一味打壓，訴諸「推力與拉力」，很少思考如何給機車族民眾一條替代出路；而新政府即將往綠能、智慧電網的世界潮流發展，產業界則殷殷尋求下一個供應鏈商機，這數個重大需求結合起來，若能形成跨部會政策一同推動，整合法規、政策補貼與稅制彼此配合，同時解決多個需求，將可事半功倍。反之，若還是像過去，政府各單位本位主義各自為政，你打壓你的機車，我把電動車「扶倒」，那麼將同樣一事無成。   特斯拉風風光光，台灣產業界固然羨慕，但我們不應只是對著可能的供應鏈商機流口水，而是該趁此機會，全盤檢討國家政策：當電動車來到「iPhone 時刻」，該如何跟上這股商機，並以此對國家全面性的發展有所助益？新政府與其區分「五大創新產業」，其實跨部會、跨領域、跨產業、跨議題的通盤思考，或許對高效率的施政更有幫助。  
參考資料：

（首圖來源：  CC BY 2.0）

（本文授權轉載自《》─〈〉）

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

【其他文章推薦】

※台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包”嚨底家”

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

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

※小三通海運與一般國際貿易有何不同?

※小三通快遞通關作業有哪些?