我要分享技术
0%

ARTS-6

发表于 更新于 分类于

ARTS-6

Algorithm

引言

放了个劳动节假, 玩的有点疯了, 所以这个题目就来个简单点吧

Description

题目

3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:

    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

大意

给出一个整数数组nums, 找出数组中所有的不同组合 a, b, c , 使之满足 a + b + c 之和等于0, 输出他们。

思路

题目提供的数组是不保证顺序的,在这种情况下, 如果直接处理,那么我们不可避免的就要进行全遍历了, 显然这不可能是最优解, 所以, 最初的思路就是使源数组有序, 首先, 对它进行排序,使之升序排列。

对于有序数组, 我们只需要控制游标移动就可以逐步进行和的数值调整, 所以, 每一次, 选取一个基准元素作为最左侧元素, 然后, 设置两个游标在它右侧, 逐步调整这两个游标使和为0即可。

Resolution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      int dimension = nums.size();
      sort(nums.begin(), nums.end());
      vector<vector<int>> result;
      for (int i=0; i<dimension-2; ++i) {
        if (nums[i] > 0) break;
        int f=i+1, t=dimension-1;
        while (f < t) {
          int sum = nums[i] + nums[f] + nums[t];
          if (sum == 0) {
            result.push_back(vector<int>({nums[i], nums[f], nums[t]}));
            while (i < dimension-2 && nums[i]==nums[i+1]) {i++;}
            do {t--;} while(f < t && nums[t]==nums[t+1]);
            do {f++;} while (f < t && nums[f]==nums[f-1]);
          } else if (sum > 0) {
           t--;
          } else {
           f++;
          }
        }
      }
      return result;
    }
};

Result

Success
Details 
Runtime: 100 ms, faster than 91.61% of C++ online submissions for 3Sum.
Memory Usage: 14.9 MB, less than 97.80% of C++ online submissions for 3Sum.
Time Submitted Status Runtime Memory Language
a few seconds ago Accepted 100 ms 14.9 MB cpp

还可能的优化

在游标调整过程中, 感觉至少一个游标的调整可以使用二分调整, 不至于每次只调整一点, 这样感觉可以进一步优化执行效率。

Review

本次Review的文在这里: Synchronization and Object Locking

引言

之前就立了Flag, 要写一篇java虚拟机关于锁实现的分享, 在参考了郑雨迪老师关于HotSpot关于实现synchronized的文章后, 整理了我对hotspot做法的理解, 这篇文章是其中一篇参考文, 在阅读之余, 进行分享。

内容

作为java语言的主要优势之一, java语言提供了语言层面的内建多线程机制的支持。任意一个对象在不同线程间共享访问可以被加锁, 以同步不同线程的访问。java提供了原生的临界区代码设计, 它通过一个共享的锁对象, 一次仅允许一个进程进入临界区执行, 第一个进入临界区的线程会将对象加锁, 当下一个线程要进入同一个临界区之前就必须等待前一个对所对象加锁的线程释放锁。

对于 Java HotSpot™ VM 一个对象由指向类的指针和一个字的头作为先导, 本文中,把它称呼为对象头。对象头存储对象特征哈希码和在垃圾回收标记代数的bit位, 也用于实现瘦锁方案。

下图展示了对象头的布局结构和它在不同状态下所代表的含义。

其中, 对象头的最后两个位标记其用途,这里需要特别特别特别注意, 因为其取值特别容易被记混, 而且, 我记错了好多次。

对象头的标记位的取值和含义

  • 01 无锁或者偏向锁
  • 00 轻量锁
  • 10 重量锁
  • 11 垃圾回收相关
00 01 10 11
轻量级锁 无锁或者偏向锁 重量级锁 gc相关

为什么这么取值

如果不弄懂这个加锁的过程, 那么对于为何这么取值会感到很困惑, 为什么状态不是按照直观顺序的呢, 这里关键应该是轻量级锁的加锁过程。

  1. 判断如果标记位不为01(无锁), 那么按照加锁过程去处理,否则, 进行下一步
  2. 将对象头和对象地址构造一个锁记录, 存入当前栈帧。
  3. 将锁记录的地址cas存入对象头。 因为栈帧是按照字(word)对齐的, 其地址肯定是00结尾, 所以, cas成功后, 对象头的标记位肯定为00, 此状态为轻量级锁加锁成功。

所以,以上轻量级加锁过程说明了为什么轻量级锁时对象头的标记位为00。 记住了这个过程, 就不太容易记混了00的含义了。

HotSpot™ 对象头结构

图片内容引自OpenJDK的Wiki https://wiki.openjdk.java.net/download/attachments/11829266/Synchronization.gif?version=4&modificationDate=1208918680000&api=v2

图右侧部分展示的是正常(标准)的锁的状态转换过程。

下面是我按照文档自己总结的一个轻量锁的加锁过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
graph TB
    
    SUCC[拿到锁,进入临界区]
    END(结束)
    Start(monitorenter)-->CheckBit{末位是否为 01}
    CheckBit-->|是|LightLocking[复制对象头到当前栈帧]
    LightLocking-->SwapHeader[构造锁记录到栈帧并将地址cas对象头]
    SwapHeader-->CheckSwapSucc{CAS操作成功}
    CheckSwapSucc-->|CAS成功|LightLocked[轻量级锁成功]
    LightLocked-->SUCC
    CheckSwapSucc-->|CAS失败|SwapFailed{对象头指针指向当前栈帧}
    
    CheckBit-->|否|HaveLocked[此时已有线程进入了临界区]
    HaveLocked-->CheckLockType{此时锁类型}
    CheckLockType-->|标记位00|ThinLocked[此时该对象为轻量锁]
    ThinLocked-->SwapFailed{对象头指针指向当前栈帧}
    
    SwapFailed-->|是|HoldBySelf[栈帧内的锁记录置0]
    HoldBySelf-->LightLocked
        
    SwapFailed-->|否|Inflate[膨胀为重锁]
    Inflate-->END
    
    CheckLockType-->|标记位10|HeavyWeightLocked[此时该对象为重锁]
    HeavyWeightLocked-->Suspend[线程挂起等待唤醒]
    Suspend-->END
    SUCC-->END

锁状态示意图, 图中忽略了偏向锁和自旋过程。

Tips

Vim 中, 往命令中粘贴内容。

引言

我是一个资深vimer, 我承认我现在分享这个内容真实丢vimer的脸。但是作为一个手动挡, 我一直都是这么做的。 每当要在文档中搜索或者替换一个内容的时候, 我都会不厌其烦的一个个字符敲入, :% s/search_my_content_balabalabala/i am the new balabalabala/g 然后认真反复检查3遍, 按下enter键, 一次替换完成, 我在过去的七八年里都是这样做的。

我见要分享的这个小技巧, 就是为了简化这个过程的, 虽然我自己并不常用它。 如何在命令行里粘贴剪切板的内容。

做法

<C-r> 在命令输入模式下, 按快捷键 Ctrl + R 开启粘贴模式, 再键入一个寄存器名, 就会将该寄存器内的内容粘贴在命令上。

于是, 搜索做法就变成了 1. 切换成visual模式 (v) 2. 复制想要搜索的内容 (y) 3. 进入命令模式, 敲入搜索/ 4. Ctrl + R 5. 按", 将刚复制的内容贴入命令, 然后Enter搜索

给出一个demo

预备一个文件:

原文件 1. 切换成visual模式, 复制搜索内容Text (normal下移动光标到Text按v,然后e到单词末尾, 按y)

复制待选内容
  1. 进入命令模式, 搜索/
搜索
  1. 键入Ctrl + r 进入选取寄存器步骤
选取寄存器
  1. 键入", 匿名寄存器刚复制的内容上屏, 回车搜索
搜索内容

这里有一点, 如果要粘贴系统剪切板的内容, 那么寄存器名字应输入0,而不是+

Share

引言

这是一篇版权文章, 非订阅用户阅读可能会受到限制。这是一篇讲解hotspot关于如何实现synchronized关键字的简单教学文, 后面我会分享我参考这篇文章写得自己关于jvm的synchronized的见解。

内容

Java虚拟机是怎么实现synchronized的？

End