Nicksxs's Blog

题目介绍

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的  

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

分析与题解

两个数组的交集，最简单就是两层循环了把两个都存在的找出来，不过还有个要去重的问题，稍微思考下可以使用集合 set 来处理，先把一个数组全丢进去，再对比另外一个，如果出现在第一个集合里就丢进一个新的集合，最后转换成数组，这次我稍微取了个巧，因为看到了提示里的条件，两个数组中的元素都是不大于 1000 的，所以就搞了个 1000 长度的数组，如果在第一个数组出现，就在对应的下标设置成 1，如果在第二个数组也出现了就加 1，

code

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
28
29
30
31
32
33
34
35
36

public int[] intersection(int[] nums1, int[] nums2) {
    // 大小是 1000 的数组，如果没有提示的条件就没法这么做
    // define a array which size is 1000, and can not be done like this without the condition in notice
        int[] inter = new int[1000];
        int[] outer;
        int m = 0;
        for (int j : nums1) {
            //  这里得是设置成 1，因为有可能 nums1 就出现了重复元素，如果直接++会造成结果重复
            // need to be set 1, cause element in nums1 can be duplicated
            inter[j] = 1;
        }
        for (int j : nums2) {
            if (inter[j] > 0) {
                // 这里可以直接+1，因为后面判断只需要判断大于 1
                // just plus 1, cause we can judge with condition that larger than  1
                inter[j] += 1;
            }
        }
        for (int i = 0; i < inter.length; i++) {
            // 统计下元素数量
            // count distinct elements
            if (inter[i] > 1) {
                m++;
            }
        }
        // initial a array of size m
        outer = new int[m];
        m = 0;
        for (int i = 0; i < inter.length; i++) {
            if (inter[i] > 1) {
                // add to outer
                outer[m++] = i;
            }
        }
        return outer;
    }

上次本来想在换车牌后面聊下这个话题，为啥要聊这个话题呢，也很简单，在地铁上看到一对猜测是情侣或者比较关系好的男女同学在聊，因为是这位男同学是大学学的工科，然后自己爱好设计绘画相关的，可能还以此赚了点钱，在地铁上讨论男的要不要好好努力把大学课程完成好，大致的观点是没必要，本来就不适合，这一段我就不说了，恋爱人的嘴，信你个鬼。
后面男的说在家里又跟他爹吵了关于男足的，估计是那次输了越南，实话说我不是个足球迷，对各方面技术相关也不熟，只是对包括这个人的解释和网上一些观点的看法，纯主观，这次地铁上这位说的大概意思是足球这个训练什么的很难的，要想赢越南也很难的，不是我们能嘴炮的；在网上看到一个赞同数很多的一个回答，说什么中国是个体育弱国，但是由于有一些乒乓球，跳水等小众项目比较厉害，让民众给误解了，首先我先来反驳下这个偷换概念的观点，第一所谓的体育弱国，跟我们觉得足球不应该这么差没半毛钱关系，因为体育弱国，我们的足球本来就不是顶尖的，也并不是去跟顶尖的球队去争，以足球为例，跟巴西，阿根廷，英国，德国，西班牙，意大利，法国这些足球强国，去比较，我相信没有一个足球迷会这么去做对比，因为我们足球历史最高排名是 1998 年的 37 名，最差是 100 名，把能数出来的强队都数完，估计都还不会到 37，所以根本没有跟强队去做对比，第二体育弱国，我们的体育投入是在逐年降低吗，我们是因战乱没法好好训练踢球？还是这帮傻逼就不争气，前面也说了我们足球世界排名最高 37，最低 100，那么前阵子我们输的越南是第几，目前我们的排名 77 名，越南 92 名，看明白了么，轮排名我们都不至于输越南，然后就是这个排名，这也是我想回应那位地铁上的兄弟，我觉得除了造核弹这种高精尖技术，绝大部分包含足球这类运动，遵循类二八原则，比如满分是 100 分，从 80 提到 90 分或者 90 分提到 100 分非常难，30 分提到 40 分，50 分提到 60 分我觉得都是可以凭后天努力达成的，基本不受天赋限制，这里可以以篮球来类比下，相对足球的确篮球没有那么火，或者行业市值没法比，但是也算是相对大众了，中国在篮球方面相对比较好一点，在 08 年奥运会冲进过八强，那也不是唯一的巅峰，但是我说这个其实是想说明两方面的事情，第一，像篮球一样，状态是有起起伏伏，排名也会变动，但是我觉得至少能维持一个相对稳定的总体排名和持平或者上升的趋势，这恰恰是我们这种所谓的“体育弱国”应该走的路线，第二就是去支持我的类二八原则的，可以看到我们的篮球这两年也很垃圾，排名跌到 29 了，那问题我觉得跟足球是一样的，就是不能脚踏实地，如斯科拉说的，中国篮球太缺少竞争，打得好不好都是这些人打，打输了还是照样拿钱，相对足球，篮球的技术我还是懂一些的，对比 08 年的中国男篮，的确像姚明跟王治郅这样的天赋型+努力型球员少了以后竞争力下降在所难免，但是去对比下基本功，传球，投篮，罚球稳定性，也完全不是一个水平的，这些就是我说的，可以通过努力训练拿 80 分的，只要拿到 80 分，甚至只要拿到 60 分，我觉得应该就还算对得起球迷了，就像 NBA 里球队也会有核心球员的更替，战绩起起伏伏，但是基本功这东西，防守积极性，我觉得不随核心球员的变化而变化，就像姚明这样的天赋，其实他应该还有一些先天缺陷，大脚趾较长等，但是他从 CBA 到 NBA，在 NBA 适应并且打成顶尖中锋，离不开刻苦训练，任何的成功都不是纯天赋的，必须要付出足够的努力。
说回足球，如果像前面那么洗地（体育弱国），那能给我维持住一个稳定的排名我也能接受，问题是我们的经济物质资源比 2000 年前应该有了质的变化，身体素质也越来越好，即使是体育弱国，这么继续走下坡路，半死不活的，不觉得是打了自己的脸么。足球也需要基本功，基本的体能，力量这些，看看现在这些国足运动员的体型，对比下女足，说实话，如果男足这些运动员都练得不错的体脂率，耐力等，成绩即使不好，也不会比现在更差。
纯主观吐槽，勿喷。

这里开始慢慢深入的讲一下 disruptor，首先是 lock free , 相比于前面介绍的两个阻塞队列，
disruptor 本身是不直接使用锁的，因为本身的设计是单个线程去生产，通过 cas 来维护头指针，
不直接维护尾指针，这样就减少了锁的使用，提升了性能；第二个是这次介绍的重点，
减少 false sharing 的情况，也就是常说的 伪共享 问题，那么什么叫 伪共享 呢，
这里要扯到一些 cpu 缓存的知识，

譬如我在用的这个笔记本

这里就可能看到 L2 Cache 就是针对每个核的

这里可以看到现代 CPU 的结构里，分为三级缓存，越靠近 cpu 的速度越快，存储容量越小，
而 L1 跟 L2 是 CPU 核专属的每个核都有自己的 L1 和 L2 的，其中 L1 还分为数据和指令，
像我上面的图中显示的 L1 Cache 只有 64KB 大小，其中数据 32KB，指令 32KB，
而 L2 则有 256KB，L3 有 4MB，其中的 Line Size 是我们这里比较重要的一个值，
CPU 其实会就近地从 Cache 中读取数据，碰到 Cache Miss 就再往下一级 Cache 读取，
每次读取是按照缓存行 Cache Line 读取，并且也遵循了“就近原则”，
也就是相近的数据有可能也会马上被读取，所以以行的形式读取，然而这也造成了 false sharing，
因为类似于 ArrayBlockingQueue，需要有 takeIndex , putIndex , count , 因为在同一个类中，
很有可能存在于同一个 Cache Line 中，但是这几个值会被不同的线程修改，
导致从 Cache 取出来以后立马就会被失效，所谓的就近原则也就没用了，
因为需要反复地标记 dirty 脏位，然后把 Cache 刷掉，就造成了false sharing这种情况
而在 disruptor 中则使用了填充的方式，让我的头指针能够不产生false sharing

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

class LhsPadding
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

class Value extends LhsPadding
{
    protected volatile long value;
}

class RhsPadding extends Value
{
    protected long p9, p10, p11, p12, p13, p14, p15;
}

/**
 * <p>Concurrent sequence class used for tracking the progress of
 * the ring buffer and event processors.  Support a number
 * of concurrent operations including CAS and order writes.
 *
 * <p>Also attempts to be more efficient with regards to false
 * sharing by adding padding around the volatile field.
 */
public class Sequence extends RhsPadding
{

通过代码可以看到，sequence 中其实真正有意义的是 value 字段，因为需要在多线程环境下可见也
使用了volatile 关键字，而 LhsPadding 和 RhsPadding 分别在value 前后填充了各
7 个 long 型的变量，long 型的变量在 Java 中是占用 8 bytes，这样就相当于不管怎么样，
value 都会单独使用一个缓存行，使得其不会产生 false sharing 的问题。

去年 8 月份运气比较好，摇到了车牌，本来其实应该很早就开始摇的，前面第一次换工作没注意社保断缴了一个月，也是大意失荆州，后面到了 17 年社保满两年了，好像只摇了一次，还是就没摇过，有点忘了，好像是什么原因导致那次也没摇成功，但是后面暂住证就取消了，需要居住证，居住证又要一年及以上的租房合同，并且那会买车以后也不怎么开，住的地方车位还好，但是公司车位一个月要两三千，甚至还是打车上下班比较实惠，所以也没放在心上，后面摇到房以后，也觉得应该准备起来车子，就开始办了居住证，居住证其实还可以用劳动合同，而且办起来也挺快，大概是三四月份开始摇，到 8 月份的某一天收到短信说摇到了，一开始还挺开心，不过心里抱着也不怎么开，也没怎么大放在心上，不过这里有一点就是我把那个照片直接发出去，上面有着我的身份证号，被 LD 说了一顿，以后也应该小心点，但是后面不知道是哪里看了下，说杭州上牌已经需要国六标准的车了，瞬间感觉是空欢喜了，可是有同事说是可以的，我就又打了官方的电话，结果说可以的，要先转籍，然后再做上牌。

转籍其实是很方便的，在交警 12123 App 上申请就行了，在转籍以后，需要去实地验车，验车的话，在支付宝-杭州交警生活号里进行预约，找就近的车管所就好，需要准备一些东西，首先是行驶证，机动车登记证书，身份证，居住证，还有车上需要准备的东西是要有三脚架和反光背心，反光背心是最近几个月开始要的，问过之前去验车的只需要三脚架就好了，预约好了的话建议是赶上班时间越早越好，不然过去排队时间要很久，而且人多了以后会很乱，各种插队，而且有很多都是汽车销售，一个销售带着一堆车，我们附近那个进去的小路没一会就堵满车，进去需要先排队，然后扫码，接着交资料，这两个都排着队，如果去晚了就要排很久的队，交完资料才是排队等验车，验车就是打开引擎盖，有人会帮忙拓印发动机车架号，然后验车的会各种检查一下，车里面，还有后备箱，建议车内整理干净点，后备箱不要放杂物，检验完了之后，需要把三脚架跟反光背心放在后备箱盖子上，人在旁边拍个照，然后需要把车牌遮住后再拍个车子的照片，再之后就是去把车牌卸了，这个多吐槽下，那边应该是本来那边师傅帮忙卸车牌，结果他就说是教我们拆，虽然也不算难，但是不排除师傅有在偷懒，完了之后就是把旧车牌交回去，然后需要在手机上（警察叔叔 App）提交各种资料，包括身份证，行驶证，机动车登记证书，提交了之后就等寄车牌过来了。

这里面缺失的一个环节就是选号了，选号杭州有两个方式，一种就是根据交管局定期发布的选号号段，可以自定义拼 20 个号，在手机上的交警 12123 App 上可以三个一组的形式提交，如果有没被选走的，就可以预选到这个了，但是这种就是也需要有一定策略，最新出的号段能选中的概率大一点，然后数字全是 8，6 这种的肯定会一早就被选走，然后如果跟我一样可以提前选下尾号，因为尾号数字影响限号，我比较有可能周五回家，所以得避开 5，0 的，第二种就是 50 选一跟以前新车选号一样，就不介绍了。第一种选中了以后可以在前面交还旧车牌的时候填上等着寄过来了，因为我是第一种选中的，第二种也可以在手机上选，也在可以在交还车牌的时候现场选。

总体过程其实是 LD 在各种查资料跟帮我跑来跑去，要不是 LD，估计在交管局那边我就懵逼了，各种插队，而且车子开着车子，也不能随便跑，所以建议办这个的时候有个人一起比较好。

很久之前就听说过这个框架，不过之前有点跟消息队列混起来，这个也是种队列，但不是跟 rocketmq，nsq 那种一样的，而是在进程内部提供队列服务的，偏向于取代ArrayBlockingQueue，因为这个阻塞队列是使用了锁来控制阻塞，关于并发其实有一些通用的最佳实践，就是用锁，即使是 JDK 提供的锁，也是比较耗资源的，当然这是跟不加锁的对比，同样是锁，JDK 的实现还是性能比较优秀的。常见的阻塞队列中例如 ArrayBlockingQueue 和 LinkedBlockingQueue 都有锁的身影的存在，区别在于 ArrayBlockingQueue 是一把锁，后者是两把锁，不过重点不在几把锁，这里其实是两个问题，一个是所谓的 lock free, 对于一个单生产者的 disruptor 来说，因为写入是只有一个线程的，是可以不用加锁，多生产者的时候使用的是 cas 来获取对应的写入坑位，另一个是解决“伪共享”问题，后面可以详细点分析，先介绍下使用
首先是数据源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class LongEvent {
    private long value;

    public void set(long value) {
        this.value = value;
    }

    public long getValue() {
        return value;
    }

    public void setValue(long value) {
        this.value = value;
    }
}

事件生产

1
2
3
4
5
6
7

public class LongEventFactory implements EventFactory<LongEvent>
{
    public LongEvent newInstance()
    {
        return new LongEvent();
    }
}

事件处理器

1
2
3
4
5
6
7
8
9
10
11
12

public class LongEventHandler implements EventHandler<LongEvent> {

    // event 事件，
    // sequence 当前的序列 
    // 是否当前批次最后一个数据
    public void onEvent(LongEvent event, long sequence, boolean endOfBatch)
    {
        String str = String.format("long event : %s l:%s b:%s", event.getValue(), sequence, endOfBatch);
        System.out.println(str);
    }
}

主方法代码

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
28
29
30
31
32
33
34
35
36
37
38

package disruptor;

import com.lmax.disruptor.RingBuffer;
import com.lmax.disruptor.dsl.Disruptor;
import com.lmax.disruptor.util.DaemonThreadFactory;

import java.nio.ByteBuffer;

public class LongEventMain
{
    public static void main(String[] args) throws Exception
    {
        // 这个需要是 2 的幂次，这样在定位的时候只需要位移操作，也能减少各种计算操作
        int bufferSize = 1024; 

        Disruptor<LongEvent> disruptor = 
                new Disruptor<>(LongEvent::new, bufferSize, DaemonThreadFactory.INSTANCE);

        // 类似于注册处理器
        disruptor.handleEventsWith(new LongEventHandler());
        // 或者直接用 lambda
        disruptor.handleEventsWith((event, sequence, endOfBatch) ->
                System.out.println("Event: " + event));
        // 启动我们的 disruptor
        disruptor.start(); 


        RingBuffer<LongEvent> ringBuffer = disruptor.getRingBuffer(); 
        ByteBuffer bb = ByteBuffer.allocate(8);
        for (long l = 0; true; l++)
        {
            bb.putLong(0, l);
            // 生产事件
            ringBuffer.publishEvent((event, sequence, buffer) -> event.set(buffer.getLong(0)), bb);
            Thread.sleep(1000);
        }
    }
}

运行下可以看到运行结果

这里其实就只是最简单的使用，生产者只有一个，然后也不是批量的。