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)的方法,因为每次调用这个方法都会触发底层的数据拷贝。对于集合的类的操作,在能预知数据量的情况下,都要进行初始化长度。