Algorithm

题目

题目描述

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。703 数据流中的第K大元素

题目解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class KthLargest {

    private PriorityQueue<Integer> queue;
    private int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        queue = new PriorityQueue<>(k);
        for(int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        if(queue.size() < k) {
            queue.offer(val);
        } else if (queue.peek() < val) {
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}

Review

与程序员相关的CPU缓存知识这是左耳朵耗子的一篇微观技术分享，讲解了程序员要知道的关于CPU缓存的知识，并举例进行了说明。

CPU的缓存技术

最新的CPU有三级缓存，分别是为L1，L2，L3，其中L1与L2为每一CPU独享，L3为所有CPU共享。越靠近CPU的缓存越小。

CPU的缓存速度比较

存储名 存取速度(CPU时钟周期)
L1 4
L2 11
L3 39
RAM内存 107

CPU缓存有多大？

L1与L2基本是KB级别，L3会是MB级别，具体看CPU型号

为什么缓存设计成三层？

  1. 与CPU的晶体构造有关，通信路线越短速度越快
  2. 多核技术CPU同步，多级不同尺寸有利于提高整体性能（老的CPU架构只有两层缓存，新的为三层是不是也是因为这个？）

缓存引入了什么问题？

  1. 缓存命中问题
  2. 缓存一致性问题

缓存命中问题

CPU中的缓存中的数据是按Cache line存储的，也就是加载数据时会把相邻近的数据也一并加载，即按块加载。

Cache line有多大？

主流的Cache line大小为64 Bytes，可以存储16个32位整形数据

内存中的数据是如何加载到缓存中的？

N-Way关联，即把N个Cache Line绑成一组，查询时先找到相关组，然后再在组内找相关的Cache Line。Cache Line中前24位存Tag（即内存地址的24bits）,再后6位为所在这一Way的Cache Line索引，再后6位为在Cache Line的偏移量。查找时则先取中6位定位到Cache Line组(Set)，再最多进行N（常数）次遍历来匹配前24位的tag，找到则命中，未找到则miss。缓存未命中时，CPU加载数据时还会有预加载操作。

缓存一致性问题

缓存的写操作分为两种，一种为Write Back，理解为写Cache，后Flush到内存。另一种为Write Through，即写Cache同时写内存。很明显，第二种速度会很慢，一般会使用第一种方法。

多个CPU如何进行缓存数据同步的？

基本上为两种协议，一是Directory协议，即通过一个集中控制器来处理同步问题，缺点明显，集中控制器容易成为瓶颈。另一种为Snoopy协议，数据通知总线型，基本就是各个CPU可以识别其它CPU上的数据状态，有数据共享就广播，类似与微服务+消息通讯，但是又与我们熟知的微服务不一样，CPU中不需要考虑网络问题，CPU多核只需要考虑数据同步问题。

Snoopy协议有哪些状态？

MESI，即Modified(已修改)，Exclusive（独占），Shared（共享），Invalid（无效的）,它们的转换异常复杂，后续单拿时间来学习。

CPU缓存间也能同步数据？

可以，有一个叫MOESI的协议允许CPU Cache间同步数据，这样可以避免从内存中读。

示例都说明了什么问题？

  1. 示例一说明了表面上看代码少执行了次数，但是具体操作时间相差不多，主要是因为缓存是Cache Line的。
  2. 示例二说明了超大步长对于CPU的性能影响，主要是由于CPU的存储数据方式，步长超过1024后，内存地址只在高24位变化，而中间的6bits没有变化，导致都命中同一组Set，Cache冲突。
  3. 示例三说明了行遍历与列遍历的性能差距，相差十几倍，列遍历对CPU是不友好的。
  4. 示例四说明了多CPU的缓存同步问题，两个不相关的数据因为在同一Cache line上而相互同步。
  5. 示例五说明了多CPU执行时的数组数据读取问题，由于Cache Line问题，多个CPU都要写同一Cache Line，导致不断重新同步数据。

总结

使用数组写程序时要多考虑CPU缓存友好性问题，写多线程的程序时要考虑避免潜在的多个CPU间缓存数据(Cache Line)同步问题。

Tip

Org文档格式的问题，可以使用两种方法达到效果。

  1. 在Org文档上加上#+STARTUP: indent来告诉Org Mode在打开文件时进行格式化，缺点明显，Org File过大，需要格式时间长。
  2. 使用org-indent-indent-buffer命令来进行格式化。方便灵活，缺点就是要多执行一下。

Share

常见集合容器应当避免的坑文章说明了在开发中常用的ArrayList使用的一些坑，大数据量下的add操作时要先对List进行指定大小初始化，不然List会进行频繁的扩容操作，影响性能。还有要少用add(int index, E element)的方法，因为每次调用这个方法都会触发底层的数据拷贝。对于集合的类的操作，在能预知数据量的情况下，都要进行初始化长度。