Noob

Bert

发表于 2019-12-10 更新于 2019-12-30 分类于 AI ， NLP

目前大部分 NLP 任务深度学习任务中都会使用预训练好的词向量（Word2Vec等）进行网络初始化（而非随机初始化），从而加快网络的收敛速度。预训练词向量通常只编码词汇之间的关系，对上下文信息考虑不足，并且无法处理一词多义问题。如 bank 既可以表示银行，也可以表示岸边，却对应相同的词向量，这显然是不合理的。为了更好地考虑词上下文信息，Context2Vec 使用两个双向长短时记忆网络（Long Short Term Memory， LSTM）来分别编码单词左到右（Left to right），右到左（right to left）的上下文信息。这种使用预训练语言模型的词向量作为特征输入到下游目标任务的方法称为 feature-based。

另一种方法是微调（Fine-tuning），GPT、BERT 和后续预训练工作都属于这一范畴，直接在深层 Transformer 网络上进行语言模型训练，收敛后针对下游目标进行微调，不需要再为目标任务设计 Task-specific 网络重头训练。

BERT（Bidirectional Encoder Representations from Transformers）是基于 Transformer 的深度双向语言表征模型，本质上利用 Transformer 结构构造了一个多层双向的 Encoder 网络。Transformer 是 Google 2017 年提出的基于自注意力机制（self-attention）的深层模型，在包括机器翻译在内的多项 NLP 任务上效果显著，超过 RNN 且训练速度更快。不到一年时间内，Transformer已经取代RNN成为神经网络机器翻译的State-Of-The-Art（SOTA）模型。

输入表示

针对不同的任务，BERT模型的输入可以是单句或者句对。对于每一个输入的Token，它的表征由其对应的词表征（Token Embedding）、段表征（Segment Embedding）和位置表征（Position Embedding）相加产生。

对于英文模型，使用了Wordpiece模型来产生Subword从而减小词表规模；对于中文模型，直接训练基于字的模型。
模型输入需要附加一个起始Token，记为[CLS]，对应最终的Hidden State（即Transformer的输出）可以用来表征整个句子，用于下游的分类任务。
模型能够处理句间关系。为区别两个句子，用一个特殊标记符[SEP]进行分隔，另外针对不同的句子，将学习到的Segment Embeddings 加到每个Token的Embedding上。
对于单句输入，只有一种Segment Embedding；对于句对输入，会有两种Segment Embedding。

参考资料

阅读全文 »

数据库设计

发表于 2019-11-27 分类于存储， RDBMS

数据库设计三范式

第一范式（1NF）：原子性，数据不可再分，表中每一列不可再分

第二范式（2NF）：唯一性，消除部分依赖，每行数据具有唯一性。在第一范式基础上，每个表必须有主键，并且没有包含在主键中的列完全依赖主键，而不能部分依赖主键。如果存在部分依赖，这些属性和关键字应该分离出来形成一个新的实体。不满足第二范式的设计容易产生冗余数据。

第三范式（3NF）：独立性，消除传递依赖。在满足第二范式的基础上，非主键列必须直接依赖主键，不能存在传递依赖。

区分第二范式还是第三范式：2NF非主键列是完全依赖主键还是依赖主键的一部分，3NF 非主键列是直接依赖主键还是直接依赖非主键列。

参考文档

1.数据库（第一范式，第二范式，第三范式）

阅读全文 »

问题整理

发表于 2019-11-26 更新于 2020-01-02

什么是僵死进程，什么时候出现

子进程退出时，父进程没有对子进程发出的 SIGCHLD 信号进行适当处理（waitpid或忽略），导致子进程停留在僵死状态等待父进程收尸，这种状态下的子进程称为僵死进程。

如果进程父进程不调用 wait / waitpid，那么保留的子进程信息（进程号，退出状态，运行时间等）不会释放，进程号会一致占用。由于系统的进程号是有限的，如果产生大量僵死进程，可能出现没有可用进程号，导致系统无法创建新的进程。

如何清除：

①改写父进程，

②把父进程杀掉，僵死进程成为孤儿进程，过继给 1 号进程 init，init 始终会负责清理僵死进程

什么是孤儿进程

父进程退出后，它的子进程还在运行，这些子进程将成为孤儿进程。孤儿进程将被 init 进程（进程 id 为 1）收养，并由 init 进程对它们进程状态收集工作。

阅读全文 »

衡量指标

发表于 2019-11-01 更新于 2020-05-16 分类于 AI

准确率

TP / (TP + FP)

召回率

TP / (TP + FN)

P-R 曲线

将样本按照是正例的概率排序，概率越大的样本排在最前面。将样本逐个加入正例集合计算准确率和召回率，并以准确率为纵轴，召回率为横轴，绘制曲线图即可得到 P-R 曲线。

ROC（受试者工作特征，Receiver Operating Characteristic）曲线的纵轴是真正例率（True Positive Rate，TPR），横轴是假正例率（False Positive Rate，FPR）

TPR = TP / (TP + FN)

FPR = FP / (FP + TN)

如果一个学习器的 ROC 曲线被另一个学习器 ROC 曲线完全包住，那么后者的性能优于前者，如果两个 ROC 曲线发生交叉，可以通过 AUC（Area Under ROC Curve）来比较。

阅读全文 »

Dubbo原理

发表于 2019-10-22 更新于 2020-05-16 分类于分布式， Dubbo

RPC（Remote Procedure Cll）远程过程调用是从一台机器（客户端）上通过参数传递的方式调用另一台机器（服务器）上的一个函数或方法并得到返回结果。

备注：本文源码分析基于dubbo-2.6.4

总体架构

请求流程

服务消费者（client 客户端）以调用本地服务的方式调用需要消费的服务
客户端存根（client stub）接收到调用请求后负责将方法、入参等信息序列化成能够进行网络传输的消息体
客户端存根（client stub）找到远程服务地址，将消息通过网络发送给服务端
服务端存根（server stub）收到消息后进行解码（反序列化）
服务端存根（server stub）根据解码结果调用本地服务进行相关处理（解码后请求转发给分发器 Dispatcher，Dispatcher 将请求派发到指定线程池）
本地服务执行具体业务逻辑将处理结果返回给服务端存根（server stub）
服务端存根（server stub）将返回结果打包成消息（序列化）并通过网络发送给消费方
客户端存根（client stub）接收到消息，进行反序列化
服务消费方得到最终结果（根据调用编号从 ConcurrentHashMap 中移除 DefaultFuture 对象并唤醒用户线程（signal/await））

Dubbo 支持同步和异步两种调用方式，其中异步调用还可以细分为有返回值和无返回值两种。无返回值时，服务消费方只管调用不关心调用结果，Dubbo 返回一个空的 RpcResult。默认为同步方式。

Dubbo 实现同步和异步调用（DubboInvoker.doInvoke()）关键点在于由谁调用 ResponseFuture 的 get 方法，同步调用模式下，由框架自身调用 FeatureResponse 的 get 方法。异步调用模式下，由用户调用该方法。

源码解析

网络通信

阅读全文 »

Java并发面试题整理

发表于 2019-10-17 更新于 2019-12-20 分类于 Java ，并发

背景知识

CPU 指令：CPU 的一些指令是非常危险的，误用可能导致严重后果，如清理内存、设置时钟等。Intel 将 CPU 指令分为4 个级别，RING0,RING1,RING2,RING3。Linux 使用 RING3级别运行用户态，RING0运行内核态。RING3 不能访问 RING0 的RING0 的地址空间，包括代码和数据。当用户态程序要执行文件操作、发送数据等操作时，需要通过 write、send 等系统调用，这些系统调用会调用内核中的代码来完成操作，必须切换到 RING0，完成后切换回 RING3，这样用户态程序就不能随意操作内核地址空间，有一定的安全保护作用。

从用户态到内核态有两种触发手段：

用户空间的应用程序通过提醒调用进入内核空间，用户空间进程将参数传递给内核，内核空间运行时也需要保存用户进程的寄存器、变量等。“进程上下文”可以看做用户进程传递给内核的参数、内核要保存的变量、寄存器和当时的环境等。
硬件通过触发信号，导致内核调用中断处理程序，进入内核空间。硬件的变量和参数也要传递给内核，内核通过这些参数进行中断处理。“中断上下文”可以看做硬件传递过来的参数和内核需要保存的环境。

Synchronized

synchronized 同步语句块的实现使用的是 monitorenter 和 monitorexit 指令，其中 monitorenter 指令指向同步代码块的开始位置，monitorexit 指令则指明同步代码块的结束位置。当执行 monitorenter 指令时，线程试图获取锁也就是获取 monitor(monitor对象存在于每个Java对象的对象头中，synchronized 锁便是通过这种方式获取锁的，也是为什么Java中任意对象可以作为锁的原因) 的持有权。当计数器为0则可以成功获取，获取后将锁计数器设为1也就是加1。相应的在执行 monitorexit 指令后，将锁计数器设为0，表明锁被释放。如果获取对象锁失败，那当前线程就要阻塞等待，直到锁被另外一个线程释放为止。

synchronized 同步方法比普通方法多了 ACC_SYNCHRONIZED 标识，JVM 根据这个标识实现同步。调用方法时先检查是否有 ACC_SYNCHRONIZED标识，有的话线程先获取 monitor，获取成功才继续执行方法，方法执行完成后线程再释放 monitor，同一个 monitor 同一时刻只能被一个线程拥有。

两种方式都通过 monitor 来实现同步，monitor 的实现依赖底层操作系统的 mutex 互斥原语，操作系统实现线程之间的切换需要从用户态转到内核态，切换成本较大。

wait、notify 和 notifyAll 也依赖于 monitor 对象来完成的，所以要在同步方法或同步代码块中调用的原因（需要先获取对象的锁，才能执行）否则抛出 IllegalMonitorStateException 异常。

jdk1.6之后 synchronized 优化

阅读全文 »

Java并发面试题整理

发表于 2019-10-12 更新于 2019-12-03 分类于 Java ，并发

AQS 全称 AbstractQueuedSynchronizer，是 java.util.concurrent.locks 包下面的一个类。用来构建锁和同步器的框架，使用 AQS 能简单而高效地构造出应用广泛的大量同步器，如ReentrantLock，Semaphore，ReentrantrantReadWriteLock，SynchronousQueue，FutureTask 等。开发者也可以利用 AQS 构造出符合要求的同步器。

AQS 的核心思想是，如果被请求的共享资源空闲，则将当前请求资源的线程设置为有效的工作线程，并将共享资源设置为锁定状态。如果被请求的共享资源被占用，就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制 AQS 是用 CLH 队列锁实现的，即将暂时获取不到锁的线程加入到队列中。

CLH（Craig，Landin， and Hagersten）队列是一个虚拟的是双向队列（虚拟的双向队列即不存在队列实例，仅存在节点之间的关联关系）。AQS 是将每条共享资源的线程封装成一个 CLH 锁队列的一个结点（Node）来实现锁的分配。

AQS 使用一个 int 成员变量来表示同步状态，通过内置的 FIFO 队列来完成获取资源线程的排队工作。使用 CAS 对该同步状态进行原子操作实现对其值的修改。

共享方式

Exclusive（独占）只有一个线程能执行，如 ReentrantLock。独占锁又分为公平锁和非公平锁。公平锁按照线程在队列中的排队顺序，先到者先获取锁；非公平锁在线程需要获取锁时，无视队列顺序直接去抢锁，谁抢到算谁的。
Share（共享）：多个线程可同时执行，如 Semaphore、CountDownLatch、CyclicBarrier、ReadWriteLock

实现原理

同步器设计基于模板模式，自定义同步器一般的方式为：

继承 AbstractQueuedSynchronizer 并重写指定方法，这些方法是对共享资源 state 的获取和释放
将 AQS 组合在自定义同步组件的实现中，并调用其它模板方法，这些模板方法会调用使用者重写的方法

AQS 使用模板方法模式，自定义同步器时重写以下几个 AQS 提供的模板方法：

阅读全文 »

生产者消费者问题

发表于 2019-09-24 更新于 2019-10-16 分类于 Java ，并发

生产者消费者问题中，生产者生产数据，消费者消费数据。为了解藕生产者和消费者的关系，通常会采用共享的数据区域，生产者生产数据后直接放在共享数据区，不需要关心消费者的行为；消费者只需要从共享区中获取数据，不需要关心生产者的行为。共享数据区应具备线程间并发协作的能力：

如果共享数据区已满，阻塞生产者继续生产数据放置到数据区
如果共享数据区为空，阻塞消费者继续消费数据

实现生产者消费者问题可以采用三种方法：

用Object的wait/notify消息通知机制
用Lock的Condition的wait/signal消息通知机制
用BlockingQueue实现

wait/notify实现

public static void main(String[] args) {
        ExecutorService executor = new ThreadPoolExecutor(8, 8, 300,
                TimeUnit.MILLISECONDS, new ArrayBlockingQueue<Runnable>(8), new ThreadPoolExecutor.DiscardPolicy());
        List<String> list = new ArrayList<String>();
        for(int i = 0; i < 4; ++i) {
            executor.submit(new Consumer(list));
        }
        for(int i = 0; i < 4; ++i) {
            executor.submit(new Producer(list, 10));
        }
        while(!executor.isTerminated()) {
            ;
        }
    }

    static class Producer implements Runnable {
        private List<String> list;
        private int maxLength;
        public Producer(List<String> list, int maxLength) {
            this.list = list;
            this.maxLength = maxLength;
        }

        @Override
        public void run() {
            while(true) {
                try {
                    synchronized(list) {
                        while(list.size() > maxLength) {
                            list.wait();
                        }
                        list.add(Thread.currentThread().getName());
                        list.notifyAll();
                    }
                } catch(InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    static class Consumer implements Runnable {
        private List<String> list;

        public Consumer(List<String> list) {
            this.list = list;
        }

        @Override
        public void run() {
            while (true) {
                try {
                    synchronized (list) {
                        while (list.isEmpty()) {
                            list.wait();
                        }
                        System.out.println(list.remove(0));
                        list.notifyAll();
                    }
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

Lock/Condition实现

@Test
public void testProducerConsumer() {
        List<String> list = Lists.newArrayList();
        ReentrantLock lock = new ReentrantLock();
        Condition full = lock.newCondition();
        Condition empty = lock.newCondition();

        ExecutorService executor = new ThreadPoolExecutor(8, 8, 30, TimeUnit.MILLISECONDS,
                new ArrayBlockingQueue<Runnable>(1), new ThreadPoolExecutor.DiscardPolicy());
        for (int i = 0; i < 4; ++i) {
            executor.submit(new Producer(list, 100, lock, full, empty));
        }
        for (int i = 0; i < 4; ++i) {
            executor.submit(new Consumer(list, lock, full, empty));
        }
        while (!executor.isTerminated()) {
            ;
        }
    }

private static class Consumer implements Runnable {
        private List<String> list;
        private Lock lock;
        private Condition full;
        private Condition empty;

        public Consumer(List<String> list, Lock lock, Condition full, Condition empty) {
            this.list = list;
            this.lock = lock;
            this.full = full;
            this.empty = empty;
        }

        @Override
        public void run() {
            while (true) {
                try {
                    lock.lock();
                    while (list.isEmpty()) {
                        empty.await();
                    }
                    String element = list.remove(0);
                    System.out.println(element);
                    full.signalAll();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    lock.unlock();
                }
            }
        }
    }

    private static class Producer implements Runnable {
        private List<String> list;
        private Integer maxLength;
        private Random random;
        private Lock lock;
        private Condition full;
        private Condition empty;

        public Producer(List<String> list, int maxLength, Lock lock, Condition full, Condition empty) {
            this.list = list;
            this.lock = lock;
            this.maxLength = maxLength;
            this.random = new Random(System.currentTimeMillis());
            this.full = full;
            this.empty = empty;
        }

        @Override
        public void run() {
            while (true) {
                try {
                    lock.lock();
                    while (list.size() >= maxLength) {
                        full.await();
                    }
                    double d = random.nextGaussian();
                    list.add(Thread.currentThread().getName() + " " + d);
                    empty.signalAll();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } finally {
                    lock.unlock();
                }
            }
        }
    }

BlockingQueue

@Test
    public void testProducerConsumer() {
        BlockingQueue<String> queue = new ArrayBlockingQueue<String>(100);
        ExecutorService executor = new ThreadPoolExecutor(8, 8, 300, TimeUnit.MILLISECONDS,
                new ArrayBlockingQueue<Runnable>(10), new ThreadPoolExecutor.AbortPolicy());
        for (int i = 0; i < 4; ++i) {
            executor.submit(new Producer(queue));
        }
        for (int i = 0; i < 4; ++i) {
            executor.submit(new Consumer(queue));
        }
        while (!executor.isTerminated()) {
            ;
        }
    }


    private static class Producer implements Runnable {
        private BlockingQueue<String> queue;

        public Producer(BlockingQueue<String> queue) {
            this.queue = queue;
        }

        @Override
        public void run() {
            while (true) {
                queue.offer(Thread.currentThread().getName());
            }
        }
    }

    private static class Consumer implements Runnable {
        private BlockingQueue<String> queue;

        public Consumer(BlockingQueue<String> queue) {
            this.queue = queue;
        }

        @Override
        public void run() {
            while (true) {
                String s = queue.poll();
                System.out.println(s);
            }
        }
    }

阅读全文 »

Skiplist

发表于 2019-09-18 分类于算法，跳表

跳跃表是链表的一种变形，具有二分查找的功能。跳跃表的每一层都是一条有序的链表，查找次数近似于层数，时间复杂度为O(logn)，插入、删除也为O(logn)。最底层的链表包含所有元素，它是一种随机化的数据结构（通过抛硬币来决定层数），空间复杂度为 O(n)

红黑树插入、删除节点时，通过调整结构来保持红黑树的平衡，比起跳跃表直接通过一个随机数来决定跨越几层，在时间复杂度的花销高于跳跃表。

阅读全文 »

晋升大纲

发表于 2019-09-17

排队金刚位

阅读全文 »