從Timer中學習優先隊列的實現

anquan 發布于2019-08-16 10:32 / 2454人閱讀

摘要：從中學習優先隊列的實現是定時器的實現，用來調度定時執行的任務和執行一次的任務，就像的和的意思，它也可以作為后臺程序運行。通過和的方法可以保證整個優先隊列的關系，保證的是最小的。作用是構建堆，可以從的數組構建堆，來表示優先隊列。

從Timer中學習優先隊列的實現

Timer是Java定時器的實現，用來調度定時執行的任務和執行一次的任務，就像JavaScript的setInterval和setTimeout的意思，它也可以作為后臺程序（Daemon）運行。

Timer

Timer調度的實現是通過TimerThread輔助類來實現的，在構造Timer實例的時候TimerThread就開始運行了；TimerThread需要從隊列（TaskQueue）中獲得需要被執行的任務（TimerTask），這是一個優先隊列，TimeTask的executionTime（TimerTask設置要執行的時間Date.getTime()形式表示的）越小的越優先執行。

TimerThread如何調度

略

TaskQueue data structure

TaskQueue實現了優先隊列的數據結構，內部是一個數組，數組內容實際上是從下標1開始填充的；它其實是用balanced binary heap來表示的，設父節點是queue[n]，則它的兩個字節點分別是queue[2*n]和queue[2*n+1]
這個數據結構的API方法包括：

add(T object)

getMin()

removeMin()

fixDown(int k)

fixUp(int k)

heapify()

最重要的兩個是fixDown和fixUp，表示從queue[k]節點位置開始demoting或promoting。

TaskQueue.fixDown

假設要操作的節點是queue[k]，那么它的子節點分別是queue[j]和queue[j+1]，j=k*2，對queue[k]做demoting處理，

    private void fixDown(int k) {
        int j;
        while ((j = k << 1) <= size && j > 0) {
            if (j < size &&
                queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
                j++; // j indexes smallest kid
            if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
                break;
            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

1.首先比較兩個子節點選出executionTime更小的那個，
2.如果右子節點的executionTime更小，則j++自增，這樣就相當于選擇了右節點（下次fixDown的位置從這里開始）
3.然后父節點和選中的更小executionTime子節點比較
4.如果父節點的executionTime更小，則交換父節點和這個子節點
那么為什么要執行2呢
之前，

之后，

如果是queue[j]變成了父節點就會破壞queue[n]<=queue[2*n+1]的關系。
然后就是一直fixDown到最后一個節點queue[size]。
我們可以思考下這個方法的時間復雜度是不是O(logn)。

TaskQueue.fixUp

假設要操作的節點是queue[k]，那么它的父節點分別是queue[j]，j=k/2，對queue[k]做promoting處理，

    private void fixUp(int k) {
        while (k > 1) {
            int j = k >> 1;
            if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
                break;
            TimerTask tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
            k = j;
        }
    }

promoting比demoting簡單一點，只需要比較queue[k]和queue[j]兩個節點，然后做交換即可。

TaskQueue other methods

通過fixUp和fixDown的方法可以保證整個優先隊列的關系，保證queue[1]的executionTime是最小的。
1.heapify()作用是構建堆，可以從{0,q[1],q[2],...,q[size]}的數組構建堆，來表示優先隊列。

    void heapify() {
        for (int i = size/2; i >= 1; i--)
            fixDown(i);
    }

從中間下標到1做fixDown。

2.add(T object)，往數組中添加元素，重新構建堆

    void add(TimerTask task) {
        // Grow backing store if necessary
        if (size + 1 == queue.length)
            queue = Arrays.copyOf(queue, 2*queue.length);

        queue[++size] = task;
        fixUp(size);
    }

不過需要判斷數組空間是否有剩余，沒有則擴展數組，并拷貝原來的數組元素，最后對queue[size]節點，也是新元素做fixUp。
3.getMin() 直接獲得queue[1]元素
4.removeMin() 將queue[size]節點替換queue[1]，然后對queue[1]做fixDown。

總結

這個TaskQueue的優先隊列的實現代碼是比較清晰的，重要方法的時間復雜度也可以算優秀。
閱讀完這部分代碼后或許可以進一步閱讀PriorityQueue。
附：測試代碼

GPU云服務器云服務器優先隊列消息隊列的實現 python優先隊列隊列實現原理

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69961.html

從Vue.js源碼看異步更新DOM策略及nextTick

摘要：我們發現默認是使用異步執行更新。優先使用，在不存在的情況下使用，這兩個方法的回調函數都會在中執行，它們會比更早執行，所以優先使用。是最后的一種備選方案，它會將回調函數加入中，等到執行。寫在前面因為對Vue.js很感興趣，而且平時工作的技術棧也是Vue.js，這幾個月花了些時間研究學習了一下Vue.js源碼，并做了總結與輸出。文章的原地址：https://github.com/ans...

leo108 2019-08-21 16:43 評論0 收藏0
從Bug中學習--Bug根因分析法

摘要：總結根因分析法是很有價值的，但并不是每一個都需要這樣刨根問底的分析，也沒有這樣的精力和時間允許我們這樣做。所以，在進行根因分析時，要以的價值作為選取標準。一提起測試，大多數人很容易就會聯想到Bug。的確，測試的日常工作離不開Bug，測試工作很重要的一部分就是發現Bug。但是，發現Bug、解決Bug，就足夠了嗎？肯定不是的。 Bug是我們測試人員寶貴的財富，通過Bug我們可以獲得經驗，...

linkin 2019-05-29 17:07 評論0 收藏0
「真?全棧之路」Web前端開發的后端指南

前言在若干次前的一場面試，面試官看我做過python爬蟲/后端的工作，順帶問了我些后端相關的問題：你覺得什么是后端？送命題。當時腦瓦特了，答曰：邏輯處理和數據增刪改查。。。 showImg(https://user-gold-cdn.xitu.io/2019/4/24/16a4ed4fc8c18078); 當場被懟得體無完膚，羞愧難當。事后再反思這問題，結合資料總結了一下。發現自己學過的Re...

chuyao 2019-05-23 16:27 評論0 收藏0
「中高級前端面試」JavaScript手寫代碼無敵秘籍

摘要：第一種直接調用避免在不必要的情況下使用，是一個危險的函數，他執行的代碼擁有著執行者的權利。來自于此外，實現需要考慮實例化后對原型鏈的影響。函數柯里化的主要作用和特點就是參數復用提前返回和延遲執行。手寫路徑導航實現一個new操作符實現一個JSON.stringify 實現一個JSON.parse 實現一個call或 apply 實現一個Function.bind 實現一個繼承實現一個J...

Zhuxy 2019-05-23 16:26 評論0 收藏0
代碼之髓讀后感——如何高效的學習語言

摘要：代碼之髓讀后感如何高效的學習語言技術讀后感王垠如何掌握程序語言代碼之髓這本書里提出了三種學習語言的方法如何高效的學習語言在比較中學習在歷史中學習在實踐中學習在比較中學習通過比較多種語言，總結出某種語言的獨有特點，以及多種語言的共有特點。 title: 代碼之髓讀后感——如何高效的學習語言date: 2017-07-08 17:17:00categories: 技術tags: 讀后感 ...

ivyzhang 2019-08-15 10:36 評論0 收藏0