Silently9527

Silently9527 查看完整檔案

成都編輯華北理工學院  |  軟件工程 編輯成都某在線教育公司  |  JAVA 編輯 silently9527.cn 編輯
編輯

個人動態

Silently9527 發布了文章 · 2月24日

程序員常用的IDEA插件ToolSet版本更新啦

完全開源的淘客項目:https://github.com/silently9527/mall-coupons-server

微信公眾號:貝塔學Java

前言

自己在開發的過程中經常會使用一些在線的工具,比如:時間戳轉日期,JSON格式化等等;前幾天思考了下想把這些常用的功能都做成IDEA插件,在使用的時候就不用去網上尋找工具,在IDEA中就可以快速完成提升開發人員開發效率,所以就熬夜肝了這個插件,歡迎大家都來使用。

Github地址: https://github.com/silently95...

Gitee地址: https://gitee.com/silently952...

覺得好用的小伙伴記得小手一抖 star 喲

版本更新

  • 修復了大家反饋的一些問題
  • 新增了md5加密功能
  • 新增了生成二維碼,下載二維碼,插入logo功能
  • 彈窗位置從右側改到了下邊

已實現功能

  • [x] SQL 轉換成 ElasticSearch 查詢語句
  • [x] 正則表達式
  • [x] Base64編碼/解碼
  • [x] JSON格式化
  • [x] URL編碼/解碼
  • [x] 手機號歸屬地
  • [x] IP地址
  • [x] 日期時間戳互轉
  • [x] MD5
  • [x] 生成二維碼

計劃中的功能

  • [ ] Cron表達式
  • [ ] 圖片base64編碼
  • [ ] UUID生成器
  • [ ] 文件下載
  • [ ] js/css混淆壓縮
  • [ ] 標簽頁支持手動設置

點關注,不迷路

白嫖不好,創作不易,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

查看原文

贊 4 收藏 2 評論 6

Silently9527 發布了文章 · 2月22日

常見的初級排序算法,這次全搞懂

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

程序員常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin

完全開源的淘客項目:https://github.com/silently9527/mall-coupons-server

微信公眾號:貝塔學Java

前言

相信所有的程序員剛開始接觸到的算法都會是排序算法,因為排序在對數據處理和計算有這重要的地位,排序算法往往是其他算法的基礎;本文我們就先從初級排序算法開始學習算法。

排序算法的模板

在開始之前我們先定義一個排序算法通用的模板,在后面的排序算法都會實現這個模板

public interface SortTemplate {

    void sort(Comparable[] array);

    default void print(Comparable[] array) {
        for (Comparable a : array) {
            System.out.print(a + " ");
        }
    }

    default boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    default void exch(Comparable[] array, int i, int j) {
        Comparable tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    
}
  • Comparable: 為了讓我們實現的排序算法更加的通用,可以排序任意的對象,所以我們這里使用了Comparable數組
  • sort: 不同的排序算法實現的方式不一樣,子類自己去實現
  • less: 定義的公用方法,如果a < b就返回true
  • exch: 定義的公用方法,交換數組中的兩個對象
  • print: 打印出數據中的每個元素

選擇排序

算法實現的思路:

  • 首先找到數組中的最小元素,
  • 其實將它和數組中的第一個元素進行交換,這樣就排定了一個元素;
  • 再次找出剩余元素中最小的元素與數組中的第二個元素進行交換,如此反復直到所有元素都是有序的

代碼實現:

public class SelectionSort implements SortTemplate {

    @Override
    public void sort(Comparable[] array) {
        int length = array.length;
        for (int i = 0; i < length; i++) {
            int min = i;
            for (int j = i + 1; j < length; j++) {
                if (less(array[j], array[min])) {
                    min = j;
                }
            }
            exch(array, i, min);
        }
    }

}

假如輸入的數組是有序的,我們會發現選擇排序運行的時候和未排序的時間一樣長!

對于N個元素的數組,使用選擇排序的時間復雜度是O(n2)

選擇排序的是數據移動最少的,交換的次數與數組的大小是線性關系,N個元素的數組需要N次交換

冒泡排序

算法實現的思路:

  • 比較相鄰的兩個元素,如果前一個比后一個大,那么就交換兩個元素的位置
  • 對每一組相鄰的元素執行同樣的操作,直到最后一個元素,操作完成之后就可以排定一個最大的元素
  • 如此往復,直到數組中所有的元素都有序

代碼實現:

public class BubbleSort implements SortTemplate {

    @Override
    public void sort(Comparable[] array) {
        int length = array.length - 1;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i; j++) {
                if (less(array[j + 1], array[j])) {
                    exch(array, j, j + 1);
                }
            }
        }
    }

}

對于N個元素的數組,使用冒泡排序的時間復雜度是O(n2)

插入排序

想象我們在玩撲克牌時,整理撲克牌都是把每一張插入到左邊已經排好序的牌中適當的位置。插入排序的思路類似

算法實現的思路:

  • 初始默認第一個元素就是有序的,當前索引的位置從0開始
  • 先后移動當前索引的位置,當前索引位置左邊的元素是有序的,從后往前開始掃碼與當前索引位置元素進行比較
  • 當確定當前索引位置上的元素在左邊有序適合的位置之后,插入到該位置上
  • 如果當確定當前索引位置上的元素大于了已排序的最后一個元素,那么當前索引位置直接往后移動
  • 如此反復,直到所有元素有序

代碼實現:

public class InsertionSort implements SortTemplate {

    @Override
    public void sort(Comparable[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j > 0 && less(array[j], array[j - 1]); j--) {
                exch(array, j, j - 1);
            }
        }
    }

}

從代碼的實現我們可以看出,當遇到了當前索引的元素大于了左邊有序數組的最后一個元素時,內層循環就直接結束了,所以所我們排序的數組中存在著部分有序,那么插入排序算法會很快。

考慮最糟糕的情況,如果輸入數組是一個倒置的,那么插入排序的效率和選擇排序一樣,時間復雜度是O(n2)

希爾排序

對于大規模的亂序數組插入排序很慢,是因為它只交換相鄰的元素,元素只能一點一點的從數組中移動到正確的位置;插入排序對于部分有序的數組排序是的效率很高;

希爾排序基于這兩個特點對插入排序進行了改進;

算法實現的思路

  • 首先設置一個步長h用來分隔出子數組
  • 用插入排序將h個子數組獨立排序
  • 減小h步長繼續排序子數組,直到h步長為1
  • 當步長為1時就成了普通的插入排序,這樣數組一定是有序的

希爾排序高效的原因,在排序之初,各個子數組都很短,子數組排序之后都是部分有序的,這兩種情況都很適合插入排序。

代碼實現:

public class ShellSort implements SortTemplate {

    @Override
    public void sort(Comparable[] array) {
        int gap = 1;
        int length = array.length;

        while (gap < length / 3) {
            gap = 3 * gap + 1;
        }

        while (gap >= 1) {
            for (int i = gap; i < length; i++) {
                for (int j = i; j >= gap && less(array[j], array[j - gap]); j -= gap) {
                    exch(array, j, j - gap);
                }
            }
            gap = gap / 3;
        }
    }

}

最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,寫作不易,請不要白嫖我喲,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore

圖片來源于網絡
參考書籍:算法第四版

查看原文

贊 0 收藏 0 評論 0

Silently9527 發布了文章 · 2月18日

如何檢測社交網絡中兩個人是否是朋友關系(union-find算法)

前言

春節放假會了老家,停更了很多天,這是年后連夜肝出來的第一篇文章,先來聊聊春節放假期間發生的事,這次回家遇到了我學生時代的女神,當年她在我心目中那是

"出淤泥而不染、濯清漣而不妖"

沒想到這次回家遇到了她,身體發福了,心目中女神的形象瞬間碎了,就好像達芬奇再次遇到了蒙娜麗莎

"菡萏香銷翠葉殘"

好了,言歸正傳。

有時候我們可以需要判斷在大型網絡中兩臺計算機是否相連,是否需要建立一條新的連接才能通信;或者是在社交網絡中判斷兩個人是否是朋友關系(相連表示是朋友關系)。在這種應用中,通常我們可能需要處理數百萬的對象和數億的連接,如何能夠快速的判斷出是否相連呢?這就需要使用到union-find算法

概念

相連

假如輸入一對整數,其中每個數字表示的是某種對象(人、地址或者計算機等等),整數對p,q理解為“p與q相連”,相連具有以下特性:

  • 自反性:p與p是相連的
  • 對稱性:如果p與q相連,那么q與p相連
  • 傳遞性:如果p與q相連,q與r相連,那么p與r也相連
對象如何與數字關聯起來,后面我們聊到一種算法符號表

等價類

假設相連是一個種等價關系,那么等價關系能夠將對象劃分為多個等價類,在該算法中,當且僅當兩個對象相連時他們才屬于同一個等價類

觸點

整個網絡中的某種對象稱為觸點

連通分量

將整數對稱為連接,將等價類稱作連通分量或者簡稱分量

動態連通性

union-find算法的目標是當程序從輸入中讀取了整數對p q時,如果已知的所有整數對都不能說明p q是相連的,那么將這一對整數輸出,否則忽略掉這對整數;我們需要設計數據結構來保存已知的所有整數對的信息,判斷出輸入的整數對是否是相連的,這種問題叫做動態連通性問題。

union-find算法API定義

public interface UF {
    void union(int p, int q); //在p與q之間添加一條連接

    int find(int p); //返回p所在分量的標識符

    boolean connected(int p, int q); //判斷出p與q是否存在于同一個分量中

    int count(); //統計出連通分量的數量
}

如果兩個觸點在不同的分量中,union操作會使兩個分量歸并。一開始我們有N個分量(每個觸點表示一個分量),將兩個分量歸并之后數量減一。

抽象實現如下:

public abstract class AbstractUF implements UF {
    protected int[] id;
    protected int count;

    public AbstractUF(int N) {
        count = N;

        id = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public int count() {
        return count;
    }
}

接下來我們就主要來討論如何實現union方法和find方法

quick-find算法

這種算法的實現思路是在同一個連通分量中所有觸點在id[]中的值都是相同的,判斷是否連通的connected的方法就是判斷id[p]是否等于id[q]。

public class QuickFindImpl extends AbstractUF {
    public QuickFindImpl(int N) {
        super(N);
    }

    @Override
    public int find(int p) {
        return id[p];
    }

    @Override
    public void union(int p, int q) {
        int pId = find(p);
        int qId = find(q);

        if (pId == qId) { //如果相等表示p與q已經屬于同一分量中
            return;
        }

        for (int i = 0; i < id.length; i++) {
            if (id[i] == pId) {
                id[i] = qId; //把分量中所有的值都統一成qId
            }
        }
        count--; //連通分量數減一
    }

}
  • 算法分析:

find()操作顯然是很快的,時間復雜度O(1), 但是union的算法是無法處理大型數據的,因為每次都需要變量整個數組,那么union方法的時間復雜度是O(n)

quick-union算法

為了提高union方法的速度,我們需要考慮另外一種算法;使用同樣的數據結構,只是重新定義id[]表示的意義,每個觸點所對應的id[]值都是在同一分量中的另一個觸點的名稱

在數組初始化之后,每個節點的鏈接都指向自己;id[]數組用父鏈接的形式表示了森林,每一次union操作都會找出每個分量的根節點進行歸并。

public class QuickUnionImpl extends AbstractUF {
    public QuickUnionImpl(int N) {
        super(N);
    }

    @Override
    public int find(int p) {
        //找出p所在分量的根觸點
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p); //找出q p的根觸點
        int qRoot = find(q);
        if (pRoot == qRoot) { //處于同一分量不做處理
            return;
        }
        id[pRoot] = qRoot; //根節點
        count--;
    }

}
  • 算法分析:

看起來quick-union算法比quick-find算法更快,因為union不需要為每對輸入遍歷整個數組,
考慮最佳情況下,find方法只需要訪問一次數組就可以得到根觸點,那么union方法的時間復雜度O(n);
考慮到最糟糕的輸入情況,如下圖:

find方法需要訪問數組n-1次,那么union方法的時間復雜度是O(n2)

加權quick-union算法

為了保證quick-union算法最糟糕的情況不在出現,我需要記錄每一個樹的大小,在進行分量歸并操作時總是把小的樹連接到大的樹上,這種算法構造出來樹的高度會遠遠小于未加權版本所構造的樹高度。

public class WeightedQuickUnionImpl extends AbstractUF {
    private int[] sz;

    public WeightedQuickUnionImpl(int N) {
        super(N);
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            sz[i] = 1;
        }
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p); //找出q p的根觸點
        int qRoot = find(q);
        if (pRoot == qRoot) { //處于同一分量不做處理
            return;
        }
        //小樹合并到大樹
        if (sz[pRoot] < sz[qRoot]) {
            sz[qRoot] += sz[pRoot]; 
            id[pRoot] = qRoot;
        } else {
            sz[pRoot] += sz[qRoot];
            id[qRoot] = pRoot;
        }
        count--;
    }

    @Override
    public int find(int p) {
        //找出p所在分量的根觸點
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }
}
  • 算法分析:

最壞的情況下,每次union歸并的樹都是大小相等的,他們都包含了2的n次方個節點,高度都是n,合并之后的高度變成了n+1,由此可以得出union方法的時間復雜度是O(lgN)

總結

union-find算法只能判斷出給定的兩個整數是否是相連的,無法給出具體達到的路徑;后期我們聊到圖算法可以給出具體的路徑

算法union()find()
quick-find算法N1
quick-union算法樹的高度樹的高度
加權quick-union算法lgNlgN

最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,寫作不易,請不要白嫖我喲,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore

參考書籍:算法第四版

程序員常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin

完全開源的淘客項目:https://github.com/silently9527/mall-coupons-server

微信公眾號:貝塔學Java

查看原文

贊 11 收藏 6 評論 0

Silently9527 發布了文章 · 2月8日

面試的季節到了,老哥確定不來復習下數據結構嗎

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

微信公眾號:貝塔學Java

前言

在上一次《面試篇》Http協議中,面試官原本想的是http問的差不多了,想要繼續問我JAVA相關的一些問題,結果我突然覺得嗓子不舒服咳嗽了幾聲,(在這個敏感的時候)嚇退了面試官,面試官帶起口罩后就說面試先暫時到這里,下次再聊;兩周之后我又收到了HR的電話;

HR:感冒好了嗎?上次面試的結果不錯,你什么時候有時間來我們公司二面呢?

我:隨時準備著

到公司后,我依然被帶到了那個小黑屋,等待著面試官的到來。沒想等來的是一位美女小姐姐。

我:人美聲甜的小姐姐,你是本次的面試官?(我竊喜中)

美女面試官:是的,上次面試你的面試官開會去了,這次面試我來和你聊聊

面試官:看你這么會說話,讓我先來幫你開個胃,說說二分查找吧

我:(果然是開胃啊,這位小姐姐竟然如此善良)

我:二分查找法是在一個有序的數組中查到一個值,如果存在就返回在數組中的索引,否則就返回-1;算法維護了兩個變量lo(最小)和hi(最大),每次查找都與中間值(mid)進行比較,如果等于就返回mid,大于就查詢右半邊的數組,小于就查詢左半邊數組。二分查找法之所以快是因為每次一次查詢都會排除掉一半的值。

No BB, show you the code(不廢話,直接看代碼)
public class BinarySearch {

    /**
     * 二分查找
     * @param key
     * @param arr
     * @return 存在返回對應的下標,不存在返回 -1
     */
    public static int search(int key, int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (key > arr[mid]) {
                lo = mid + 1;
            } else if (key < arr[mid]) {
                hi = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

}

對于一個包含n個元素的列表,用二分查找法最多需要log2n(前面的2是底數)次就可以判斷出元素是否存在;所以二分查找法的時間復雜度是O(log n)

面試官:說說使用數組如何實現棧?

我:小姐姐,棧的特點就是后進先出,使用數組和鏈表都可以實現棧的功能,首先看下棧的定義:

public interface Stack<T> extends Iterable {
    void push(T item); //向棧添加元素
    T pop(); //從棧中彈出
    boolean isEmpty();
    int size(); //返回元素的個數
}



棧在使用的時候有可能也會遍歷全部的元素,所以繼承了Iterable,使用數組實現棧的完整代碼:

public class FixCapacityArrayStack<T> implements Stack<T> {
    private T[] arr;
    private int size;

    public FixCapacityArrayStack(int capacity) {
        this.arr = (T[]) new Object[capacity]; //初始化數組大小
    }

    @Override
    public void push(T item) {
        this.arr[size++] = item;
    }

    @Override
    public T pop() {
        return this.arr[--size];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            int index;

            @Override
            public boolean hasNext() {
                return index < size;
            }

            @Override
            public T next() {
                return arr[index++];
            }
        };
    }
}



面試官:你剛才實現的棧是定容的,那如何實現動態調整棧的大小

我:(已猜到你會問這個問題了,剛才故意沒說動態調整大??;經過多年的面試經驗總結,最和諧的面試過程就是與面試官你推我擋,一上來就說出了最優解,如何體現面試官的優越感?)

我:要實現動態的調整大小,首先需要在提供一個 resize 的方法,把數組擴容到指定的大小并拷貝原來的數據到新的數組中;

private void resize(int newCapacity) {
    Object[] tmp = new Object[newCapacity];
    for (int index = 0; index < size; index++) {
        tmp[index] = arr[index];
    }
    this.arr = (T[]) tmp;
}


需要push方法中檢查當前的size是否已經達到了數組的最大容量,如果是,就把數組擴容2倍

@Override
public void push(T item) {
    if (this.arr.length == size) {
        this.resize(2 * this.arr.length);
    }
    this.arr[size++] = item;
}


pop方法中需要檢查當前占用的空間是否是數組的四分之一,如果是,就需要把數據的容量縮小到原來的一半

@Override
public T pop() {
    T item = this.arr[--size];
    this.arr[size] = null;  //避免游離對象,讓垃圾回收器回收無用對象
    if (size > 0 && size == this.arr.length / 4) {
        this.resize(this.arr.length / 2);
    }
    return item;
}



面試官:剛才你提到了鏈表,那么使用鏈表如何實現棧

我:(這就是你推我擋的結果,和小姐姐的互動很和諧)

我:使用鏈表,首先需要先定義個Node,單向的鏈表包含了值和下一個節點的引用

public class Node<T> {
    private T item;
    private Node next;
}


采用鏈表實現的棧相對于數組實現還較為簡單一些,不需要考慮擴容的問題。

public class LinkedListStack<T> implements Stack<T> {
    private Node<T> first;
    private int size;

    @Override
    public void push(T item) {//先棧頂添加元素
        this.first = new Node<>(item, first);
        size++;
    }

    @Override
    public T pop() { //從棧頂刪除元素
        T item = first.getItem();
        size--;
        first = first.getNext();
        return item;
    }

    @Override
    public boolean isEmpty() {
        return first == null;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node<T> current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T item = current.getItem();
                current = current.getNext();
                return item;
            }
        };
    }
}


面試官:使用鏈表如何實現先進先出隊列

我:與棧的實現過程類似,首先需要定義出隊列

public interface Queue<T> extends Iterable {
    void enqueue(T item); //入隊列

    T dequeue(); //出隊列

    int size();

    boolean isEmpty();
}


使用鏈表實現隊列需要維護兩個變量first、last;first表示的是隊列的頭結點,last表示隊列的尾結點;當入隊列時enqueue向尾部結點添加元素,當出隊列時dequeue從頭結點刪除元素。

public class LinkedListQueue<T> implements Queue<T> {
    private Node<T> first;
    private Node<T> last;
    private int size;

    @Override
    public void enqueue(T item) {
        Node<T> node = new Node<>(item, null);
        if (isEmpty()) {
            first = node; //當隊列為空,first和last指向同一個元素
        } else {
            last.setNext(node);
        }
        last = node;
        size++;
    }

    @Override
    public T dequeue() {
        T item = first.getItem();
        first = first.getNext();
        if (isEmpty()) { //當隊列為空時,需要把last設置為null
            last = null;
        }
        size--;
        return item;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return first == null;  //首節點為空
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private Node<T> current = first;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public T next() {
                T item = current.getItem();
                current = current.getNext();
                return item;
            }
        };
    }
}



面試官:胃開的差不多了,來聊一點算法吧;你來設計一個算法對算術表示式求值,比如:( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )

我:(昨天晚上熬夜看算法沒白辛苦啊,剛好看到了這個解法。)

我:(撓撓頭),這個問題有點麻煩,我需要思考一會。(這樣顯得我是沒有提前準備的,屬于臨場發揮)

我:定義兩個棧,一個用于保存運算符,一個用戶保存操作數;具體的操作過程如下:

  • 忽略左邊括號
  • 遇到數字就壓入操作數棧
  • 遇到符號就壓入符號棧
  • 遇到右括號,彈出一個運算符,彈出所需要的操作數,將計算的結果再次壓入到操作數棧

public static int calculate(String expression) {
    Stack<String> operate = new LinkedListStack<>();
    Stack<Integer> numbers = new LinkedListStack<>();

    String[] split = expression.split(" ");
    for (String str : split) {
        if ("(".equals(str)) {
        } else if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
            operate.push(str);
        } else if (")".equals(str)) {
            String op = operate.pop();
            int resut = 0;
            if ("+".equals(op)) {
                resut = numbers.pop() + numbers.pop();
            } else if ("-".equals(op)) {
                resut = numbers.pop() - numbers.pop();
            } else if ("*".equals(op)) {
                resut = numbers.pop() * numbers.pop();
            } else if ("/".equals(op)) {
                resut = numbers.pop() / numbers.pop();
            }
            numbers.push(resut);
        } else {
            numbers.push(Integer.valueOf(str));
        }
    }
    return numbers.pop();
}


面試官:一個int類型的數組,其中存在三個數字相加等于0,你來設計個算法幫我統計出有多少組這樣的數字

我:這個簡單,請看代碼:

public static int count1(int[] arr) {
    int length = arr.length;
    int count = 0;
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            for (int k = j + 1; k < length; k++) {
                if (arr[i] + arr[j] + arr[k] == 0) {
                    count++;
                }
            }
        }
    }
    return count;
}


面試官:假如這個數組有100萬的int值,你這個算法得運行到什么時候

我:(對的哦,這個算法的時間復雜度是O(n3),在遇到數據量較大時效率極低)

(經過大腦快速思考后)

我:這個算法確實有問題,我大意了,沒有考慮到大量數據的情況;用這個算法會浪費小姐姐的大好青春,所以剛才我思考了下,對這個算法進行改進一下;

首先把3-sum簡化成2-sum。

2-sum中,一個數a[i]要與另一個數相加等于0;有兩種方法:

第一種:與3-sum實現類似使用兩層循環,時間復雜度是O(n2)

第二種:只需要找出數組中是否有-a[i],查找的算法使用二分查找法

public static int count2(int[] arr) {
    Arrays.sort(arr); //首先排序
    int length = arr.length;
    int count = 0;
    for (int i = 0; i < length; i++) {
        if (BinarySearch.search(-arr[i], arr) > i) {
            count++;
        }
    }
    return count;
}


二分查找法的時間復雜度是O(log n), 實現2-sum的算法多了一層循環,所以時間復雜度O(nlog n)

對待3-sum也是用類似的方法,直接上機擼代碼:

public static int count3(int[] arr) {
    Arrays.sort(arr);
    int length = arr.length;
    int count = 0;
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            if (BinarySearch.search(-arr[i]-arr[j], arr) > j) {
                count++;
            }
        }
    }
    return count;
}


我:小姐姐,這個算法改進之后的時間復雜度是O(n2log n),我已經盡力了,只能這么快了。(面試官露出迷人的微笑)

面試官:假如你是微信的開發人員,隨便給你兩個用戶,如何判斷這兩個用戶是否連通的。何為連通?A是B的好友,B是C的好友,那么A與C就是連通的

我:(這小姐姐的問題是越來越難了)

我:美麗的面試官,今天燒腦嚴重,我可以趴下休息一會嗎?(其實是沒想到好的解法,拖延時間戰術)

面試官:可以,那你先休息10分鐘。

面試未完,待續

最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,寫作不易,請不要白嫖我喲,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore

參考書籍:算法第四版

程序員常用的IDEA插件:https://github.com/silently9527/ToolsetIdeaPlugin

完全開源的淘客項目:https://github.com/silently9527/mall-coupons-server

查看原文

贊 2 收藏 2 評論 0

Silently9527 發布了文章 · 2月3日

熬夜肝了個IDEA插件整合程序員常用的工具,總有你能用上的

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

微信公眾號:貝塔學Java

前言

自己在開發的過程中經常會使用一些在線的工具,比如:時間戳轉日期,JSON格式化等等;前幾天思考了下想把這些常用的功能都做成IDEA插件,在使用的時候就不用去網上尋找工具,在IDEA中就可以快速完成提升開發人員開發效率,所以就熬夜肝了這個插件,歡迎大家都來使用。

Github地址: https://github.com/silently95...

Gitee地址: https://gitee.com/silently952...

覺得好用的小伙伴記得小手一抖 star 喲

已實現功能

  • [x] SQL 轉換成 ElasticSearch 查詢語句
  • [x] 正則表達式
  • [x] Base64編碼/解碼
  • [x] JSON格式化
  • [x] URL編碼/解碼
  • [x] 手機號歸屬地
  • [x] IP地址
  • [x] 日期時間戳互轉

計劃中的功能

  • [ ] Cron表達式
  • [ ] MD5
  • [ ] 圖片base64編碼
  • [ ] 文件下載
  • [ ] js/css混淆壓縮

插件安裝步驟

  1. 從release中下載最新版本的代碼
  2. 在IDEA中通過本地安裝插件

功能介紹:

SQL轉換成ElasticSearch查詢語句

手寫ElasticSearch的查詢語句,語法記不住的可以使用下這個工具,常用的都能正常轉換,如果遇到復雜的可能會轉換出錯,需要在再轉換的結果中自行修改

Base64編碼/解碼

JSON格式化

IP地址

手機號歸屬地

URL編碼/解碼

日期時間戳互轉

正則表達式

提供了常用的正則表達式匹配,當然自己也可以自己寫表達式


寫到最后(點關注,不迷路)

白嫖不好,創作不易,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

歡迎關注公眾號:貝塔學JAVA

查看原文

贊 7 收藏 3 評論 5

Silently9527 發布了文章 · 2月2日

精美的淘客項目完全開源啦,確定不來圍觀嗎

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

項目介紹

Mall-Coupons是一個從前端到后端完全開源的淘寶客項目,當初學習完uniapp之后想做一個實戰項目,所以才研發了這個項目。由于本人平時主要從事后端研發,界面樣式非我所長,所以大家覺得界面效果不好的可以自己修改。目前項目已經支持打包成App、微信小程序、QQ小程序、Web站點;理論上其他小程序也支持,可能需要微調

Github地址:

Gitee地址:

效果預覽

功能列表

  • 推薦穿衣搭配
  • 搭配篩選
  • 搭配詳情
  • 相關搭配推薦
  • 用戶點贊
  • 商品分類
  • 分類查詢商品列表
  • 首頁輪播
  • APP、Web支持喚醒淘寶
  • 9.9包郵
  • 瘋搶排行榜
  • 首頁優質商品推薦
  • 商品、優惠券搜索
  • 商品詳情
  • 相似商品推薦
  • 商品收藏、收藏夾
  • 口令購買、領券購買
  • 用戶登錄、微信登錄、QQ登錄、手機驗證碼登錄
  • 用戶新手教程

技術選型

后端技術

技術備注地址
SpringBoot容器+MVC框架https://spring.io/projects/spring-boot
MyBatisORM框架http://www.mybatis.org/mybatis-3/zh/index.html
SpringSecurity認證和授權框架https://spring.io/projects/spring-security
SpringSocialOAuth2認證框架https://github.com/spring-projects/spring-social
Redis分布式緩存https://redis.io/
Druid數據庫連接池https://github.com/alibaba/druid
Lombok簡化對象封裝工具https://github.com/rzwitserloot/lombok
FastjsonJSON工具https://github.com/alibaba/fa...
spring-data-mybatis封裝Mybatis實現JPA部分功能https://github.com/easybest/spring-data-mybatis

前端技術

技術備注地址
Vue前端框架https://vuejs.org/
UniApp一個使用 Vue.js 開發所有前端應用的框架https://uniapp.dcloud.io/
Vuex全局狀態管理框架https://vuex.vuejs.org/
colorui樣式庫https://github.com/weilanwl/ColorUI

開發環境

工具版本號下載
JDK1.8https://www.oracle.com/techne...
Mysql5.7https://www.mysql.com/
Redis5.0https://redis.io/download
Nginx1.10http://nginx.org/en/download....

部署文檔

關注微信公眾號:貝塔學JAVA ;回復文檔獲取部署文檔

有任何部署疑問,歡迎給我留言

我的技術博客

https://silently9527.cn/


寫到最后(點關注,不迷路)

白嫖不好,創作不易,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

查看原文

贊 8 收藏 6 評論 0

Silently9527 發布了文章 · 1月27日

面試官常問的垃圾回收器,這次全搞懂

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

前言

前幾天寫了一篇《JVM性能調優實戰:讓你的IntelliJ Idea縱享絲滑》,其中有對GC垃圾回收器的選擇嘗試,本篇我們就來詳細的看看JVM中常見的垃圾回收器有哪些以及每個垃圾回收器的特點,這也是面試的時候經常被問的內容

JVM堆內存概覽

在聊垃圾回收器之前,我們先來看看JVM堆內存的區域劃分是怎么樣的,看下圖

  • 因為虛擬機使用的垃圾回收算法是分代收集算法,所以堆內存被分為了新生代和老年代
  • 新生代使用的垃圾回收算法是復制算法,所以新生代又被分為了 Eden 和Survivor;空間大小比例默認為8:2
  • Survivor又被分為了S0、S1,這兩個的空間大小比例為1:1

內存分配以及垃圾回收

  1. 對象優先在Eden區進行分配,如果Eden區滿了之后會觸發一次Minor GC
  2. Minor GC之后從Eden存活下來的對象將會被移動到S0區域,當S0內存滿了之后又會被觸發一次Minor GC,S0區存活下來的對象會被移動到S1區,S0區空閑;S1滿了之后在Minor GC,存活下來的再次移動到S0區,S1區空閑,這樣反反復復GC,每GC一次,對象的年齡就漲一歲,默認達到15歲之后就會進入老年代,對于晉身到老年代的年齡閾值可以通過參數 -XX:MaxTenuringThreshold設置
  3. 在Minor GC之后需要的發送晉身到老年代的對象沒有空間安置,那么就會觸發Full GC (這步非絕對,視垃圾回收器決定)
Minor GC和Full GC的區別:Minor GC是指發生在新生代的垃圾收集行為,由于對象優先在Eden區分配,并且很多對象都是朝生夕死,所以觸發的頻率相對較高;由于采用的復制算法,所以一般回收速度非???。Full GC是指發生在老年代的垃圾收集行為,Full GC的速度一般會比Minor GC慢10倍以上;所以不能讓JVM頻繁的發生Full GC

為了能夠更好的適應不同程序的內存情況,JVM也不一定要求必須達到年齡15歲才能晉身到老年代,如果在Survivor區中相同年齡的所有對象大小總和大于Survivor區空間的一半,年齡大于或者等于這個年齡的對象將會直接進入到老年代

Full GC觸發條件

  • 代碼中調用System.gc()
  • 老年代空間不足/滿了
  • 持久區空間不足/滿了
注意:大對象會直接在老年代分配內存,可以通過參數-XX:PretenureSizeThreshold控制對象的大小,通常遇到的大對象是很長的字符串或者數組,如果分配了一大群大對象只是臨時使用,生命很短暫,那么就會頻繁的發生Full GC,但是此時的新生代的空間還有空閑;寫代碼的時候,這種情況應該避免,特別是在創建數組的時候要當心

空間擔保

在新生代發生Minor GC的時候,JVM會先檢查老年代中可分配的連續空間是否大于新生代所有對象的總和,如果大于,那么本次Minor GC就可以安全的執行;如果不大于,那么JVM會先去檢查參數HandlePromotionFailure設置值是否允許空間擔保失敗,如果允許,JVM會繼續檢查老年代可分配的連續空間是否大于歷次晉升到老年代對象的平均大小,如果大于,盡管這次Minor GC是有風險的,JVM也會嘗試一次Minor GC;如果不允許擔保失敗,那么JVM直接進行Full GC

雖然擔保有可能會失敗,導致饒一圈才能進行GC,但是還是建議把這個參數打開,可以避免JVM頻繁的Full GC

垃圾回收器概覽

從上圖可以看出:

  • 新生代可以使用的垃圾回收器:Serial、ParNew、Parallel Scavenge
  • 老年代可以適用的垃圾回收器:CMS、Serial Old、Parallel Old
  • G1回收器適用于新生代和老年代
  • 相互之間有連線的表示可以配合使用
CMS和Serial Old同為老年代回收器,為何相互會有連線呢?

Serial收集器

這是個單線程收集器,發展歷史最悠久的收集器,當它在進行垃圾收集工作的時候,其他線程都必須暫停直到垃圾收集結束(Stop The World)。

雖然Serial收集器存在Stop The World的問題,但是在并行能力較弱的單CPU環境下往往表現優于其他收集器;因為它簡單而高效,沒有多余的線程交互開銷;Serial對于運行在Client模式下的虛擬機來說是個很好的選擇

使用-XX:+UseSerialGC參數可以設置新生代使用這個Serial收集器

ParNew收集器

ParNew收集器是Serial收集器的多線程版本;除了使用了多線程進行垃圾收集以外,其他的都和Serial一致;它默認開始的線程數與CPU的核數相同,可以通過參數-XX:ParallelGCThreads來設置線程數。

從上面的圖可以看出,能夠與CMS配合使用的收集器,除了Serial以外,就只剩下ParNew,所以ParNew通常是運行在Server模式下的首選新生代垃圾收集器

使用-XX:+UseParNewGC參數可以設置新生代使用這個并行回收器

Parallel Scavenge收集器

Parallel Scavenge收集器依然是個采用復制算法的多線程新生代收集器,它與其他的收集器的不同之處在于它主要關心的是吞吐量,而其他的收集器關注的是盡可能的減少用戶線程的等待時間(縮短Stop The World的時間)。吞吐量=用戶線程執行時間/(用戶線程執行時間+垃圾收集時間),虛擬機總共運行100分鐘,其中垃圾收集花費時間1分鐘,那么吞吐量就是 99%

停頓時間越短適合需要和用戶進行交互的程序,良好的響應能夠提升用戶的體驗。而高效的吞吐量可以充分的利用CPU時間,盡快的完成計算任務,所以Parallel Scavenge收集器適用于后臺計算型任務程序。

-XX:MaxGCPauseMillis可以控制垃圾收集的最大暫停時間,需要注意不要以為把這個時間設置的很小就可以減少垃圾收集暫用的時間,這可能會導致發生頻繁的GC,反而降低了吞吐量

-XX:GCTimeRatio設置吞吐量大小,參數是取值范圍0-100的整數,也就是垃圾收集占用的時間,默認是99,那么垃圾收集占用的最大時間 1%

-XX:+UseAdaptiveSizePolicy 如果打開這個參數,就不需要用戶手動的控制新生代大小,晉升老年代年齡等參數,JVM會開啟GC自適應調節策略

Serial Old收集器

Serial Old收集器也是個單線程收集器,適用于老年代,使用的是標記-整理算法,可以配合Serial收集器在Client模式下使用。

它可以作為CMS收集器的后備預案,如果CMS出現Concurrent Mode Failure,則SerialOld將作為后備收集器。(后面CMS詳細說明)

Parallel Old收集器

Parallel Old收集器可以配合Parallel Scavenge收集器一起使用達到“吞吐量優先”,它主要是針對老年代的收集器,使用的是標記-整理算法。在注重吞吐量的任務中可以優先考慮使用這個組合

-XX:+UseParallelOldGc設置老年代使用該回收器。

XX:+ParallelGCThreads設置垃圾收集時的線程數量。

CMS收集器

CMS收集器是一種以獲取最短回收停頓時間為目標的收集器,在互聯網網站、B/S架構的中常用的收集器就是CMS,因為系統停頓的時間最短,給用戶帶來較好的體驗。

-XX:+UseConcMarkSweepGC設置老年代使用該回收器。

-XX:ConcGCThreads設置并發線程數量。

CMS采用的是標記-清除算法,主要分為了4個步驟:

  • 初始化標記
  • 并發標記
  • 重新標記
  • 并發清除

初始化標記和重新標記這兩個步驟依然會發生Stop The World,初始化標記只是標記GC Root能夠直接關聯到的對象,速度較快,并發標記能夠和用戶線程并發執行;重新標記是為了修正在并發標記的過程中用戶線程產生的垃圾,這個時間比初始化標記稍長,比并發標記短很多。整個過程請看下圖

優點

  • CMS是一款優秀的收集器,它的主要優點:并發收集、低停頓,因此CMS收集器也被稱為并發低停頓收集器(Concurrent Low Pause Collector)。

缺點

  • CMS收集器對CPU資源非常敏感。 在并發階段,它雖然不會導致用戶線程停頓,但會因為占用了一部分線程(或者說CPU資源)而導致應用程序變慢,總吞吐量會降低。CMS默認啟動的回收線程數是(CPU數量+3)/4,也就是當CPU在4個以上時,并發回收時垃圾收集線程不少于25%的CPU資源,并且隨著CPU數量的增加而下降。但是當CPU不足4個時(比如2個),CMS對用戶程序的影響就可能變得很大,如果本來CPU負載就比較大,還要分出一半的運算能力去執行收集器線程,就可能導致用戶程序的執行速度忽然降低了50%,其實也讓人無法接受。
  • 無法處理浮動垃圾。 由于CMS并發清理階段用戶線程還在運行著,伴隨程序運行自然就還會有新的垃圾不斷產生。這一部分垃圾出現在標記過程之后,CMS無法再當次收集中處理掉它們,只好留待下一次GC時再清理掉。這一部分垃圾就被稱為“浮動垃圾”。也是由于在垃圾收集階段用戶線程還需要運行,那也就還需要預留有足夠的內存空間給用戶線程使用,因此CMS收集器不能像其他收集器那樣等到老年代幾乎完全被填滿了再進行收集,回收閥值可以通過參數-XX:CMSInitiatingoccupancyFraction來設置;如果回收閥值設置的太大,在CMS運行期間如果分配大的對象找不到足夠的空間就會出現“Concurrent Mode Failure”失敗,這時候會臨時啟動SerialOld GC來重新進行老年代的收集,這樣的話停頓的時間就會加長。
  • 標記-清除算法導致的空間碎片 CMS是一款基于“標記-清除”算法實現的收集器,這意味著收集結束時會有大量空間碎片產生??臻g碎片過多時,將會給大對象分配帶來很大麻煩,往往出現老年代空間剩余,但無法找到足夠大連續空間來分配當前對象。為了解決這個問題CMS提供了一個參數-XX:+UseCMSCompactAtFullCollecion,如果啟用,在Full GC的時候開啟內存碎片整理合并過程,由于內存碎片整理的過程無法并行執行,所以停頓的時間會加長??紤]到每次FullGC都要進行內存碎片合并不是很合適,所以CMS又提供了另一個參數-XX:CMSFullGCsBeforeCompaction來控制執行多少次不帶碎片整理的FullGC之后,來一次帶碎片整理GC

G1收集器

G1是一款面向服務端應用的垃圾回收器。

  • 并行與并發:與CMS類似,充分里用多核CPU的優勢,G1仍然可以不暫停用戶線程執行垃圾收集工作
  • 分代收集:分代的概念依然在G1保留,當時它不需要和其他垃圾收集器配合使用,可以獨立管理整個堆內存
  • 空間的整合:G1整體上采用的是標記-整理算法,從局部(Region)采用的是復制算法,這兩種算法都意味著G1不需要進行內存碎片整理
  • 可預測的停頓:能夠讓用戶指定在時間片段內,消耗在垃圾收集的時間不超過多長時間。

Region

雖然在G1中依然保留了新生代和老年代的概念,但是采用的是一種完全不同的方式來組織堆內存,它把整個堆內存分割成了很多大小相同的區域(Region),并且新生代和老年代在物理上也不是連續的內存區域,請看下圖:

每個Region被標記了E、S、O和H,其中H是以往算法中沒有的,它代表Humongous,這表示這些Region存儲的是巨型對象,當新建對象大小超過Region大小一半時,直接在新的一個或多個連續Region中分配,并標記為H。Region區域的內存大小可以通過-XX:G1HeapRegionSize參數指定,大小區間只能是2的冪次方,如:1M、2M、4M、8M

G1的GC模式

  • 新生代GC:與其他新生代收集器類似,對象優先在eden region分配,如果eden region內存不足就會觸發新生代的GC,把存活的對象安置在survivor region,或者晉升到old region
  • 混合GC:當越來越多的對象晉升到了old region,當老年代的內存使用率達到某個閾值就會觸發混合GC,可以通過參數-XX:InitiatingHeapOccupancyPercent設置閾值百分比,此參數與CMS中-XX:CMSInitiatingoccupancyFraction的功能類似;混合GC會回收新生代和部分老年代內存,注意是部分老年代而不是全部老年代;G1會跟蹤每個Region中的垃圾回收價值,在用戶指定的垃圾收集時間內優先回收價值最大的region
  • Full GC:如果對象內存分配速度過快,混合GC還未回收完成,導致老年代被填滿,就會觸發一次full gc,G1的full gc算法就是單線程執行的serial old gc,此過程與CMS類似,會導致異常長時間的暫停時間,盡可能的避免full gc.
    • -

寫到最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,請朋友們不要白嫖我喲,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

    • -
我已經從零開始手寫了簡易版springmvc,以及編寫了詳細的說明文檔,希望能夠幫助伙伴們深入理解springmvc核心原理,有需要的朋友歡迎關注公眾號:貝塔學JAVA ,回復源碼即可

image

查看原文

贊 6 收藏 5 評論 0

Silently9527 發布了文章 · 1月25日

吐血整理:推薦幾款頂級好用的IDEA插件

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

微信公眾號:貝塔學Java

前言

“工欲善其事必先利其器” 在實際的開發過程中,靈活的使用好開發工具,將讓我們的工作事半功倍。今天給大家推薦幾款好用的IDEA插件,寫代碼也可以“飛起來”

美化插件

Material Theme UI

相親第一眼也得看眼緣,所以今天推薦的第一款是主題插件,可以讓你的idea圖標、配置搭配很到位,也可以切換不用的顏色,默認提供了很多的主題供選擇,每一種都是狂拽酷炫;當前端小姐姐或者測試小姐姐看到了你這么炫酷的界面,她肯定會覺得原來男孩子也會這么精致呀,形象陡然上升~

就問你,這么絢麗多彩的顏色,哪個小姐姐不為你著迷~

Extra Icons

這也是一款美化插件,為一些文件類型提供官方沒有的圖標

Background Image Plus

設置idea背景圖片的插件,不但可以設置固體的圖片,還可以設置一段時間后隨機變化背景圖片,以及設置圖片的透明度等等;接下來我設置一張女神的照片,看著女神照片擼代碼,整天心情美滋滋

實用插件

Translation

像我這樣英文很菜的人來說,這款插件就是神器,在看各種框架源碼的時候十分有用; 選擇右鍵就可以翻譯,對于方法或者類上面的注釋,只要按下F1就自動被翻譯成中文

Maven Helper

依賴包沖突的問題,我相信大家都遇到過,一旦出現了沖突,啟動或運行過程總是會出一些莫名其妙的錯誤,查找沖突過程十分痛苦,但如果你安裝了這個插件,那這些都不是事,分分鐘搞定

Code Glance

Sublime Text右側的預覽區相信很多人都用過吧, 此插件就實現了代碼編輯區迷你縮放功能, 達到代碼全局預覽

MyBatis Log Plugin

Mybaits在運行的時候會把SQL打印出來,但是打印的是帶占位符的SQL,如果遇到SQL復雜的話,那么要手動拼接出這個SQL還是比較麻煩的,好在這個插件幫我們搞定

菜單欄 -> Tools -> MyBatis Log Plugin

Free Mybatis plugin

可以在Mybatis的Mapper接口和xml文件之間很方便的來回切換,像是查看接口實現類一樣簡單,無需到xml中去搜索。

Lombok

神器級別的插件,可以讓實體類更加簡化,不在需要寫getter/setter方法,通過注解就可以實現builder模式以及鏈式調用;在充血模型中可以不需要在和getter/setter方法混在一起

項目還需要添加maven依賴

<dependency>
    <groupId>org.projectlombok</groupId>
    <artifactId>lombok</artifactId>
    <version>1.16.10</version>
</dependency>

Key promoter X

回想剛開始從eclipse切換到idea那段時間實在是很痛苦,就是因為快捷鍵不熟悉,熟悉開發工具的快捷鍵能夠很好的提高我們的開發效率,這款工具的目的就是為了幫助用戶記住快捷鍵,操作窗口之后就會在右下角給出快捷鍵的提示,提醒多了自然你就記住了。

Grep Console

在開發的過程中,idea的控制臺通常會打印出一大推的日志,想要快速找到自己關心的日志比較困難,通過這個插件可以給不同級別的日志設置不同的展示樣式,幫助快速定位日志


寫到最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,白嫖不好,創作不易,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

原創不易 轉載請注明出處:https://silently9527.cn/archives/104

我已經從零開始手寫了簡易版springmvc,以及編寫了詳細的說明文檔,希望能夠和伙伴們深入理解springmvc核心原理,有需要的朋友歡迎關注公眾號:貝塔學JAVA ,回復源碼即可


公眾號:貝塔學JAVA

查看原文

贊 7 收藏 5 評論 0

Silently9527 關注了用戶 · 1月22日

SegmentFault @segmentfault

SegmentFault 社區管理媛 - 思否小姐姐

純粹的技術社區離不開所有開發者的支持和努力 biubiu

更多技術內容與動態歡迎關注 @SegmentFault 官方微博與微信公眾號!

點擊添加思否小姐姐個人微信號!

關注 84103

Silently9527 發布了文章 · 1月19日

JVM性能調優實戰:讓你的IntelliJ Idea縱享絲滑

本文已被Github倉庫收錄 https://github.com/silently9527/JavaCore

微信公眾號:貝塔學Java

前言

在前面整理了一篇關于JVM故障診斷和處理工具,考慮到大部分的Java程序員都使用的時IntelliJ Idea,本篇就使用工具來實戰演練對IntelliJ Idea運行速度調優

調優前的運行狀態

原始配置內容

要查詢idea原始配置文件的路徑可以在VisualVM中的概述中查看

原始配置內容:

-XX:ReservedCodeCacheSize=240m
-XX:+UseCompressedOops
-Dfile.encoding=UTF-8
-XX:SoftRefLRUPolicyMSPerMB=50
-ea
-Dsun.io.useCanonCaches=false
-Djava.net.preferIPv4Stack=true
-Djdk.http.auth.tunneling.disabledSchemes=""
-XX:+HeapDumpOnOutOfMemoryError
-XX:-OmitStackTraceInFastThrow

-XX:ErrorFile=$USER_HOME/java_error_in_idea_%p.log
-XX:HeapDumpPath=$USER_HOME/java_error_in_idea.hprof

-Xmx512m

打印啟動時間插件開發

需要直觀的看到優化前和優化后啟動時間的變化,所以需要簡單做一個Idea的插件開發,關于Idea插件開發的流程建議參考我以前的文章《IDEA插件:多線程文件下載插件開發

JVM的啟動時間到所有組件初始化完成后的時間就看做是IDEA的啟動時間,代碼如下

public class MyApplicationInitializedListener implements ApplicationInitializedListener {
    @Override
    public void componentsInitialized() {
        RuntimeMXBean bean = ManagementFactory.getRuntimeMXBean();
        long startTime = bean.getStartTime();
        long costTime = System.currentTimeMillis() - startTime;

        Messages.showMessageDialog("毫秒:" + costTime, "啟動耗時", Messages.getInformationIcon());
    }
}

plugin.xml中添加如下代碼:

<extensions defaultextensionns="com.intellij">
    <applicationinitializedlistener id="MyApplicationInitializedListener" implementation="cn.silently9527.MyApplicationInitializedListener" />
</extensions>

優化前的啟動信息與時間消耗

根據VisualGC和IDEA啟動插件收集到的信息:

  • IDEA啟動耗時 15s
  • 總共垃圾收集22次,耗時1.2s,其中新生代GC 17次,耗時324ms; 老年代GC 5次,耗時953ms
  • 加載類27526個,耗時 21s

> 按照這個數據來看也算是正常,15s 其實也在接受范圍內,由于本文主要演示性能調優,所以需要測試能否在快一些

開始嘗試優化

調整內存來控制垃圾回收頻率

圖上我們可以看出,啟動參數指定的512m的內存被分配到新生代的只有169m,由于IDEA是我們開發常用的工具,平時的編譯過程也需要足夠的內存,所以我們需要先把總的內存擴大,這里我設置最大的內存-Xmx1024m,為了讓JVM在GC期間不需要再浪費時間再動態計算擴容大小,同時也設置了-Xms1024m;

在啟動的過程中Eden共發生了17次GC,為了減少新生代gc次數,我把新生代的內存大小設置成-Xmn256m;

重新啟動之后查看VisualGC,新生代gc次數從 17次 降低到了 7次,耗時從 324ms 降低到了 152ms。

在調整內存前發生了5次Full GC,調整內存后的依然還是有4次Full GC,但是從兩張圖我們可以看出,老年代的空間還有很多剩余,是不應該發生Full GC的;考慮是否是代碼中有地方手動調用System.gc()出發了Full GC,所以添加了參數-XX:+DisableExplicitGC,再次重新啟動IDEA,結果很失望,依然還有4次Full GC;

再次仔細觀察優化前的圖,注意看 Last Cause: Metadata GC Threshold , 最后一次gc是應該Metaspace區域內存不夠發生的GC,為了驗證我們的猜想,打印出GC日志來看看。在idea.vmoptions中添加打印日志相關的參數:

-XX:+PrintGCDetails
-XX:+PrintGCDateStamps
-Xloggc:../gc.log

> JVM的GC日志的主要參數包括如下幾個:
> - -XX:+PrintGC 輸出GC日志
> - -XX:+PrintGCDetails 輸出GC的詳細日志
> - -XX:+PrintGCTimeStamps 輸出GC的時間戳(以基準時間的形式)
> - -XX:+PrintGCDateStamps 輸出GC的時間戳(以日期的形式,如 2013-05-04T21:53:59.234+0800)
> - -XX:+PrintHeapAtGC 在進行GC的前后打印出堆的信息
> - -Xloggc:../logs/gc.log 日志文件的輸出路徑

重新啟動idea,查看gc.log

> 其中PSYoungGen:表示新生代使用的ParallelScavenge垃圾收集器,31416K-&gt;0K(181248K)表示 gc前已使用的內存大小 -> gc后已使用內存大?。ㄔ搮^域的總內存大?。?/p>

從日志中我們看出每次Full GC都是因為Metadata GC Threshold,而Metaspace每次gc回收的內存幾乎沒有,僅僅是擴大了該區域的容量;找到了原因那就好辦了,添加如下的參數調整Metaspace的大?。?/p>

-XX:MetaspaceSize=256m

再次重啟Idea之后,發現Full GC沒有了,心情很爽

測試打開大項目點擊編譯代碼,發現自己的idea卡死了,查看VisualGC之后發現堆內存都還有空閑,只有Metaspace被全部占滿了,所以是自己給的最大空間設置太小,所以直接去掉了-XX:MaxMetaspaceSize=256m

選擇垃圾收集器

從剛才的gc日志中,我們可以發現默認使用的是ParallelScavenge + Parallel Old垃圾收集器,這個組合注重的是吞吐量,這里我們嘗試換一個注重低延時的垃圾收集器試一試

  • ParNew + CMS

idea.vmoptions中添加如下配置:

-XX:+UseConcMarkSweepGC
-XX:+UseParNewGC

重啟IDEA之后查看VisualGC

很尷尬,同樣發生了6次gc,ParallelScavenge + Parallel Old的組合耗時197ms,而ParNew + CMS的組合耗時379ms;雖然是這個結果,但是我們需要考慮當前只發生了MinorGC,如果發生FullGC了結果又會如何了,大家可以自己測試一下

  • G1

我們在換一個最新的G1垃圾回收器試試,在idea.vmoptions中添加如下配置:

-XX:+UseG1GC

這個結果好像也還是要慢一點點,自己多次測試過這兩個垃圾回收器,雖然每次結果都不一樣,相差不遠,所以垃圾回收器可以自己選擇,這里我們選擇的是G1

類加載時間優化

根據之前的分析,idea啟動加載類27526個,耗時 21s,這個我們有辦法能優化一下嗎?因為idea是常用的開發工具,經常很多人的使用,我們可以認為它的代碼是安全的,是否符合當前虛擬機的要求,不會危害虛擬機的安全,所以我們使用參數-Xverify:none來禁用字節碼的驗證過程

重啟IDEA

耗時下降到了11s,效果還是比較明顯的

總結

做完了所有優化之后,經過多次重啟測試,平均的啟動時間下降到了11s,為了安慰我本次操作沒有白辛苦,搞一張11s以下的圖


寫到最后(點關注,不迷路)

文中或許會存在或多或少的不足、錯誤之處,有建議或者意見也非常歡迎大家在評論交流。

最后,白嫖不好,創作不易,希望朋友們可以點贊評論關注三連,因為這些就是我分享的全部動力來源??

原創不易 轉載請注明出處:https://silently9527.cn/archives/102

我已經從零開始手寫了簡易版springmvc,以及編寫了詳細的說明文檔,希望能夠幫助伙伴們深入理解springmvc核心原理,有需要的朋友歡迎關注公眾號:貝塔學JAVA ,回復源碼即可


查看原文

贊 11 收藏 8 評論 2

認證與成就

  • 獲得 75 次點贊
  • 獲得 5 枚徽章 獲得 0 枚金徽章, 獲得 0 枚銀徽章, 獲得 5 枚銅徽章

擅長技能
編輯

開源項目 & 著作
編輯

(??? )
暫時沒有

注冊于 2020-11-13
個人主頁被 5.1k 人瀏覽

一本到在线是免费观看_亚洲2020天天堂在线观看_国产欧美亚洲精品第一页_最好看的2018中文字幕 <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>