LeetCode 1103:Distribute Candies to People

本文为LeetCode 1103:Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果:

我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。

然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。

这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组(长度为num_people),该数组表示最终每个人得到的糖果数量。

题解

首先我们考虑能完整的分发几轮。

由于分发数量总体上就是从1到n*num_people的等差序列,n符合如下不等式:

阅读更多

LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树,每个节点都编号(label)了:对于奇数层(第1、3、5等层),从左向右编号。对于偶数层,从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1

如图:

给你一个编号(label),输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

阅读更多

yum仓库内部原理

本文是yum repository internals的翻译。

TL;DR

这篇博客将会检查各种yum仓库中的索引文件,从而深入了解yum仓库的细节。我们将介绍每个索引文件的含义,并研究用户如何检查这些元数据。

什么是yum仓库?

Yum仓库就是一些RPM包的集合,加上一些yum命令能够读取的元数据。有一个yum仓库能够让你安装、删除、升级软件包或者软件组。

yum仓库对于存储、管理、交付软件非常重要。

使用createrepo命令创建一个yum仓库

在详细了解yum仓库元数据之前,先让我们看看如何用开源命令行工具createrepo架设一个yum仓库。

使用命令行工具createrepo,你能创建一个yum仓库。你能在CentOS或Red Hat系统中使用如下命令安装这个工具:

$ sudo yum install createrepo

阅读更多

PHP Generator相关的设计失误

PHP的Generator,也就是 yield/yield from 语法,使得函数调用可以“暂停”执行,并保留上下文,并在后续可以恢复执行。

但是,在PHP后续的设计中,很多地方都没有考虑到Generator:

Return Type Declarations(返回类型声明)

RFC见https://wiki.php.net/rfc/return_types。简而言之,可以给函数声明返回类型。先来看一段代码:

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
<?php
declare(strict_types=1);

function inner(): Iterator
{
yield __FUNCTION__;
return 1;
}

function gen(): Generator
{
yield __FUNCTION__;
return yield from inner();
}

try {
$gen = gen();
foreach ($gen as $yielded) {
echo "yield: ".$yielded . PHP_EOL;
}
echo "return: " . $gen->getReturn() . PHP_EOL;
} catch (Exception $e) {
echo PHP_EOL;
echo $e->getTraceAsString();
echo PHP_EOL;
}

gen/inner函数是一个generator,yield的的类型是string,return的类型是int。但为了让PHP不报错,gen/inner函数的返回类型只能声明为Iterator或Generator——这完全破坏了返回类型声明的初衷:

对于普通函数,返回类型声明用来表示返回类型;对于generator,返回类型声明用来表示这是一个迭代器/Generator。(听着很不一致的样子)

好,没关系,无伤大雅。没法通过返回类型声明来推倒类型而已,我们通过PhpDoc来总可以了吧?

通过PhpDoc来标记返回类型

但是这个怎么写呢?对于刚刚的inner函数(yield的的类型是string,return的类型是int),最自然的写法是这样:

阅读更多

Java中的SPI机制

SPI 全称为 (Service Provider Interface) ,是Java 1.6之后内置的一种服务提供发现机制。SPI可以通过配置来替换服务(或者说interface)的实现;比如java.sql.Driver接口,可以很轻松的从MySQL切换到MongoDB实现。

问题的核心在于,如何根据interface查找对应的实现。

SPI的实现

Java 1.6中,开发者只需要在META-INF/services下添加文件,即可切换、修改对应interface的实现。文件名为实现的接口,文件内容为N个实现的类名,按行分隔。比如:

1
2
3
$ cat src/main/resources/META-INF/services/com.robberphex.Plugin 
com.robberphex.impl.PluginImpl1
com.robberphex.impl.PluginImpl2

使用起来,主要就是ServiceLoader类

1
2
3
4
ServiceLoader<Plugin> loader = ServiceLoader.load(Plugin.class);
for (Plugin plugin : loader) {
System.out.println(plugin.getClass().getCanonicalName());
}

要注意的是,ServiceLoader#load方法是CallerSensitive的,即load的时候用的是调用者的类加载器。

Java 9

Java 9之后,由于模块化的引入,所以SPI机制也做了扩展:除了原有的通过META-INF/services来注册服务外,还可以通过module中的provides…with语句来注册服务:

阅读更多

Java的类/实例初始化过程

昨天看到群里面有人分享了一道题目,我答错了,于是趁机了解了下Java的类/对象初始化过程:

程序的输出见文章最后。

程序A主要考察的是类实例初始化。简单验证了下,类实例初始化过程如下:

  • 父类实例初始化
  • 构造块/变量初始化(按照文本顺序执行)
  • 构造函数

程序B考察的则是类初始化。类初始化的过程如下:

  • 父类初始化
  • static变量初始化/static块(按照文本顺序执行)

但是我们必须做到面向接口编程,而不是面向实现编程(Program to an ‘interface’, not an ‘implementation’)。

于是就得看看Java Language Specification是如何规定的。其中类初始化过程如下:

  1. 每个类都有一个初始化锁LC,进程获取LC(如果没有获取到,就一直等待)
  2. 如果C正在被其他线程初始化,释放LC并等待C初始化完成
  3. 如果C正在被本线程初始化,即_递归初始化_,释放LC
  4. 如果C已经被初始化了,释放LC
  5. 如果C处于erroneous状态,释放LC并抛出异常NoClassDefFoundError
  6. 否则,将C标记为正在被本线程初始化,释放LC;然后,初始化那些final且为基础类型的类成员变量
  7. 初始化C的父类SC和各个接口SI_n(按照implements子句中的顺序来) ;如果SC或SIn初始化过程中抛出异常,则获取LC,将C标记为erroneous,并通知所有线程,然后释放LC,然后再抛出同样的异常。
  8. 从classloader处获取assertion是否被打开
  9. 接下来,按照文本顺序执行类变量初始化和静态代码块,或接口的字段初始化,把它们当作是一个个单独的代码块。
  10. 如果执行正常,获取LC,标记C为已初始化,并通知所有线程,然后释放LC
  11. 否则,如果抛出了异常E。若E不是Error,则以E为参数创建新的异常ExceptionInInitializerError作为E。如果因为OutOfMemoryError导致无法创建ExceptionInInitializerError,则将OutOfMemoryError作为E。
  12. 获取LC,将C标记为erroneous,通知所有等待的线程,释放LC,并抛出异常E。
阅读更多

为什么HTTP Upgrade的时候,需要Connection: upgrade

很久之前,在看HTTP头部的时候,发现WebSocket等协议的Upgrade请求,需要同时带上Connection和Upgrade头部。但是,如果是仅仅Upgrade的话,Connection头部不就是多余的设计了么?

比如一个典型的WebSocket升级请求如下:

1
2
3
4
5
6
GET /chat HTTP/1.1
Host: example.com:8000
Upgrade: websocket
Connection: Upgrade
Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==
Sec-WebSocket-Version: 13

当时在知乎提了一个问题,结果到现在没有满意了回答,只能自己来回答了。

Connection的起源

最开始,在HTTP/1.0出现没多久,人们就意识到HTTP持久连接的重要性(毕竟三次握手还是很慢的),所以各个服务器实现都采用了Keep-Alive头部来表示这个请求支持连接持久化。

HTTP/1.1中的Connection

在HTTP/1.1中,正式标准化了Connection头部:

Connection头部一般表示那些头部是属于逐跳头部的,比如Connection: Custom-Header,就表示在这个连接中,Custom-Header是一个逐跳头部,不应当被代理原样传递给upstream。

有两个例外:close表示会话不持久化,keep-alive表示会话支持持久化(虽然有一个Keep-Alive头部,但是大小写不一样)。

阅读更多

JVM如何获取当前容器的资源限制

最近同事说到Java的 ParallelGCThreads 参数,我翻了下jdk8的代码,发现 ParallelGCThreads 的参数默认值如下:

  • 如果cpu核心数目少于等于8,则GC线程数量和CPU数一致
  • 如果cpu核心数大于8,则前8个核,每个核心对应一个GC线;其他核,每8个核对应5个GC线程

但是被提醒,发现即使在分配4核的容器上,GC线程数也为38。然后就想到应该和容器的资源限制有关——jvm可能无法觉察到当前容器的资源限制。

翻了下代码,发现最新版本的java是能感知容器的资源限制的,就按照jdk版本再翻了下代码:

线上的jdk(jdk8u144)

写一个sleep 1000s的程序,用于查看JVM的线程数量:

1
./jdk1.8.0_144/bin/java -XX:+UseG1GC -XX:+ParallelRefProcEnabled Main 

然后查看GC线程数目:

1
2
$ jstack $pid | grep 'Parallel GC Threads' | wc -l
38

一算就知道物理机器有56个核心(8+(56-8)*5/8=38)

阅读更多

如何找到一个可用端口?

很多场景中,我们确实需要找一个空闲端口,比如启动一个子进程监听指定端口,然后通过这个端口与之通信

然后实现方式就有很多了:

VSCode的实现

比如VSCode,就是逐个连接,如果某个端口连接失败,并且错误不是ECONNREFUSED的话,那么就说明这个端口可用。

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
function doFindFreePort(startPort: number, giveUpAfter: number, clb: (port: number) => void): void {
if (giveUpAfter === 0) {
return clb(0);
}

const client = new net.Socket();

// If we can connect to the port it means the port is already taken so we continue searching
client.once('connect', () => {
dispose(client);

return doFindFreePort(startPort + 1, giveUpAfter - 1, clb);
});

client.once('data', () => {
// this listener is required since node.js 8.x
});

client.once('error', (err: Error & { code?: string }) => {
dispose(client);

// If we receive any non ECONNREFUSED error, it means the port is used but we cannot connect
if (err.code !== 'ECONNREFUSED') {
return doFindFreePort(startPort + 1, giveUpAfter - 1, clb);
}

// Otherwise it means the port is free to use!
return clb(startPort);
});

client.connect(startPort, '127.0.0.1');
}

这种方式完全混淆了“端口可以被监听”和“端口不能连接”这两个语义,虽然现在Linux上述代码能够正常工作,但是保不准哪天新添加一个类似ECONNREFUSED这样的错误码呢。

vscode-mono-debug的实现

然后继续找,发现vscode-mono-debug的实现:通过不指定端口的方式listen,让操作系统分配端口:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int FindFreePort(int fallback)
{
TcpListener l = null;
try {
l = new TcpListener(IPAddress.Loopback, 0);
l.Start();
return ((IPEndPoint)l.LocalEndpoint).Port;
}
catch (Exception) {
// ignore
}
finally {
l.Stop();
}
return fallback;
}

这种方式好了一点,但是比人调用这个函数是为了拿到端口去监听,而这个函数并不会保证这个端口不被别人占用,所以这个实现还是有一点问题。

阅读更多

StringBuffer,StringBuilder以及String

今天在网上闲逛,看见 @姚冬 的一个回答

他提到的问题也很有深度,然后思考了下,想评论来着。然而评论区太小,写不下,所以单独写在这儿。

基本上可以当作快问快答来读…

为什么java中的string不以\0结尾?

  • \0结尾在很大程度上要求程序员写规范的代码,如果写出了不规范的代码,那么很容易就内存越界了。
  • 另外,string的内部存储是char[],而为了内存安全,java数组本来就有一个length属性,这时以\0结尾就是一个多余的设计了。
  • String的内部存储也只能是char[]了,如果是其他的方式,比如通过native内部放一个c风格的数组,那么java代码中的char[]和string的转换就要很多内存拷贝操作了。
  • 而C语言设计成\0结尾,是为了减少抽象层,让C语言更加贴近硬件

(在语言设计中,)字符串的长度放哪里,放到起始指针的位置,还是起始指针的前面 ?

  • Java中,String的length也就是数组的length,JLS也只是说明了arraylength字节码,没有规定如何实现
  • 不过Hot Spot的实现是,先元数据,再长度,再具体的内容(比如char[])

如果放前面,那么字符串起始指针和内存块起始不一致怎么解决

Java不存在这个问题,我觉得。元数据和length字段都在实际数组之前呢。Java中,访问任何对象之前都要再多一次跳转,跳过元数据(和length)。

字符串拼接的时候把源串复制到目标串结尾,那么目标串剩余内存不够怎么办,重新分配要多一次赋值,频繁拼接性能有问题怎么办

阅读更多