Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

发表于 分类于 ， 阅读次数： Disqus：

题目介绍

给定两个数组 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;
    }

发表于 分类于 ， 阅读次数： Disqus：

上次本来想在换车牌后面聊下这个话题，为啥要聊这个话题呢，也很简单，在地铁上看到一对猜测是情侣或者比较关系好的男女同学在聊，因为是这位男同学是大学学的工科，然后自己爱好设计绘画相关的，可能还以此赚了点钱，在地铁上讨论男的要不要好好努力把大学课程完成好，大致的观点是没必要，本来就不适合，这一段我就不说了，恋爱人的嘴，信你个鬼。
后面男的说在家里又跟他爹吵了关于男足的，估计是那次输了越南，实话说我不是个足球迷，对各方面技术相关也不熟，只是对包括这个人的解释和网上一些观点的看法，纯主观，这次地铁上这位说的大概意思是足球这个训练什么的很难的，要想赢越南也很难的，不是我们能嘴炮的；在网上看到一个赞同数很多的一个回答，说什么中国是个体育弱国，但是由于有一些乒乓球，跳水等小众项目比较厉害，让民众给误解了，首先我先来反驳下这个偷换概念的观点，第一所谓的体育弱国，跟我们觉得足球不应该这么差没半毛钱关系，因为体育弱国，我们的足球本来就不是顶尖的，也并不是去跟顶尖的球队去争，以足球为例，跟巴西，阿根廷，英国，德国，西班牙，意大利，法国这些足球强国，去比较，我相信没有一个足球迷会这么去做对比，因为我们足球历史最高排名是 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 年前应该有了质的变化，身体素质也越来越好，即使是体育弱国，这么继续走下坡路，半死不活的，不觉得是打了自己的脸么。足球也需要基本功，基本的体能，力量这些，看看现在这些国足运动员的体型，对比下女足，说实话，如果男足这些运动员都练得不错的体脂率，耐力等，成绩即使不好，也不会比现在更差。
纯主观吐槽，勿喷。

发表于 更新于 分类于 阅读次数： Disqus：

这里开始慢慢深入的讲一下 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 的问题。

0%