成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

從Timer中學(xué)習(xí)優(yōu)先隊(duì)列的實(shí)現(xiàn)

anquan / 2493人閱讀

摘要：從中學(xué)習(xí)優(yōu)先隊(duì)列的實(shí)現(xiàn)是定時(shí)器的實(shí)現(xiàn)，用來(lái)調(diào)度定時(shí)執(zhí)行的任務(wù)和執(zhí)行一次的任務(wù)，就像的和的意思，它也可以作為后臺(tái)程序運(yùn)行。通過(guò)和的方法可以保證整個(gè)優(yōu)先隊(duì)列的關(guān)系，保證的是最小的。作用是構(gòu)建堆，可以從的數(shù)組構(gòu)建堆，來(lái)表示優(yōu)先隊(duì)列。

從Timer中學(xué)習(xí)優(yōu)先隊(duì)列的實(shí)現(xiàn)

Timer是Java定時(shí)器的實(shí)現(xiàn)，用來(lái)調(diào)度定時(shí)執(zhí)行的任務(wù)和執(zhí)行一次的任務(wù)，就像JavaScript的setInterval和setTimeout的意思，它也可以作為后臺(tái)程序（Daemon）運(yùn)行。

Timer

Timer調(diào)度的實(shí)現(xiàn)是通過(guò)TimerThread輔助類來(lái)實(shí)現(xiàn)的，在構(gòu)造Timer實(shí)例的時(shí)候TimerThread就開(kāi)始運(yùn)行了；TimerThread需要從隊(duì)列（TaskQueue）中獲得需要被執(zhí)行的任務(wù)（TimerTask），這是一個(gè)優(yōu)先隊(duì)列，TimeTask的executionTime（TimerTask設(shè)置要執(zhí)行的時(shí)間Date.getTime()形式表示的）越小的越優(yōu)先執(zhí)行。

TimerThread如何調(diào)度

略

TaskQueue data structure

TaskQueue實(shí)現(xiàn)了優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，內(nèi)部是一個(gè)數(shù)組，數(shù)組內(nèi)容實(shí)際上是從下標(biāo)1開(kāi)始填充的；它其實(shí)是用balanced binary heap來(lái)表示的，設(shè)父節(jié)點(diǎn)是queue[n]，則它的兩個(gè)字節(jié)點(diǎn)分別是queue[2*n]和queue[2*n+1]
這個(gè)數(shù)據(jù)結(jié)構(gòu)的API方法包括：

add(T object)

getMin()

removeMin()

fixDown(int k)

fixUp(int k)

heapify()

最重要的兩個(gè)是fixDown和fixUp，表示從queue[k]節(jié)點(diǎn)位置開(kāi)始demoting或promoting。

TaskQueue.fixDown

假設(shè)要操作的節(jié)點(diǎn)是queue[k]，那么它的子節(jié)點(diǎn)分別是queue[j]和queue[j+1]，j=k*2，對(duì)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.首先比較兩個(gè)子節(jié)點(diǎn)選出executionTime更小的那個(gè)，
2.如果右子節(jié)點(diǎn)的executionTime更小，則j++自增，這樣就相當(dāng)于選擇了右節(jié)點(diǎn)（下次fixDown的位置從這里開(kāi)始）
3.然后父節(jié)點(diǎn)和選中的更小executionTime子節(jié)點(diǎn)比較
4.如果父節(jié)點(diǎn)的executionTime更小，則交換父節(jié)點(diǎn)和這個(gè)子節(jié)點(diǎn)
那么為什么要執(zhí)行2呢
之前，

之后，

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

TaskQueue.fixUp

假設(shè)要操作的節(jié)點(diǎn)是queue[k]，那么它的父節(jié)點(diǎn)分別是queue[j]，j=k/2，對(duì)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簡(jiǎn)單一點(diǎn)，只需要比較queue[k]和queue[j]兩個(gè)節(jié)點(diǎn)，然后做交換即可。

TaskQueue other methods

通過(guò)fixUp和fixDown的方法可以保證整個(gè)優(yōu)先隊(duì)列的關(guān)系，保證queue[1]的executionTime是最小的。
1.heapify()作用是構(gòu)建堆，可以從{0,q[1],q[2],...,q[size]}的數(shù)組構(gòu)建堆，來(lái)表示優(yōu)先隊(duì)列。

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

從中間下標(biāo)到1做fixDown。

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

    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);
    }

不過(guò)需要判斷數(shù)組空間是否有剩余，沒(méi)有則擴(kuò)展數(shù)組，并拷貝原來(lái)的數(shù)組元素，最后對(duì)queue[size]節(jié)點(diǎn)，也是新元素做fixUp。
3.getMin() 直接獲得queue[1]元素
4.removeMin() 將queue[size]節(jié)點(diǎn)替換queue[1]，然后對(duì)queue[1]做fixDown。

總結(jié)

這個(gè)TaskQueue的優(yōu)先隊(duì)列的實(shí)現(xiàn)代碼是比較清晰的，重要方法的時(shí)間復(fù)雜度也可以算優(yōu)秀。
閱讀完這部分代碼后或許可以進(jìn)一步閱讀PriorityQueue。
附：測(cè)試代碼

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69961.html

相關(guān)文章

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

    摘要：我們發(fā)現(xiàn)默認(rèn)是使用異步執(zhí)行更新。優(yōu)先使用，在不存在的情況下使用，這兩個(gè)方法的回調(diào)函數(shù)都會(huì)在中執(zhí)行，它們會(huì)比更早執(zhí)行，所以優(yōu)先使用。是最后的一種備選方案，它會(huì)將回調(diào)函數(shù)加入中，等到執(zhí)行。 寫在前面 因?yàn)閷?duì)Vue.js很感興趣，而且平時(shí)工作的技術(shù)棧也是Vue.js，這幾個(gè)月花了些時(shí)間研究學(xué)習(xí)了一下Vue.js源碼，并做了總結(jié)與輸出。文章的原地址：https://github.com/ans...

    leo108 評(píng)論0 收藏0

  • 從Bug中學(xué)習(xí)--Bug根因分析法

    摘要：總結(jié)根因分析法是很有價(jià)值的，但并不是每一個(gè)都需要這樣刨根問(wèn)底的分析，也沒(méi)有這樣的精力和時(shí)間允許我們這樣做。所以，在進(jìn)行根因分析時(shí)，要以的價(jià)值作為選取標(biāo)準(zhǔn)。 一提起測(cè)試，大多數(shù)人很容易就會(huì)聯(lián)想到Bug。的確，測(cè)試的日常工作離不開(kāi)Bug，測(cè)試工作很重要的一部分就是發(fā)現(xiàn)Bug。但是，發(fā)現(xiàn)Bug、解決Bug，就足夠了嗎？肯定不是的。 Bug是我們測(cè)試人員寶貴的財(cái)富，通過(guò)Bug我們可以獲得經(jīng)驗(yàn)，...

    linkin 評(píng)論0 收藏0

  • 「真?全棧之路」Web前端開(kāi)發(fā)的后端指南

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

    chuyao 評(píng)論0 收藏0

  • 「中高級(jí)前端面試」JavaScript手寫代碼無(wú)敵秘籍

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

    Zhuxy 評(píng)論0 收藏0

  • 代碼之髓讀后感——如何高效的學(xué)習(xí)語(yǔ)言

    摘要：代碼之髓讀后感如何高效的學(xué)習(xí)語(yǔ)言技術(shù)讀后感王垠如何掌握程序語(yǔ)言代碼之髓這本書(shū)里提出了三種學(xué)習(xí)語(yǔ)言的方法如何高效的學(xué)習(xí)語(yǔ)言在比較中學(xué)習(xí)在歷史中學(xué)習(xí)在實(shí)踐中學(xué)習(xí)在比較中學(xué)習(xí)通過(guò)比較多種語(yǔ)言，總結(jié)出某種語(yǔ)言的獨(dú)有特點(diǎn)，以及多種語(yǔ)言的共有特點(diǎn)。 title: 代碼之髓讀后感——如何高效的學(xué)習(xí)語(yǔ)言date: 2017-07-08 17:17:00categories: 技術(shù)tags: 讀后感 ...

    ivyzhang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<