ARTS-9-无锁队列

松花皮蛋me 2019-05-12 16:49
文章首发于公众号 松花皮蛋的黑板报松花皮蛋的黑板报,作者就职于京东,在稳定性保障、敏捷开发、高级JAVA、微服务架构有深入的理解

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安全编码标准学习分享


文章已于2019-06-08 00:09修改,变动:修改文章标题
阅读 187 次