松花皮蛋的黑板報
  • 分享在京東工作的技術感悟,還有JAVA技術和業內最佳實踐,大部分都是務實的、能看懂的、可復現的

掃一掃
關注公眾號

ARTS-9-無鎖隊列

博客首頁文章列表 松花皮蛋me 2019-05-12 16:49

ARTS的初衷

Algorithm: 主要是為了編程訓練和學習。

Review:主要是為了學習英文

Tip:主要是為了總結和歸納在是常工作中所遇到的知識點。學習至少一個技術技巧。在工作中遇到的問題,踩過的坑,學習的點滴知識。

Share:主要是為了建立影響力,能夠輸出價值觀。分享一篇有觀點和思考的技術文章

https://www.zhihu.com/question/301150832

一、Algorithm

Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string’s length and k will not exceed 104.

Example 1:

Input:
s = “ABAB”, k = 2

Output:
4

Explanation:
Replace the two ‘A’s with two ‘B’s or vice versa.
Example 2:

Input:
s = “AABABBA”, k = 1

Output:
4

Explanation:
Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”.
The substring “BBBB” has the longest repeating letters, which is 4.

    public int characterReplacement(String s, int k) {
        //滑動窗口法
//        int longestRep = 0;
//        for(int i=0;i<s.length();i++) {
//            int replaceNum = 0;
//            for (int j=i+1;j<s.length();j++) {
//                if(s.charAt(j)!=s.charAt(i)) {
//                    replaceNum++;
//                }
//                //k可能為0
//                if(replaceNum>=k) {
//                    //還需判斷next
//                    while (j<s.length() && s.charAt(j++)==s.charAt(i));
//                    longestRep =  j-i+1>longestRep?j-i+1:longestRep;
//                    break;
//                }
//            }
//        }
//        return longestRep;

        int uniqueCount = 0;
        int left = 0;
        int max = 0;
        int[] count = new int[26];
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            uniqueCount = Math.max(uniqueCount, ++count);
            int replaceCount = right - left + 1 - uniqueCount;
            if (replaceCount > k) {
                count[s.charAt(left++) - 'A']--;
            } else {
                max = Math.max(max, right - left + 1);
            }
        }
        return max;

    }

二、Review

Implementing Lock-Free Queue無鎖隊列的實現

CAS:Compare&Set,當且僅當預期值E和內存值V相等時,將內存值V修改為新值U

進隊列:

EnQueue(x) 
{
    q = new record();
    q->value = x;
    q->next = NULL;

    do {
        p = tail;
    } while( CAS(p->next, NULL, q) != TRUE); 

    CAS(tail, p, q); //置尾結點
}

如果某個線程在用CAS更新tail指針之前,線程掛掉則其他線程會進入死循環,因為tail->next!=null永遠滿足條件

進隊列改良版:

EnQueue(x) 
{
    q = new record();
    q->value = x;
    q->next = NULL;

    p = tail;
    oldp = p
    do {
        while (p->next != NULL)
            p = p->next;
    } while( CAS(p.next, NULL, q) != TRUE); 

    CAS(tail, oldp, q); 
}

因為CAS判斷的是指針的地址,所以存在ABA問題,JAVA并發中一般使用版本號解決這個問題,文章給出的是使用結點內存引用計數refcnt

SafeRead(q)
{
    loop:
        p = q->next;
        if (p == NULL){
            return p;
        }

        Fetch&Add(p->refcnt, 1);

        if (p == q->next){
            return p;
        }else{
            Release(p);
        }
    goto loop;
}

更多細節請閱讀:https://coolshell.cn/articles/8239.html

三、Tip

用Chrome的Network面板分析HTTP報文的技巧

按類型過濾,比如Media、CSS等

按屬性過濾,比如Domain、has-reponse-header、is:running、is:from-cache、larger-than、method、mime-type、minxed-content、scheme、set-cookie-domain、set-cookie-name、set-cookie-value、status-code

請求列表的排序,start-time、response-time、end-time、total-duration、latency(最短響應時間)

四、Share

JAVA安全編碼標準學習分享

黑龙江6+1开奖结果查询