yield-bytes

沉淀、分享与无限进步

发表于 更新于 分类于
本文字数： 10k 阅读时长 ≈ 9 分钟

使用场景

ArrayList并发读写不安全示例:

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
39
40
41
42
43
44
import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class ArrayListDemo {
    public static void main(String[] args) throws InterruptedException {
//        CopyOnWriteArrayList<String> list= new CopyOnWriteArrayList<>(Arrays.asList("foo","bar"));
        ArrayList<String> list= new ArrayList<>(Arrays.asList("foo","bar"));
        ArrayList<Thread> writeTreadList=new ArrayList<>();
        ArrayList<Thread> readTreadList=new ArrayList<>();
        int threadNum=10;
        ExecutorService service= Executors.newFixedThreadPool(threadNum);
        for(int i=0;i<threadNum;i++){
            service.execute(new Writer(list));
            service.execute(new Reader(list));
        }
        service.shutdown();
    }
}

class Writer implements Runnable{
    List<String> list;

    public Writer(List<String> list){
        this.list=list;
    }
    @Override
    public void run() {
        this.list.add("writer");
    }
}

class Reader implements Runnable{
    List<String> list;
    public Reader(List<String> list){
        this.list=list;
    }
    @Override
    public void run() {
        System.out.println(Thread.currentThread().getName()+":"+list);
    }
}

提示ConcurrentModificationException：并发修改异常。这是因为有写线程和读线程同时操作list因为有写线程添加元素后，会改动modCount，导致某个读线程在读之前拿到的expectedModCount不等于正在读过程中modCount，故会在next()方法抛出异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
pool-1-thread-4:[foo, bar, writer, writer]
pool-1-thread-7:[foo, bar, writer, writer, writer]
pool-1-thread-9:[foo, bar, writer, writer, writer, writer]
pool-1-thread-11:[foo, bar, writer, writer, writer, writer, writer]
pool-1-thread-11:[foo, bar, writer, writer, writer, writer, writer, writer]
pool-1-thread-11:[foo, bar, writer, writer, writer, writer, writer, writer, writer]
pool-1-thread-11:[foo, bar, writer, writer, writer, writer, writer, writer, writer, writer]
pool-1-thread-11:[foo, bar, writer, writer, writer, writer, writer, writer, writer, writer, writer]
pool-1-thread-11:[foo, bar, writer, writer, writer, writer, writer, writer, writer, writer, writer, writer]
Exception in thread "pool-1-thread-2" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at java.util.AbstractCollection.toString(AbstractCollection.java:461)
	at java.lang.String.valueOf(String.java:2994)
	at java.lang.StringBuilder.append(StringBuilder.java:131)
	at concurrent.demo.Reader.run(ArrayListDemo.java:43)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
	at java.lang.Thread.run(Thread.java:748)

将ArrayList换成CopyOnWriteArrayList即可正常运行，因为CopyOnWriteArrayList 允许并发的读写操作，写操作不会影响到读操作，这就是所谓的读写分离设计。

阅读全文 »

发表于 更新于 分类于
本文字数： 19k 阅读时长 ≈ 18 分钟
成员变量以及节点定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
transient int size = 0;

/**
 * Pointer to first node.
 等效判断一定是头节点的类型： first为空且last为空，那么肯定是头节点，或者first的前驱节点为空且first节点内容不为空
 * Invariant: (first == null && last == null) || // 空头节点
 *            (first.prev == null && first.item != null) // 非空头节点
 */
transient Node<E> first;

/**
 * Pointer to last node.
 //同上
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;
阅读全文 »

发表于 更新于 分类于
本文字数： 22k 阅读时长 ≈ 20 分钟
成员变量

空参构造非常简单，它会为我们创建一个空的集合。elementData成员变量是用来存放数据的对象,是一个Object[]，DEFAULTCAPACITY_EMPTY_ELEMENTDATA则是一个空的数组。

1
2
3
4
5
6
/**
　* Constructs an empty list with an initial capacity of ten.
　*/
public ArrayList() {
　　this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

空参构造非常简单，它会为我们创建一个空的集合。elementData成员变量是用来存放数据的对象,是一个Object[]，DEFAULTCAPACITY_EMPTY_ELEMENTDATA则是一个空的数组。注意DEFAULTCAPACITY_EMPTY_ELEMENTDATA类型为static final，表明其在内存中只有一份且禁止修改。

1
2
3
4
5
　* Shared empty array instance used for default sized empty instances. We
　* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
　* first element is added.
　*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

注意elementData使用transient修饰。表明在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。而ArrayList类实现了java.io.Serializable接口，即采用了Java默认的序列化机制。但是elementData在网络传输的时候不序列化肯定是不行的，翻看源码会发现ArrayList自己实现了序列化和反序列化的方法。

1
transient Object[] elementData; // non-private to simplify nested class access
阅读全文 »

发表于 更新于 分类于
本文字数： 30k 阅读时长 ≈ 27 分钟

在前面的《jdk1.8的HashMap源码分析》文章已经给出HashMap中数组+链表这一部分的内容，本篇文章将剩余的HashMap里面红黑树及其相关操作源码进行解析，内容较多，因此单独放在一篇文章进行讨论。

一、背景知识

由于红黑树的插入、删除、扩容等操作相对复杂，因此建议先熟悉基本数据结构，例如二叉树、二叉搜索树及其关于它的查找、插入、删除操作、2-3节点树等。

本人假定看此文章的同学已经具备基本的数据结构知识，因此，关于红黑树的背景知识，这里不再累赘。

冷知识：红黑树为什么叫红黑？节点为什么被标记为红色和黑色， 可以改为蓝黄树、绿蓝树等吗？

首先红黑树第一版在1972年由Rudolf Bayer发明，当时的学名是平衡二叉B树（symmetric binary B-trees），还不是被称为Red Black Trees。后来平衡二叉B树在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为现在版本的红黑树，他们之所以称之为“红黑”树，因为他们在研究这种树型数据结构过程中，需要在草稿纸上作图，用的恰是红色笔和黑色笔，红黑笔非常方便给相关节点标记颜色以便可视化设计相关逻辑，因此“红黑树”的红黑来源于此。

二、红黑树性质：

以下5个性质结合基于序列3，7，11，15，19，23，27，31，35，构成的一棵红黑树进行理解（这里给出的是有序序列，其实即使原序列是无序的， 被重构成为红黑树后，在红黑树也会形成二叉树搜索树的有序序列）

  • 1、树上的所有节点都被标记颜色，节点可以被标记位黑色，也可以被标记为红色，

32

  • 2、root根节点必须被标记为黑色

  • 3、所有的叶子节点都被标记为黑色，而且是NIL节点（需要注意：在JDK1.8的HashMap中，没有NIL命名的节点，也不是所谓的用null来表示NIL节点，在分析原理上可以将其当做虚构的null节点来对待，不影响结构，在平常作图中，NIL叶子节点可以忽略，在这里只是为了说明红黑树有NIL这种设计，因此在图中显式画出）

33

  • 4、每个被标记为红色的节点，它的两子节点一定都是黑色

35

第4点也可以推出这样的结论：两个红节点一定不会直接相连，也即：红色节点与红色节点不能直接连接，或者说，红色节点的父节点及其子节点都不能是红色节点

36

  • 5、任一节点到每个叶子结点的路径都包含数量相等的黑色节点，俗称：黑色平衡或者黑高，BlackHeight，如 下图的5条路径，每条路径经过黑色节点数都是2，NIL节点不作为黑色节点计数。

37

阅读全文 »

发表于 更新于 分类于
本文字数： 8.1k 阅读时长 ≈ 7 分钟

  本文的使用场景相对常见，例如需要解析一份含几千上万行Excel表（或者长报告里需要插入表格数据），需要将某列的一个单元格长字符串对应展开为多行且索引号不变，或者groupby后将同组的多行值拼接为单个长字符串，使用pandas可以快速完成。（文章由jupyter notebook导出的Markdown文件生成）

groupby后将同组的多行值连接为一个长字符串

使用df.groupby、apply、pd.merge

（在mysql中可以直接使用GROUP_CONCAT(字段 SEPARATOR ‘、’)方法完成）

1
2
3
4
5
6
7
import pandas as pd
data={
    '省份':['上海','广东','上海','广东','上海'],
    '大学名称':['复旦大学','中山大学','同济大学','华南理工大学','上海交通大学']
}
df=pd.DataFrame(data)
df
阅读全文 »

发表于 更新于 分类于
本文字数： 34k 阅读时长 ≈ 31 分钟

jdk1.8的HashMap应该JSR-166 Java专家组（HashMap主要还是Dung Lea做了大量贡献）设计的一个极其出色且优秀的数据结构，无论是算法设计和程序代码设计都显得非常高水平，个人深入分析后，获益匪浅！

一、HashMap底层结构图以及基本术语

在这里插入图片描述

​ 这张结构图清晰展示HashMap由一维数组+链表+红黑树构成，数组在源码命名为table，是一个Node[]泛型类型数组，table数组上的每个元素或者为null或者为单个node或者冲突链头节点或者为treeNode。桶位上可能形成冲突链表，红黑树tree bins是由node链表树化而来。

阅读全文 »

发表于 更新于 分类于
本文字数： 15k 阅读时长 ≈ 13 分钟

  本blog用于归档如何在GitHub搭建个人博客的过程，内容参考来自本篇文章《如何用 GitHub 从零开始搭建一个博客》 以及hexo中文官网的文档。

更新：这篇文章写于今年年初，个人博客在年初已使用GitHub Pages搭建开源博客主页，今年下半年GitHub Pages在国内出现了某一时期无法正常访问，因此将其切换到国内Gitee Pages以保证主页正常访问，确实也需支持国内开源平台。

在这里插入图片描述

阅读全文 »

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

  本文内容主要给出基于PySpark程序，整合Spark Streaming和Kafka，实现实时消费和处理topic消息，为PySpark开发大数据实时计算项目提供基本参考。

1 程序环境准备：

  这里不再使用Spark的集群环境，因涉及的计算资源测试环境受限，目前两台虚拟机：1个vcore+2G内存，其中一台虚拟机启动Spark Streaming服务进程，另外一台虚拟机启动kafka进程。

  • 虚拟机A：启动单实例kafka服务
  • 虚拟机B：运行PySpark程序

  在VM A，程序环境要求安装jdk1.8以上以及与kafka匹配版本的scala版本
版本兼容说明：

1
2
3
kafka：kafka_2.11-2.4.0
java：java version "1.8.0_11"
scala： Scala 2.12.0

  这里需要注意：如果使用kafka_2.12版本以上，需要使用jdk1.8.0_212以上；kafka_2.12与jdk1.8.0_11有不兼容地方，kafka启动报错提示java.lang.VerifyError: Uninitialized object exists on backward branch 209。

阅读全文 »

发表于 更新于 分类于
本文字数： 31k 阅读时长 ≈ 28 分钟

  在前面两篇文章《gevent与协程》和《asyncio与协程》，讨论了有关协程异步编程方面的内容，从代码层面和基本的demo可以大致理解协程的工作方式。如果要深入理解为何单线程基于事件的驱动可以在“低能耗”的条件下达到高性能的IO服务，则要研究Linux底层实现原理——IO多路复用，而理解IO多路复用的前提是对文件描述符有较为深入的理解，因此本文把文件描述符和IO多路复用放在同一篇文章里，形成全局的体系化认知，这就是本文讨论的内容。

阅读全文 »