標籤: 南投搬家公司費用

Java8之前的日期和時間API，存在一些問題，最重要的就是線程安全的問題。這些問題都在Java8中的日期和時間API中得到了解決，而且Java8中的日期和時間API更加強大。

傳統時間格式化的線程安全問題

示例：

import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.concurrent.*;

public class TestOldSimpleDateFormat {
    public static void main(String[] args) throws Exception {
        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        Callable<Date> task = new Callable<Date>() {
            @Override
            public Date call() throws Exception {
                return sdf.parse("2020-01-01");
            }
        };
        ExecutorService pool = Executors.newFixedThreadPool(10);
        List<Future<Date>> list = new ArrayList<>();
        for (int i=0;i<10;i++){
            Future<Date> future = pool.submit(task);
            list.add(future);
        }
        for (Future<Date> future : list){
            System.out.println(future.get());
        }

　　　　　pool.shutdown();
    }
}

以上代碼運行會報錯：

 

 

報錯緣由：取部分源碼解釋

    /**
     * SimpleDateFormat 類的 parse 方法 部分源碼
     */
    public Date parse(String source) throws ParseException
    {
        ParsePosition pos = new ParsePosition(0);
        Date result = parse(source, pos); 
        if (pos.index == 0)
            throw new ParseException("Unparseable date: \"" + source + "\"" ,
                pos.errorIndex);
        return result;
    }

public Date parse(String text, ParsePosition pos)
    {
        // 省略上面諸多代碼
        Date parsedDate;

        CalendarBuilder calb = new CalendarBuilder();
        try {
            //這裏這個 calendar 對象是 SimpleDateFormat 類的父類 DateFormat 中的屬性  ： protected Calendar calendar;
            parsedDate = calb.establish(calendar).getTime();//這個 calb.establish(calendar) 方法中，這個方法中的主要步驟不是原子操作，並且會對 calendar 對象進行修改，所以在多線程環境下就會出現線程安全問題。
            // 省略下面面諸多代碼
        }
        catch (IllegalArgumentException e) {
            //省略.........................
            return null;
        }
        return parsedDate;
    }

 Calendar establish(Calendar cal) {
        boolean weekDate = isSet(WEEK_YEAR)
                            && field[WEEK_YEAR] > field[YEAR];
        if (weekDate && !cal.isWeekDateSupported()) {
            // Use YEAR instead
            if (!isSet(YEAR)) {
                set(YEAR, field[MAX_FIELD + WEEK_YEAR]);
            }
            weekDate = false;
        }

        cal.clear();
        // Set the fields from the min stamp to the max stamp so that
        // the field resolution works in the Calendar.
        for (int stamp = MINIMUM_USER_STAMP; stamp < nextStamp; stamp++) {
            for (int index = 0; index <= maxFieldIndex; index++) {
                if (field[index] == stamp) {
                    cal.set(index, field[MAX_FIELD + index]);
                    break;
                }
            }
        }

        if (weekDate) {
            int weekOfYear = isSet(WEEK_OF_YEAR) ? field[MAX_FIELD + WEEK_OF_YEAR] : 1;
            int dayOfWeek = isSet(DAY_OF_WEEK) ?
                                field[MAX_FIELD + DAY_OF_WEEK] : cal.getFirstDayOfWeek();
            if (!isValidDayOfWeek(dayOfWeek) && cal.isLenient()) {
                if (dayOfWeek >= 8) {
                    dayOfWeek--;
                    weekOfYear += dayOfWeek / 7;
                    dayOfWeek = (dayOfWeek % 7) + 1;
                } else {
                    while (dayOfWeek <= 0) {
                        dayOfWeek += 7;
                        weekOfYear--;
                    }
                }
                dayOfWeek = toCalendarDayOfWeek(dayOfWeek);
            }
            cal.setWeekDate(field[MAX_FIELD + WEEK_YEAR], weekOfYear, dayOfWeek);
        }
        return cal;
    }

綜上，我們可以看到 SimpleDateFormat 類中的parse 方法，調用了 CalendarBuilder 的 establish(calendar) 方法，並在方法中，對 calendar 對象進行了各種判斷及修改，並且這些操作都不是原子操作或同步操作，而這個calendar 對象又是 SimpleDateFormat 的父類 DateFormat 的一個實例變量，所以，在多線程同時調用SimpleDateFormat 的 parse 方法的時候，就會出現線程安全問題。

針對以上異常，JAVA8之前的解決辦法：

1. 將 SimpleDateFormat 對象定義成局部變量。

2. 加鎖。

3. 使用ThreadLocal，每個線程都擁有自己的SimpleDateFormat對象副本。

示例（加鎖）：

        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        Callable<Date> task = new Callable<Date>() {
            @Override
            public synchronized Date call() throws Exception {//加個同步，解決問題
                return sdf.parse("2020-01-01");
//                return DateFormatThreadLocal.convert("2020-01-01");
            }
        };
        ExecutorService pool = Executors.newFixedThreadPool(10);
        List<Future<Date>> list = new ArrayList<>();
        for (int i=0;i<10;i++){
            Future<Date> future = pool.submit(task);
            list.add(future);
        }
        for (Future<Date> future : list){
            System.out.println(future.get());
        }
        pool.shutdown();

 

示例（ThreadLocal）：

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.Date;

public class DateFormatThreadLocal {
    private static final ThreadLocal<DateFormat> df = new ThreadLocal<DateFormat>() {
        protected DateFormat initialValue() {
            return new SimpleDateFormat("yyyy-MM-dd");
        }
    };
    public static Date convert(String source) throws Exception {
        return df.get().parse(source);
    }
}


////////////////////////////////////////////////////////////////

public class TestOldSimpleDateFormat {
    public static void main(String[] args) throws Exception {
//        SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
        Callable<Date> task = new Callable<Date>() {
            @Override
            public Date call() throws Exception {
//                return sdf.parse("2020-01-01");
                return DateFormatThreadLocal.convert("2020-01-01");
            }
        };
        ExecutorService pool = Executors.newFixedThreadPool(10);
        List<Future<Date>> list = new ArrayList<>();
        for (int i=0;i<10;i++){
            Future<Date> future = pool.submit(task);
            list.add(future);
        }
        for (Future<Date> future : list){
            System.out.println(future.get());
        }

　　　　　pool.shutdown();

} }

 

JAVA8的解決辦法：使用新的API（DateTimeFormatter  和 LocalDate ）

示例：

import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

public class TestOldSimpleDateFormat {
    public static void main(String[] args) throws Exception {
        DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd");

        Callable<LocalDate> task = new Callable<LocalDate>() {
            @Override
            public LocalDate call() throws Exception {
//                return sdf.parse("2020-01-01");
                return LocalDate.parse("2020-01-01",formatter);
            }
        };
        ExecutorService pool = Executors.newFixedThreadPool(10);
        List<Future<LocalDate>> list = new ArrayList<>();
        for (int i=0;i<10;i++){
            Future<LocalDate> future = pool.submit(task);
            list.add(future);
        }
        for (Future<LocalDate> future : list){
            System.out.println(future.get());
        }
        pool.shutdown();
    }
}

 

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

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

微信公眾號：小超說

這是查找算法系列文章的第一篇，助你快速入門二叉樹

什麼是樹(Tree)？

我們首先來看一些圖片：

其中，第一、二、四個都是樹，第三個不是。樹的特點很明顯吧！

其中每個元素叫做“節點”；用來連接相鄰節點之間的關係，我們稱之為“父子關係”。例如在圖一中，A節點是B節點的父節點，B節點是A節點的子結點,同時，B節點和Q節點是同一個父節點A的子節點，所以它們之間互相成為兄弟節點。我們把沒有父節點的節點稱為根節點，也就是圖一中的A節點。我們把沒有子節點的節點稱為恭弘=叶 恭弘子節點，比如圖一中的D、E、F、G節點。這些概念都是顯而易見，但卻是最基本的東西。

二叉樹

二叉樹，自然就是每個節點最多有兩個分支，即兩個子節點的一種樹，兩個分支分別稱為左子樹和右子樹。還是那上面那張圖舉例，圖一、圖二和圖四都是二叉樹，因為它們每個節點都最多含有兩個子節點。其中，圖一又稱為滿二叉樹，圖四又稱為完全二叉樹。而之所以出現完全二叉樹的概念，其實是基於二叉樹的物理存儲方式。

二叉樹的存儲方法

• 基於鏈表的鏈式存儲法
• 基於數組的順序存儲法

鏈式存儲法：

我們為每個節點創建一個Node對象:

class Node{
		int data;
		Node left,right;
}

每個節點都是一個Node對象，它包含我們所需要存儲的數據，指向左子節點的引用，直向右子節點的引用，就像鏈表一樣將整個樹串起來。如果該節點沒有左子節點，則Node.left==null或者Node.right==null.

順序存儲法：

我們把根節點儲存在下標為i=1的位置，那麼左子節點儲存在2*i=2的位置，右子節點儲存在下標為2*i+1=2的位置。依此類推，完成樹的存儲。藉助下標運算，我們可以很輕鬆的從父節點跳轉到左子節點和右子節點或者從任意一個子節點找到它的父節點。如果X的位置為i，則它的兩個子節點的下標分別為2i和2i+1,它的父節點的位置為i/2(這裏結果向下取整)。

具體如下圖所示：可以發現，只有完全二叉樹存儲的效率才最高，最省內存

二叉樹的遍歷

二叉樹的遍歷操作主要有三種

• 前序遍歷
• 中序遍歷
• 後序遍歷

前序遍歷是指，對於樹中的任意節點來說，先打印這個節點，然後再打印它的左子樹，最後打印它的右子樹。

中序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它本身，最後打印它的右子樹。

後序遍歷是指，對於樹中的任意節點來說，先打印它的左子樹，然後再打印它的右子樹，最後打印這個節點本身。

注意，這其中有點遞歸的味道

還是以剛才的圖為例：

• 前序遍歷：A->B->D->E->C->F
• 中序遍歷：D->B->E->A->F->C
• 後序遍歷：D->E->B->F->C->A

具體的代碼實現(寫出遞歸即可）：

public void preOrder(Node root){
	if(root==null) return;
	System.out.println(root.data);//打印root節點的值
    preOrder(root.left);
    preOrder(root.right);
}

public void inOrder(Node root){
	if(root==null) return;
	inOrder(root.left);
	Systrm.out.println(root.data);
	inOrder(root.right);
}

public void inOrder(Node root){
	if(root==null) return;
	inOrder(root.left)
	inOrder(root.right);
	Systrm.out.println(root.data);
}

二叉樹遍歷的時間複雜度是O(n),這是因為每個節點最多會被訪問兩次，（遞歸時函數進棧和出棧），所以遍歷操作的訪問次數跟節點的個數 n 成正比，也就是說二叉樹遍歷的時間複雜度是 O(n)。

展望

經過上面的介紹，我們已經大致對二叉樹有了一個基本的認識，那麼，二叉樹存在的意義是什麼呢？我們可以基於這種數據結構設計出哪些高效的算法呢？下一次我們將介紹二叉查找樹（Binary Search Tree），我們將定義一種數據結構並維護它的性質。

題外話：對於算法初學者，推薦一本十分 nice 的書籍 《算法第四版》，裏面各種配圖十分詳細。如果你需要电子版文件，後台回復算法4即可獲得下載鏈接。後台回復 算法01 送你一份 算法與數據結構思維導圖。最後，希望我們一起進步，一起成長！

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

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準