发表于

在《使用 Docker 和 Golang 快速上手 WebAssembly》一文中，我介绍了如何制作符合 WASI 接口标准的通用 WASM，以及如何在几种不同的场景下进行程序调用。

本篇文章将延续前文，聊聊在如何借助 WASM 增强 Golang、Node.js ，进行更高效的密集计算。

写在前面

或许有读者会说，既然使用 Golang 又何必使用 Node.js，差不多的代码实现场景，两者性能根本不在一个数量级，比较起来不够客观。但其实，完全没有必要做这样的语言对立，除了两种语言的绝对的性能区别之外，或许我们也应该关注下面的事情：

在相同的计算场景下，如果分别以两种语言自身的实现方式为基准，配合 WASM 进行业务实现，是否有可能在：程序执行效率、程序分发内容安全、插件生态上产生更好的变化呢？

以及，我们可以脑洞更大一些，两种语言是否可以通过 WASM 的方式进行生态整合，让丰富的 Node / NPM 生态，灵活的 JavaScript 应用和严谨高效的 Golang 产生化学反应呢？

在开始本文之前，我先来说几个让人意外的观察结论（具体数据可以参考文末表格）：

  • 如果说 Go 在使用 WASM 的模式下，普遍执行速度并不会比“原生”差多少，甚至在个别场景下，执行速度还比原生快，你是否会感到诧异？
  • 如果说原本 Node 多进程/线程的执行速度落后相同功能的 Golang 程序 200%，在不进行极端优化的场景下，仅仅是通过引入 WASM，就能让差距缩小到 100%。
  • 甚至在一些情况下，你会发现 Node + WASM 的性能和 Go 最佳的表现其实差距可以从 300% 缩短到接近 30%。

如果你觉得意外，但是又好奇，不妨跟随文章自己亲自来试一试。

测试环境中的几种程序，为了模拟最糟糕的情况，均采用 CLI 一次性触发执行的方式来收集结果，减少 Go 语言运行时的 GC 优化、或者 Node 在运行过程中的 JIT 优化，以及字节码缓存带来的有益帮助。

前置准备

在开始折腾之旅之前，我们首先需要准备环境。为了保障程序运行和测试的结果尽量客观，我们统一使用同一台机器，并且准备相同的容器环境，并将容器可以使用的 CPU 资源数量限制小一些，为宿主机预留一些资源，确保测试的机器不会出现 CPU 不足的状况。

关于构建程序使用的方式和容器环境，可以参考前一篇文章的“环境准备”，为了节约篇幅，就不多赘述了。

下面是各种依赖和组件的版本。

1
2
3
4
5
6
7
8
9
10
11
bash复制代码# go version
go version go1.17.3 linux/amd64

# node --version
v17.1.0

# wasmer --version
wasmer 2.0.0

#tinygo version
tinygo version 0.21.0 linux/amd64 (using go version go1.17.3 and LLVM version 11.0.0)

准备 WASM 程序

为了更好的模拟和进行结果对比，我们需要一个计算时间比较久的“活儿”，“斐波那契数列”就是一个不错的选择，尤其是没有进行动态规划优化的“基础版”。

约定模拟密集计算的场景

这里为了方便程序性能对比，我们统一让程序针对斐波那契数列的第40位（大概1亿多的一个整数）进行快速的重复计算。

为了保证容器内的 CPU 充分使用，结果相对客观，程序一律使用“并行计算”的方式来进行数值计算。

使用 Go 编写 具备 WASI 标准接口的 WASM 程序

如果将上面的需求进行翻译，仅实现斐波那契数列的计算。那么使用 Go 不做任何算法优化的话，纯计算函数的实现，代码大概会类似下面：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
go复制代码package main

func main() {}

//export fibonacci
func fibonacci(n uint) uint {
	if n == 0 {
		return 0
	} else if n == 1 {
		return 1
	} else {
		return fibonacci(n-1) + fibonacci(n-2)
	}
}

将上面的内容保存为 wasm.go，参考上篇文章中提到的编写通用的 WASI 程序，执行 tinygo build --no-debug -o module.wasm -wasm-abi=generic -target=wasi wasm.go。

我们将会顺利的得到一个编译好的、通用的 WASM 程序，用于稍后的程序测试中。

编写 Go 语言基准版程序

虽然我们已经得到了 WASM 程序，但是为了直观的比较，我们还是需要一个完全使用 Go 实现基础版的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
go复制代码package main

import (
	"fmt"
	"time"
)

func fibonacci(n uint) uint {
	if n == 0 {
		return 0
	} else if n == 1 {
		return 1
	} else {
		return fibonacci(n-1) + fibonacci(n-2)
	}
}

func main() {
	start := time.Now()
	n := uint(40)
	fmt.Println(fibonacci(n))
	fmt.Printf("🎉 都搞定了，用时：%v \n", time.Since(start).Milliseconds())
}

将上面的代码保存为 base.go，然后执行 go run base.go，将会看到类似下面的结果：

1
2
go复制代码102334155
🎉 都搞定了，用时：574

如果你想追求绝对的性能，可以进行 go build base.go，然后执行 ./base，不过因为代码实在是太简单了，从输出结果来看，性能差异并不大。

基础计算功能搞定后，我们来简单调整代码，让代码具备并行计算的能力：

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
45
46
47
go复制代码package main

import (
	"fmt"
	"os"
	"runtime"
	"strconv"
	"time"
)

func fibonacci(n uint) uint {
	if n == 0 {
		return 0
	} else if n == 1 {
		return 1
	} else {
		return fibonacci(n-1) + fibonacci(n-2)
	}
}

func calc(n uint, ch chan string) {
	ret := fibonacci(n)
	msg := strconv.FormatUint(uint64(ret), 10)
	fmt.Println(fmt.Sprintf("📦 收到结果 %s", msg))
	ch <- msg
}

func main() {
	numCPUs := runtime.NumCPU()
	n := uint(40)
	ch := make(chan string, numCPUs)

	fmt.Printf("🚀 主进程上线 #ID %v\n", os.Getpid())

	start := time.Now()

	for i := 0; i < numCPUs; i++ {
		fmt.Printf("👷 分发计算任务 #ID %v\n", i)
		go calc(n, ch)
	}

	for i := 0; i < numCPUs; i++ {
		<-ch
	}

	fmt.Printf("🎉 都搞定了，用时：%v \n", time.Since(start).Milliseconds())
}

将代码保存为 full.go，然后执行 go run full.go，将会看到类似下面的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
go复制代码🚀 主进程上线 #ID 2248
👷 分发计算任务 #ID 0
👷 分发计算任务 #ID 1
👷 分发计算任务 #ID 2
👷 分发计算任务 #ID 3
👷 分发计算任务 #ID 4
👷 分发计算任务 #ID 5
👷 分发计算任务 #ID 6
👷 分发计算任务 #ID 7
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
🎉 都搞定了，用时：658

是不是有一丝性价比的味道，前面一次计算结果接近 600 毫秒，这次并发8个（受限于 Docker 环境资源限制）计算，也就 650 毫秒。

编写 Go 语言调用 WASM 程序

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
go复制代码package main

import (
	"fmt"
	"os"
	"runtime"
	"time"

	"io/ioutil"

	wasmer "github.com/wasmerio/wasmer-go/wasmer"
)

func main() {
	wasmBytes, _ := ioutil.ReadFile("module.wasm")
	store := wasmer.NewStore(wasmer.NewEngine())
	module, _ := wasmer.NewModule(store, wasmBytes)

	wasiEnv, _ := wasmer.NewWasiStateBuilder("wasi-program").Finalize()
	GenerateImportObject, err := wasiEnv.GenerateImportObject(store, module)
	check(err)

	instance, err := wasmer.NewInstance(module, GenerateImportObject)
	check(err)

	wasmInitial, err := instance.Exports.GetWasiStartFunction()
	check(err)
	wasmInitial()

	fibonacci, err := instance.Exports.GetFunction("fibonacci")
	check(err)

	numCPUs := runtime.NumCPU()
	ch := make(chan string, numCPUs)

	fmt.Printf("🚀 主进程上线 #ID %v\n", os.Getpid())

	start := time.Now()

	for i := 0; i < numCPUs; i++ {
		fmt.Printf("👷 分发计算任务 #ID %v\n", i)

		calc := func(n uint, ch chan string) {
			ret, _ := fibonacci(n)
			msg := fmt.Sprintf("%d", ret)
			fmt.Println(fmt.Sprintf("📦 收到结果 %s", msg))
			ch <- msg
		}

		go calc(40, ch)
	}

	for i := 0; i < numCPUs; i++ {
		<-ch
	}

	fmt.Printf("🎉 都搞定了，用时：%v \n", time.Since(start).Milliseconds())

}

func check(e error) {
	if e != nil {
		panic(e)
	}
}

将代码保存为 wasi.go ，执行 go run wasi.go，会得到类似下面的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
go复制代码🚀 主进程上线 #ID 3198
👷 分发计算任务 #ID 0
👷 分发计算任务 #ID 1
👷 分发计算任务 #ID 2
👷 分发计算任务 #ID 3
👷 分发计算任务 #ID 4
👷 分发计算任务 #ID 5
👷 分发计算任务 #ID 6
👷 分发计算任务 #ID 7
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
🎉 都搞定了，用时：595

多执行几次，你会发现相比较完全使用 Go 实现的程序，多数执行结果居然会更快一些，极限的情况，也不过是差不多快。是不是性价比的味道又来了。（不过为了保证客观，文末会附带多次计算结果）

使用 Node 编写基准版程序（Cluster模式）

相同的代码如果使用 Node.js 来实现，行数会稍微多一点。

虽然程序文件名叫啥都行，但是为了能在 CLI 执行上偷懒，就管它叫 index.js 吧：

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
45
46
47
48
49
50
51
52
53
js复制代码const cluster = require('cluster');
const { cpus } = require('os');
const { exit, pid } = require('process');

function fibonacci(num) {
  if (num === 0) {
    return 0;
  } else if (num === 1) {
    return 1;
  } else {
    return fibonacci(num - 1) + fibonacci(num - 2);
  }
}


const numCPUs = cpus().length;

if (cluster.isPrimary) {
  let dataStore = [];
  const readyChecker = () => {
    if (dataStore.length === numCPUs) {
      console.log(`🎉 都搞定了，用时：${new Date - start}`);
      exit(0);
    }
  }

  console.log(`🚀 主进程上线 #ID ${pid}`);
  const start = new Date();

  for (let i = 0; i < numCPUs; i++) {
    cluster.fork();
  }

  cluster.on('online', (worker) => {
    console.log(`👷 分发计算任务 #ID ${worker.id}`);
    worker.send(40);
  });

  const messageHandler = function (msg) {
    console.log("📦 收到结果", msg.ret)
    dataStore.push(msg.ret);
    readyChecker()
  }

  for (const id in cluster.workers) {
    cluster.workers[id].on('message', messageHandler);
  }

} else {
  process.on('message', (msg) => {
    process.send({ ret: fibonacci(msg) });
  });
}

保存好文件，执行 node . ，程序输出内容会类似下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
js复制代码🚀 主进程上线 #ID 2038
👷 分发计算任务 #ID 1
👷 分发计算任务 #ID 2
👷 分发计算任务 #ID 3
👷 分发计算任务 #ID 4
👷 分发计算任务 #ID 7
👷 分发计算任务 #ID 5
👷 分发计算任务 #ID 6
👷 分发计算任务 #ID 8
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
🎉 都搞定了，用时：1747

目前来看，执行时间差不多是 Go 版程序的 3 倍，不过往好处想，可提升空间应该也非常大。

使用 Node 编写基准版程序（Worker Threads）

当然，每当提到 Node.js Cluster 的时候，就不免会有人说 Cluster 数据交换效率低、比较笨重，所以我们同样测试一把 Worker Threads。

其实从 Node.js 12.x LTS 开始，Node 就具备了 Worker Threads 的能力。关于如何使用 Node.js 的 Worker Treads ，以及循序渐进的理解如何使用 SharedArrayBuffer，可以参考这篇文章《How to work with worker threads in NodeJS》，本文就不做基础展开了。考虑到我们模拟的是极限糟糕的情况，所以这里也不必使用 node-worker-threads-pool 之类的三方库，对 threads 做 pool 化了。（实测几乎没差别）

将上面 Cluster 版本的代码简单调整，我们可以得到类似下面的代码，不同的是，为了书写简单，我们这次需要拆分为两个文件：

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
js复制代码const { Worker } = require("worker_threads");
const { cpus } = require('os');
const { exit } = require('process');

let dataStore = [];

const readyChecker = () => {
    if (dataStore.length === numCPUs) {
        console.log(`🎉 都搞定了，用时：${new Date - start}`)
        exit(0);
    }
}

const num = [40];
const sharedBuffer = new SharedArrayBuffer(Int32Array.BYTES_PER_ELEMENT * num.length);
const sharedArray = new Int32Array(sharedBuffer);
Atomics.store(sharedArray, 0, num);

const numCPUs = cpus().length;

console.log(`🚀 主进程上线 #ID ${process.pid}`);

const start = new Date();

for (let i = 0; i < numCPUs; i++) {
    const worker = new Worker("./worker.js");

    worker.on("message", msg => {
        console.log("📦 收到结果", msg.ret)
        dataStore.push(msg.ret);
        readyChecker()
    });

    console.log(`👷 分发计算任务`);
    worker.postMessage({ num: sharedArray });
}

可以考虑换个目录，先将上面的内容同样保存为 index.js。我们继续来完成 worker.js 的内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
js复制代码const { parentPort } = require("worker_threads");

function fibonacci(num) {
    if (num === 0) {
        return 0;
    } else if (num === 1) {
        return 1;
    } else {
        return fibonacci(num - 1) + fibonacci(num - 2);
    }
}

parentPort.on("message", data => {
    parentPort.postMessage({ num: data.num, ret: fibonacci(data.num) });
});

在文件都保存就绪后，执行 node . 同样可以看到类似下面的输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
js复制代码🚀 主进程上线 #ID 2190
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
🎉 都搞定了，用时：1768

这里应该是因为交换的数据量比较少，所以执行时间其实和 Cluster 版本差不多。

使用 Node 调用 WASM 程序（Cluster）

简单调整上文中的 Cluster 模式的代码，来实现一个能够使用 WASM 进行计算的程序：

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
45
46
47
48
49
50
51
52
53
js复制代码const { readFileSync } = require('fs');
const { WASI } = require('wasi');
const { argv, env } = require('process');

const cluster = require('cluster');
const { cpus } = require('os');
const { exit, pid } = require('process');

const numCPUs = cpus().length;

if (cluster.isPrimary) {
    let dataStore = [];
    const readyChecker = () => {
        if (dataStore.length === numCPUs) {
            console.log(`🎉 都搞定了，用时：${new Date - start}`);
            exit(0);
        }
    }

    console.log(`🚀 主进程上线 #ID ${pid}`);
    const start = new Date();

    for (let i = 0; i < numCPUs; i++) {
        cluster.fork();
    }

    cluster.on('online', (worker) => {
        console.log(`👷 分发计算任务 #ID ${worker.id}`);
        worker.send(40);
    });

    const messageHandler = function (msg) {
        console.log("📦 收到结果", msg.ret)
        dataStore.push(msg.ret);
        readyChecker()
    }

    for (const id in cluster.workers) {
        cluster.workers[id].on('message', messageHandler);
    }

} else {

    process.on('message', async (msg) => {
        const wasi = new WASI({ args: argv, env });
        const importObject = { wasi_snapshot_preview1: wasi.wasiImport };
        const wasm = await WebAssembly.compile(readFileSync("./module.wasm"));
        const instance = await WebAssembly.instantiate(wasm, importObject);
        wasi.start(instance);
        const ret = await instance.exports.fibonacci(msg)
        process.send({ ret });
    });
}

将内容保存为 index.js 后，执行 node --experimental-wasi-unstable-preview1 . 后，会看到类似下面的输出结果：

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
js复制代码🚀 主进程上线 #ID 2338
(node:2338) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
👷 分发计算任务 #ID 1
👷 分发计算任务 #ID 3
👷 分发计算任务 #ID 2
👷 分发计算任务 #ID 5
👷 分发计算任务 #ID 6
👷 分发计算任务 #ID 8
👷 分发计算任务 #ID 4
👷 分发计算任务 #ID 7
(node:2345) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2346) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2360) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2350) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2365) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2377) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2371) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2354) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
🎉 都搞定了，用时：808

是不是再次嗅到了一丝真香的味道。在几乎不需要怎么费劲的情况下，简单调整下代码，执行效率比不使用 WASM 少了一半的时间，甚至在降低了一个数量级之后，如果继续优化、以及让程序持续的运行，或许甚至能够无限趋近于 Go 版本实现的程序的性能。

使用 Node 调用 WASM 程序（Worker Threads）

为了让我们的代码保持简单，我们可以将程序拆分为三个部分：入口程序、Worker程序、WASI 调用程序。还是先来实现入口程序 index.js：

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
js复制代码const { Worker } = require("worker_threads");
const { cpus } = require('os');
const { exit, pid } = require('process')

let dataStore = [];

const readyChecker = () => {
    if (dataStore.length === numCPUs) {
        console.log(`🎉 都搞定了，用时：${new Date - start}`);
        exit(0);
    }
}

const num = [40];
const sharedBuffer = new SharedArrayBuffer(Int32Array.BYTES_PER_ELEMENT * num.length);
const sharedArray = new Int32Array(sharedBuffer);
Atomics.store(sharedArray, 0, num);

const numCPUs = cpus().length;
console.log(`🚀 主进程上线 #ID ${pid}`);

const start = new Date();

for (let i = 0; i < numCPUs; i++) {
    const worker = new Worker("./worker.js");

    worker.on("message", msg => {
        console.log("📦 收到结果", msg.ret)
        dataStore.push(msg.ret);
        readyChecker()
    });

    console.log(`👷 分发计算任务`);
    worker.postMessage({ num: sharedArray });
}

接着实现 worker.js 部分：

1
2
3
4
5
6
7
8
js复制代码const { parentPort } = require("worker_threads");
const wasi = require("./wasi");

parentPort.on("message", async (msg) => {
    const instance = await wasi();
    const ret = await instance.exports.fibonacci(msg.num)
    parentPort.postMessage({ ret });
});

最后来实现新增的 wasi.js 部分：

1
2
3
4
5
6
7
8
9
10
11
12
js复制代码const { readFileSync } = require('fs');
const { WASI } = require('wasi');
const { argv, env } = require('process');

module.exports = async () => {
    const wasi = new WASI({ args: argv, env });
    const importObject = { wasi_snapshot_preview1: wasi.wasiImport };
    const wasm = await WebAssembly.compile(readFileSync("./module.wasm"));
    const instance = await WebAssembly.instantiate(wasm, importObject);
    wasi.start(instance);
    return instance;
};

将文件都保存好之后，执行 node . 可以看到类似上面 Cluster 版本的运行输出：

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
js复制代码🚀 主进程上线 #ID 2927
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
👷 分发计算任务
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
(node:2927) ExperimentalWarning: WASI is an experimental feature. This feature could change at any time
(Use `node --trace-warnings ...` to show where the warning was created)
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
📦 收到结果 102334155
🎉 都搞定了，用时：825

和分别使用 Cluster 和 Threads 实现基准版程序一样，执行时间也是差不多的。

对上述程序进行批量测试

为了让结果更客观，我们来编写一个小程序，让上面的程序分别重复执行 100 遍，并剔除表现最好和最糟糕的情况，取平均值。

先来实现一个简单的程序，代替我们的手动执行，针对不同的程序目录执行不同的命令，收集 100 次程序运行数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
js复制代码const { execSync } = require('child_process');
const { writeFileSync } = require('fs');
const sleep = (ms) => new Promise((res) => setTimeout(res, ms));

const cmd = './base';
const cwd = '../go-case';
const file = './go-base.json';

let data = [];

(async () => {
    for (let i = 1; i <= 100; i++) {
        console.log(`⌛️ 正在收集 ${i} 次结果`)
        const stdout = execSync(cmd, { cwd }).toString();
        const words = stdout.split('\n').filter(n => n && n.includes('搞定'))[0];
        const time = Number(words.match(/\d+/)[0]);
        data.push(time)
        await sleep(100);
    }
    writeFileSync(file, JSON.stringify(data))
})();

程序执行之后的输出会类似下面这样：

1
2
3
4
5
js复制代码⌛️ 正在收集 1 次结果
⌛️ 正在收集 2 次结果
⌛️ 正在收集 3 次结果
...
⌛️ 正在收集 100 次结果

在数据采集完毕之后，我们来编写一个更简单的程序，来查看程序运行的极端情况，以及排除掉极端情况后的平均值。（其实还应该跑个分布，不过偷懒就不做啦，感兴趣的同学可以试试看，会有惊喜）

1
2
3
4
5
6
7
8
9
10
11
12
js复制代码const raw = require('./data.json').sort((a, b) => a - b);
const body = raw.slice(1,-1);

const sum = body.reduce((x,y)=>x+y, 0);
const average = Math.floor(sum / body.length);

const best = raw[0];
const worst = raw[raw.length-1];

console.log('最佳',best);
console.log('最差',worst);
console.log('平均', average);

测试结果

前文提到，本次测试可以看作上述程序在非常受限制的情况下的比较差的数据。

因为这次我没有使用云服务器，而是使用笔记本上的本地容器，所以在持续运行过程中，由于多次密集计算，会导致设备的发热。存在因为温度导致计算结果放大的情况，如果你采取云端设备进行测试，数值结果应该会比较漂亮。

类型 最佳 最差 平均
Go 574 632 586
Go + WASM 533 800 610
Node Cluster 1994 3054 2531
Node Threads 1997 3671 2981
Node Cluster + WASM 892 1694 1305
Node Threads + WASM 887 2160 1334

但是总体而言，趋势还是很明显的，或许足够支撑我们在一些适合的场景下，采取 WASM + Node 或者 WASM + GO 的方式来进行混合开发了。

最后

如果说上一篇文章目的在于让想要折腾 WASM 的同学快速上手，那么这篇文章，希望能够帮助到“犹豫是否采用轻量异构方案”的同学，并给出最简单的实战代码。

因为非常多的客观原因，WASM 的发展和推广或许会和 Docker 一般，非常的慢热。在 2021 年的末尾，我们看到了 Docker 已经爆发出来的巨大能量。

如果你愿意保持开放心态，如同七八年前，对待 Docker 一样的来看待 WASM，相信这个轻量的、标准化的、异构的解决方案应该能为你和你的项目带来非常多的不同。

君子以文会友，以友辅仁。

–EOF

我们有一个小小的折腾群，里面聚集了几百位喜欢折腾的小伙伴。

在不发广告的情况下，我们在里面会一起聊聊软硬件、HomeLab、编程上的一些问题，也会在群里不定期的分享一些技术沙龙的资料。

喜欢折腾的小伙伴欢迎扫码添加好友。（添加好友，请备注实名，注明来源和目的，否则不会通过审核）

关于折腾群入群的那些事

如果你觉得内容还算实用，欢迎点赞分享给你的朋友，在此谢过。

本文使用「署名 4.0 国际 (CC BY 4.0)」许可协议，欢迎转载、或重新修改使用，但需要注明来源。 署名 4.0 国际 (CC BY 4.0)

本文作者: 苏洋

创建时间: 2021年11月26日
统计字数: 12835字
阅读时间: 26分钟阅读
本文链接: soulteary.com/2021/11/26/…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

问题描述

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例：

输入：matrix = [[“1”,”0”,”1”,”0”,”0”], [“1”,”0”,”1”,”1”,”1”], [“1”,”1”,”1”,”1”,”1”], [“1”,”0”,”0”,”1”,”0”]]

输出：4

image-20211122134648361

分析问题

我们都知道正方形的面积等于边长的平方，要想求出最大的正方形面积，首先需要找到最大正方形的边长，然后在计算平方就好。

最直观的解法就是使用暴力法来求解。具体来说，我们遍历矩阵中的每一个元素，每次遇到1时，则将该元素作为正方形的左上角；然后根据左上角所在的行和列计算可能的最大正方形的边长（每次在下方新增一行以及在右方新增一列，判断新增的行和列是否满足所有元素都是 1）。

下面我们来看一下代码的实现。

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
ini复制代码class Solution:
    def maximalSquare(self, matrix):
        #如果矩阵为空，直接返回0
        if len(matrix) == 0 \
                or len(matrix[0]) == 0:
            return 0
        #最大的边长
        max_length=0
        rows, columns = len(matrix), len(matrix[0])

        for i in range(rows):
            for j in range(columns):
                #遇到一个 1 作为正方形的左上角
                if matrix[i][j] == '1':
                    max_length = max(max_length, 1)
                    #求出超出边界的最小值
                    current_edge = min(rows - i, columns - j)
                    for k in range(1, current_edge):
                        #判断新增的一行一列是否均为1
                        tag = True
                        #判断对角线是否为1，如果为0，直接退出，
                        if matrix[i + k][j + k] == '0':
                            break
                        for m in range(k):
                            #判断对应的列或者行是否全为1
                            if matrix[i + k][j + m] == '0' or matrix[i + m][j + k] == '0':
                                tag = False
                                break
                        if tag:
                            #如果新增的一行一列均为1，则增加边长
                            max_length = max(max_length, k + 1)
                        else:
                            break
        #返回最大面积
        result = max_length * max_length
        return result

该算法的时间复杂度是 O(m * n * min(m, n) ^ 2)，其中 m 和 n 是矩阵的行数和列数；空间复杂度是O(1)。显然该算法的时间复杂度太高，下面我们来看一下如何进行优化求解。

这道题我们可以使用动态规划来求解。我们用 dp[i] [j] 表示以 (i，j) 为右下角，且只包含 1 的正方形的边长的最大值。在求出所有的dp[i] [j]的值以后，那么其中的最大值就是矩阵中只包含1的正方形的边长的最大值，其平方就是最大正方形的面积。下面我们来看一下如何来求解dp[i] [j] 。

对于矩阵中的每一个位置（i，j），检查其对应的值。

  • 如果该位置是0，那么dp[i] [j] =0，因为当前位置不可能在由1组成的正方形中；
  • 如果该位置是1，那么dp[i] [j] 的值由其上边，左边以及左上角三个相邻位置的值决定。即当前位置的值等于三个相邻位置元素对应的值的最小值加1。

dp[i] [j] = min( dp[i-1] [j] , dp[i] [j-1] , dp[i-1] [j-1] ) + 1

image-20211122172537892

我们来看一下边界条件。当i=0或者j=0时，如果矩阵中位置为(i, j) 的值为1，那么以位置（i,j）为右下角的矩阵的边长只能是1，即此时dp[i] [j] = 1。

当matrix 为 [[“1”,”0”,”1”,”0”,”0”], [“1”,”0”,”1”,”1”,”1”], [“1”,”1”,”1”,”1”,”1”], [“1”,”0”,”0”,”1”,”0”]] 时，其状态转移矩阵如下图所示。

image-20211122174241556

下面我们来看一下代码的实现。

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
ini复制代码class Solution:
    def maximalSquare(self, matrix):
        #如果矩阵为空，直接返回0
        if len(matrix) == 0 \
                or len(matrix[0]) == 0:
            return 0

        max_edge = 0
        m, n = len(matrix), len(matrix[0])
        #初始化一个状态转移矩阵
        dp = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '1':
                    #边界条件
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    max_edge = max(max_edge, dp[i][j])

        #求出最大正方形
        result = max_edge * max_edge
        return result

该算法的时间复杂度是O(m*n)，其中m、n分别为矩阵的行和列。空间复杂度也是O(m * n)。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

hashCode是什么？

首先，hashCode在计算机领域指的是一个数据经过hash funcation后得到的一个摘要，而这个摘要可以作为索引应用到hash map中去。接下来我们聊聊hashCode在java中是什么样的。

hashCode是Java.lang.Object定义的一个native方法，默认返回的是一个由对象的内存地址转换而来的一个数值。

在Object的子类中会有一些其他的实现，比如在Java.lang.String中，hashCode返回的是这个字符串每个字符的unicode码类乘跟累加混合运算得出来的一个数值。

又比如在Java.lang.Integer中，hashCode返回的就是这个Integer的值

不管怎么去实现hashCode，hashCode都必须遵守以下约定：

  1. 同一个对象返回的hashCode必须保持不变
  2. 两个对象如果通过equals判断是相等的，那么hashCode也必须相等

对于通过equals判断为不相等的对象并没有强制要求hashCode也不相等，但是，为这类不相等的对象产生不同的hashCode可以提升操作哈希表的性能。

就拿HashMap来说，其put方法有这样一个判断：

1
2
vbnet复制代码if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))

如果，equals判断两个对象不相等，但是这两个对象的hashCode一样，那么上面这个if里所有的判断都会执行一遍，这显然会造成没必要的性能损耗。

Java里为什么要有hashCode这个函数？

在java里，hashCode是实现Java.util.HashMap等hash类数据结构必不可少的一个组成部分。这类数据结构需要用hashCode来定位数据在hash map中的位置。比如，在HashMap#put中，有这么一段代码：

1
2
ini复制代码if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

PS:上面代码中的hash是对象的hashCode经过特殊处理后的一个int类型的值。这个特殊处理主要是将高位的影响向低位传播，这样就不会导致往一些size比较小的HashMap里插入数据时，无论高位(超过size的部分)怎么变，最终都会定位到同一个位置的问题。总而言之，这个特殊处理是为了降低hash冲突发生的概率。

可以看出，hashCode被用来定位key在tab这个数组中的位置。

另外，hashCode由于自身的一些特性，hashCode这个函数通常会将第一次调用计算出来的结果存储下来，这样以后每次调用就会直接返回这个值。所以，其实hashCode这个函数的调用所产生的计算量是很少的。这就牵扯到HashMap#put的一个小细节：

1
2
vbnet复制代码if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))

上面这段代码用来在发生hash碰撞时判断即将插入的key是否跟hash map中已有的的key是同一个。可以看到，这段代码首先就是比较两个key的hash是否相等。只有hash相等时才会进入后面的比较，首先会比较引用地址是否相等，不等时才最终执行equals()方法进行等价关系判断。所以优化体现在哪呢？

p.hash == hash这段代码是需要hashCode做支撑的，相对后面的equals()来说，它的执行成本更低。这个更低一是因为方法执行执行需要做一些额外的操作，比如栈帧出栈入栈，程序计数器的跳转等。另一方面，像Java.lang.String这个类的equals方法，它是通过字符逐个遍历来进行比对的，这个性能就更低了。

一些有意思的点

在Java.lang.String#hashCode的实现中，有下面这么一段代码：

1
ini复制代码h = 31 * h + val[i];

我当时看到这段代码有两个疑问：

  • 为什么这里要乘以一个31呢？
  • 别的数不可以吗？

关于这段代码，在Joshua Bloch的《Effective Java》这本书里有这么一段话(第三章第十一节)：

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, because multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance on some architectures: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

这里可以解答第一个问题。首先，选择31是因为它既是素数又是奇数。因为一个数乘以一个奇数在乘法溢出时不会导致信息丢失。又因为31 * i = (i << 5) - i ，位移+减法比乘法有着更好的性能。

关于大佬说的第二点好处，我也不是很理解，因为乘除都可以写成位移加上加减运算，区别在于位移的位数以及加减的次数。所以，我觉得应该是31转换乘位移加减法后，减法只需要执行一次即可。性能点应该在于加减执行的次数。那么，关于上面的疑问2，也就有了答案，只要一个数同时满足素数跟奇数就行，比如33 * i = (i << 5) + i。

总结

  1. hashCode是hashMap的实现中必不可少的一部分，同时呢，hashCode也间接参与到了hashMap内部的一些优化操作中。
  2. hashCode跟equals具备两个约定跟一个建议，约定决定了与hashCode相关的代码(比如hashMap)的执行结果的正确性，而建议决定了执行的性能

案例代码

github

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

  • 示例 1:
1
2
makefile复制代码输入: [10,2]
输出: "102"
  • 示例 2:
1
2
makefile复制代码输入: [3,30,34,5,9]
输出: "3033459"
  • 提示
1
matlab复制代码0 < nums.length <= 100

解析

根据题意，这一题最关键的部分就是自定义排序，一旦找到排序的奇点，就可以轻而易举解决这一题。 我们判断两个数字谁大谁小的依据是，str1+str2是否大于str2+str1，其实就是这么简单。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
scss复制代码class Solution {
    public String minNumber(int[] nums) {
        //第一种方法，全排列，但是比较麻烦
        //第二种方法就是按照一定顺序排列，也就是要重写比较器
        //从首位到末尾开始比较
        //所以手写一个冒泡，排好序以后用
        //用新的比较器写一个冒泡排序
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (o1, o2) -> (o1+o2).compareTo(o2+o1));
        StringBuilder sb = new StringBuilder();
        for (String x:strs) {
            sb.append(x);
        }
        return sb.toString();
    }
}

运行结果：

执行结果：通过

执行用时：4 ms, 在所有 Java 提交中击败了97.52%的用户

内存消耗：38 MB, 在所有 Java 提交中击败了45.05%的用户

  • 其他解法

下面这种方式是通过随机快排，切记排序不是简单对a,b排序，如排序12，543，那么应该比较的是12543 和 54312 这个直接找到每个数是多少位，然后相加即可 12000 + 54 与 54300 + 12 比较

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
css复制代码class Solution {
    public String minNumber(int[] nums) {
        return minNumber4(nums);
    }
    public String minNumber4(int[] nums){
       quickSortRandom(nums,0,nums.length-1);
       StringBuilder sb = new StringBuilder(nums.length);
       for(int i : nums) sb.append(i);
       return sb.toString();
    }
    public void quickSortRandom(int[] A,int low,int high){
        if(low < 0 || high >= A.length || low >= high ) return;
        int q = partition(A,low,high);
        quickSortRandom(A,low,q-1);
        quickSortRandom(A,q+1,high);
    }
    public int partition(int[] A,int low,int high){
        int rand = low + (int)(Math.random()*(high - low));
        swap(A,rand,high);
        int x = A[high],i = low - 1;
        long a,b;
        for(int j = low; j < high; j++){
            a = 10;b = 10;
            while(A[j] >= a) a *= 10;
            while(x >= b) b *= 10;
            if(A[j] * b + x <= A[j] + x * a){
                i++;
                swap(A,i,j);
            }
        }
        swap(A,i+1,high);
        return i + 1;
    }
    public void swap(int[] A,int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

一、git merge

1.使用

  • 将分支切换到 master 上去：git checkout master
  • 将分支 feature 合并到当前分支（即 master 分支）上：git merge feature

2.特点

  • 只处理一次冲突
  • 引入了一次合并的历史记录，合并后的所有 commit 会按照提交时间从旧到新排列
  • 所有的过程信息更多，可能会提高之后查找问题的难度

二、git rebase

1.使用

与 git merge 一致，git rebase 的目的也是将一个分支的更改并入到另外一个分支中去。

  • 执行 git rebase master 的操作，意味着让当前分支 feature 相对于 分支 master 进行变基
  • 遇到冲突，进行对比的双方分别是 master 分支的最新内容和 feature 分支的第一次提交的内容。
  • 在我们解决了冲突之后，需要执行 git rebase –continue 来继续变基的操作。
  • 执行之后又遇到了冲突，这次是与 feature 分支的第二次提交进行对比出现的冲突，意味着我们需要多次解决同一个地方的冲突。

2.特点

  • 改变当前分支从 master 上拉出分支的位置
  • 没有多余的合并历史的记录，且合并后的 commit 顺序不一定按照 commit 的提交时间排列
  • 可能会多次解决同一个地方的冲突（有 squash 来解决）
  • 更清爽一些，master 分支上每个 commit 点都是相对独立完整的功能单元

3.交互模式

1
css复制代码git rebase -i HEAD~4

指定了对当前分支的最近四次提交进行操作。

中间红框内有一些命令，可以用来处理某次提交的，可以使用 squash 来将所有的 commit 合并成一次提交，编辑并保存之后会出现编辑提交的信息的提示，编辑提交即可。

4.git rebase和git merge的区别

  • rebase 会把你当前分支的 commit 放到公共分支的最后面,所以叫变基。就好像你从公共分支又重新拉出来这个分支一样。
  • 而 merge 会把公共分支和你当前的 commit 合并在一起，形成一个新的 commit 提交

优劣：

  • git merge 优点是分支代码合并后不破坏原分支代码的提交记录，缺点是会产生额外的提交记录并进行两条分支的合并
  • git rebase 优点是可以将对象分支的提交记录续道目标分支上，形成线性提交历史记录，review时更加直观

5.什么时候使用rebase

  • 不能在一个共享的分支上进行git rebase操作
    • 因为往后放的这些 commit 都是新的,这样其他从这个公共分支拉出去的人，都需要再重新merge，导致提交记录混乱

如下图：

总结

  • 合代码到公共分支上时用git merge
  • 合代码到个人分支时用git rebase，形成线性提交历史记录

三、git cherry-pick

1.基本使用

  • git cherry-pick 的使用场景就是将一个分支中的部分的提交合并到其他分支
1
2
xml复制代码git checkout master 
git cherry-pick <commitHash>

使用以上命令以后，这个提交将会处在master的最前面

2.合并多个提交

1
2
3
css复制代码git cherry-pick <hashA> <hashB>     // 合并两个提交
git cherry-pick <hashA>..<hashB>    // 合并从A到B两个提交中到所有提交，但不包含A
git cherry-pick <hashA>^..<hashB>   // 合并从A到B两个提交中到所有提交，包含A

3.pick以后产生了冲突

当执行了cherry-pick 命令如果有冲突，就会报冲突错误

1
2
3
scss复制代码git cherry-pick --continue  // 1. 解决完冲突以后，继续下一个 cherry-pick
git cherry-pick --abort   // 2. 如果不想解决冲突，要放弃合并，用此命令回到操作以前
git cherry-pick --quit   // 3. 不想解决冲突，放弃合并，且保持现有情况，不回到操作以前

4.转移到另一个代码库

1
2
3
c复制代码git remote add target git://gitUrl //添加一个远程仓库target
git fetch target                   //远程代码抓取到本地
git log target/master              //获取该提交的哈希值

5.应用场景

想要合并某些内容，但又不想包含整个分支。这时用cherry-pick来合并单次提交

参考资料

Git merge和rebase分支合并命令的区别

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

  • 示例 1:
1
2
3
makefile复制代码输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
  • 提示
1
2
复制代码1 是丑数。
n 不超过1690。

解析

根据题意，我们可以有下面这种解法：丑数就是质因数只包含 2, 3, 5 的正整数。1是丑数

1.核心就是这句话：保证每个位置的丑数都有生成2、3、5的机会，且不漏过一个值！

2.循环结束后，保证每个位置的丑数都完成了2，3，5这三个操作！只不过重复值不会重复统计

3.确保每个丑数都会完成2，3，5这三个操作，如：b指向的丑数完成了一次3操作，就b++；

4.如果出现这种情况：dp[a] * 2 == dp[b] * 3,那么a和b都会完成自增，表示dp[a]这个丑数完成了2操作，dp[b]这个丑数完成了3操作，所以，下一个需要完成2操作的丑数是dp[a+1]，下一个需要完成3操作的丑数是dp[b+1]

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ini复制代码class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n]; //初始化存储丑数的数组
        dp[0] = 1;
        int a=0,b=0,c=0;
        
        for(int i=1;i<n;i++){
        dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
        if(dp[i] == dp[a]*2) a++; 
        if(dp[i] == dp[b]*3) b++;
        if(dp[i] == dp[c]*5) c++;
        }
        return dp[n-1];
    }
   
}

运行结果：

执行结果：通过

执行用时：2 ms, 在所有 Java 提交中击败了99.62%的用户

内存消耗：37.4 MB, 在所有 Java 提交中击败了73.38%的用户

此外还有最小堆算法：

要得到从小到大的第 nn 个丑数，可以使用最小堆实现。初始时堆为空。首先将最小的丑数 11 加入堆。每次取出堆顶元素 xx，则 xx 是堆中最小的丑数，由于 2x, 3x, 5x2x,3x,5x 也是丑数，因此将 2x, 3x, 5x2x,3x,5x 加入堆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ini复制代码class Solution {
    public int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> seen = new HashSet<Long>();
        PriorityQueue<Long> heap = new PriorityQueue<Long>();
        seen.add(1L);
        heap.offer(1L);
        int ugly = 0;
        for (int i = 0; i < n; i++) {
            long curr = heap.poll();
            ugly = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ugly;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第7天，活动详情查看：2021最后一次更文挑战」

连通“指令”和“计算”这两大功能，才能构建完整的CPU。

1 指令周期（Instruction Cycle）

计算机每执行一条指令的过程，可分解为如下步骤：

  1. Fetch（取指令）
    指令放在存储器，通过PC寄存器和指令寄存器取出指令的过程，由控制器（Control Unit）操作。
    从PC寄存器找到对应指令地址，据指令地址从内存把具体指令加载到指令寄存器，然后PC寄存器自增
  2. Decode（指令译码）
    据指令寄存器里面的指令，解析成要进行何操作，是R、I、J中的哪一种指令，具体要操作哪些寄存器、数据或内存地址。该阶段也是由控制器执行。
  3. Execute（执行指令）
    实际运行对应的R、I、J这些特定的指令，进行算术逻辑操作、数据传输或者直接的地址跳转。无论是算术操作、逻辑操作的R型指令，还是数据传输、条件分支的I型指令，都由算术逻辑单元（ALU）操作，即由运算器处理。
    如果是一个简单的无条件地址跳转，那可直接在控制器里完成，无需运算器。
  4. 重复1～3

这就是个永动机般的“FDE”循环，即指令周期。

CPU还有两个Cycle：

Machine Cycle，机器周期或者CPU周期

CPU内部操作速度很快，但访问内存速度却慢很多。
每条指令都需要从内存里面加载而来，所以一般把从内存里面读取一条指令的最短时间，称为CPU周期。

Clock Cycle，时钟周期及机器主频

一个CPU周期，通常由几个时钟周期累积。一个CPU周期时间，就是这几个Clock Cycle总和。

对于一个指令周期，取出一条指令，然后执行它，至少需两个CPU周期：

  • 取出指令，至少得一个CPU周期
  • 执行指令，至少也得一个CPU周期
    因为执行完的结果，还要写回内存

三个周期（Cycle）之间的关系


一个指令周期，包含多个CPU周期，而一个CPU周期包含多个时钟周期。

2 建立数据通路

名字是什么其实并不重要，一般可以认为，数据通路就是我们的处理器单元，通常由两类原件组成：

  • 操作元件，也叫组合逻辑元件（Combinational Element），就是ALU
    在特定的输入下，根据下面的组合电路的逻辑，生成特定的输出。
  • 存储元件，也叫状态元件（State Element）
    如在计算过程中要用到的寄存器，无论是通用寄存器还是状态寄存器，都是存储元件。

通过数据总线把它们连接起来，就可完成数据存储、处理和传输，即建立了数据通路。

控制器

可以把它看成只是机械地重复“Fetch - Decode - Execute“循环中的前两个步骤，然后把最后一个步骤，通过控制器产生的控制信号，交给ALU去处理。

控制器将CPU指令解析成不同输出信号

目前Intel CPU支持2000个以上指令。说明控制器输出的控制信号，至少有2000种不同组合。

运算器里的ALU和各种组合逻辑电路，可认为是一个固定功能的电路。
控制器“翻译”出来的，就是不同控制信号，告诉ALU去做不同计算。正是控制器，才让我们能“编程”实现功能，才铸就了“存储程序型计算机”。

  • 指令译码器将输入的机器码，解析成不同操作码、操作数，然后传输给ALU计算

3 CPU对硬件电路的要求

搭建CPU，还得在数字电路层面，实现如下功能。

ALU

就是个无状态，根据输入计算输出结果的第一个电路。

支持状态读写的电路元件 - 寄存器

要有电路能存储上次计算结果。

该计算结果不一定要立刻给下游电路使用，但可在需要时直接用。常见支持状态读写的电路：

  • 锁存器（Latch）
  • D触发器（Data/Delay Flip-flop）电路

自动”电路，按固定周期实现PC寄存器自增

自动执行Fetch - Decode - Execute。

我们的程序执行，并非靠人工拨动开关执行指令。得有个“自动”电路，无休止执行一条条指令。

看似复杂的各种函数调用、条件跳转，只是修改了PC寄存器保存的地址。PC寄存器里面的地址一修改，计算机即可加载一条指令新指令，往下运行。
PC寄存器还叫程序计数器，随时间变化，不断计数。数字变大了，就去执行一条新指令。所以，我们需要的就是个自动计数的电路。

译码电路

无论是decode指令，还是对于拿到的内存地址去获取对应的数据或者指令，都要通过一个电路找到对应数据，就是“译码器”电路。

把这四类电路，通过各种方式组合在一起就能组成CPU。要实现这四种电路中的中间两种，我们还需要时钟电路的配合。下一节，我们一起来看一看，这些基础的电路功能是怎么实现的，以及怎么把这些电路组合起来变成一个CPU。

总结

至此，CPU运转所需的数据通路和控制器介绍完了，也找出完成这些功能，需要的4种基本电路：

  • ALU这样的组合逻辑电路
  • 存储数据的锁存器和D触发器电路
  • 实现PC寄存器的计数器电路
  • 解码和寻址的译码器电路

CPU 好像一个永不停歇的机器，一直在不停地读取下一条指令去运行。那为什么 CPU 还会有满载运行和 Idle 闲置的状态呢？

操作系统内核有 idle 进程，优先级最低，仅当其他进程都阻塞时被调度器选中。idle 进程循环执行 HLT 指令，关闭 CPU 大部分功能以降低功耗，收到中断信号时 CPU 恢复正常状态。 CPU在空闲状态就会停止执行，即切断时钟信号，CPU主频会瞬间降低为0，功耗也会瞬间降为0。由于这个空闲状态是十分短暂的，所以你在任务管理器也只会看到CPU频率下降，不会看到降为0。 当CPU从空闲状态中恢复时，就会接通时钟信号，CPU频率就会上升。所以你会在任务管理器里面看到CPU的频率起伏变化。

uptime 命令查看平均负载

满载运行就是平均负载为1.0(一个一核心CPU)，定义为特定时间间隔内运行队列中的平均线程数。
load average 表示机器一段时间内的平均load，越低越好。过高可能导致机器无法处理其他请求及操作，甚至死机。

当CUP执行完当前系统分配的任务，为省电，系统将执行空闲任务（idle task），该任务循环执行HLT指令，CPU就会停止指令的执行，且让CPU处于HALT状态，CPU虽停止指令执行，且CPU部分功能模块将会被关闭（以低功耗），但CPU的LAPIC（Local Advanced Programmable Interrupt Controller）并不会停止工作，即CPU将会继续接收外部中断、异常等外部事件（事实上，CPU HALT状态的退出将由外部事件触发）。“Idle 闲置”是一种低功耗的状态，cpu在执行最低功耗的循环指令。实际上并非啥都没干，而是一直在干最最轻松的事儿。
当CPU接收到这些外部事件，将会从HALT状态恢复，执行中断服务函数，且当中断服务函数执行完毕后，指令寄存器（CS:EIP）将会指向HLT指令的下一条指令，即CPU继续执行HLT指令之后的程序。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

在这之前，Kubernetes开发团队宣布，他们正在弃用docker。这则新闻通过科技界和社交网络广为流传。Kubernetes 群集是否会中断，如果是，我们将如何运行我们的应用程序？我们现在该怎么办？今天，我们将审查所有这些问题和更多。

让我们从头开始。如果你已经熟悉docker和kubernetes，并希望直接了解关键信息，跳到docker弃用对你有什么影响？

什么是容器？

尽管Docker被用作容器的同义词，但现实情况是，它们早在docker成为东西之前就已经存在了。Unix 和 Linux 自 70 年代末开始引入 chroot 以来，一直有某种形式的容器。Chroot 允许系统管理员在一种但并非真正孤立的文件系统中运行程序。后来，这个想法被提炼和增强到集装箱引擎，如免费 BSD Jails ， OpenVZ ，或Linux Containers（LXC） 。

但是什么是容器呢？

容器是一个逻辑分区，我们可以运行与系统其余部分分离的应用程序。每个应用程序都有自己的专用网络和不与其他容器或主机共享的虚拟文件系统。

图片

运行容器应用程序比安装和配置软件方便得多。首先，容器是便携式的：我们可以在一台服务器中构建，并相信它将在任何服务器中工作。另一个优点是，我们可以同时运行同一程序的多个副本，而不会发生冲突或重叠，否则确实很难做到。

然而，要使这一切发挥作用，我们需要一个容器runtime，一个能够运行容器的软件。

什么是docker？

docker是最受欢迎的容器runtime-从长远来看。这并不奇怪，因为它将容器的概念引入主流，这反过来又激发了像Kubernetes这样的平台的创建。

在Docker之前，运行容器确实是可能的，但这是艰苦的工作。Docker 使事情变得简单，因为它是一个完整的技术堆栈，可以：

  • 管理容器生命周期。
  • 代理请求来回容器。
  • 监视和记录容器活动。
  • 安装共享目录。
  • 对容器设置资源限制。
  • 生成镜像。Dockerfile是构建容器镜像的格式文件。
  • 从注册处推送和拉取图像。

在第一次迭代中，Docker 使用 Linux 容器（LXC）作为运行时间后端。随着项目的发展，LXC被容器所取代，docker自己的实施。现代docker安装分为两个服务：containerd，负责管理容器；dockerd，处理剩余的部分。

图片

什么是kubernetes？

kubernetes采取容器的想法，并把它一个缺口。Kubernetes 不是在单个服务器中运行容器化应用程序，而是将其分布在一组机器上。在 Kubernetes 中运行的应用程序的外观和行为都像一个单元，尽管在现实中，它们可能由松散耦合的容器排列而成。

Kubernetes在容器顶部添加分布式计算功能：

  • 吊舱：吊舱是共享内存、CPU、存储和网络等资源的逻辑容器组。
  • 自动缩放：Kubernetes 可根据需要启动和停止吊舱，从而自动适应不断变化的工作负载。
  • 自我修复：容器在故障时被监控并重新启动。
  • 负载均衡：请求分布在健康的可用吊舱上。
  • 推出：kubernetes支持自动推出和回滚。使 Canary 和 Blue-Green 等复杂程序变得微不足道。我们可以将Kubernetes的架构视为两架飞机的组合：

控制面板是集群的协调大脑。它有一个控制器，管理节点和服务，调度器分配吊舱的节点，和API服务，处理通信。配置和状态存储在一个高度可用的数据库称为etcd。工人节点是运行容器的机器。每个工人节点运行几个组件，如kubelet代理、网络代理和容器运行时。Kubernetes版本 v1.20 的默认容器运行时是 Docker。

图片

容器格式

在启动容器之前，我们需要构建或下载一个容器镜像，这是一个文件系统，里面装满了应用程序所需的一切：代码、二进制文件、配置文件、库和依赖项。

容器的普及表明需要开放的镜像标准。因此，Docker 公司和 CoreOS 于 2015 年建立了开放式容器计划（OCI） ，其使命是生产供应商中立格式。这一努力的结果是创造了两项标准：

  • 定义镜像二进制格式的镜像规范。
  • 描述如何拆开和运行容器的运行时规范。OCI 维护称为runc的参考实现。容器和 CRI-O 都使用背景中的流体生成容器。OCI 标准带来了不同容器解决方案之间的互操作性。因此，一个系统内置的图像可以在任何其他合规堆栈中运行。

OCI 标准带来了不同容器解决方案之间的互操作性。因此，一个系统内置的镜像可以在任何其他合规堆栈中运行。

Docker Vs. Kubernetes

这里是事情变得更加技术性的地方。我说每个Kubernetes工人节点都需要一个容器运行时。在其第一个原始设计 ，Docker是离不开Kubernetes，因为它是唯一的运行时支持。

然而，Docker从未被设计成在Kubernetes内运行。意识到这个问题，Kubernetes开发人员最终实现了一个名为容器运行时间接口（CRI） 的 API。此界面允许我们在不同的容器运行时之间进行选择，使平台更加灵活，对 Docker 的依赖性更小。

图片

这一变化给Kubernetes团队带来了新的困难， 因为Docker不知道CRI或支持CRI 。因此，在引入 API 的同时，他们不得不编写一个名为Dockershim的适配器，以便将 CRI 消息转换为 Docker 特定命令。

弃用Dockershim

虽然Docker是一段时间以来第一个也是唯一支持的引擎，但是它从来不在长期计划内。Kubernetes V 1.20弃用了dockershim ， 拉开了离开docker的过渡的序幕。

一旦过渡完成，堆栈就会变小得多。它从这个：

图片

变为：

图片

结果是每个工人节点所需的膨胀更少，依赖性也更少。

那么，为什么要改变呢？

简单地说，Docker很重。我们得到更好的性能与轻量级集装箱运行时，如容器或CRI-O 。最近的例子是，谷歌的基准显示，容器消耗的内存和CPU更少，而吊舱的启动时间也比Docker少。

此外，在某些方面，Docker本身可以被认为是技术债务。事实上，Kubernetes需要的是容器运行时：容器。其余的，至少就Kubernetes而言，是额外的开销。

Kubernetes弃用Docker对你有什么影响？

事情并不像听起来那么戏剧化。让我们在整节的开头说，在v1.20中唯一改变的是，你会得到一个弃用警告，只有当你运行Docker。就这样。

我还能使用Docker进行开发吗？

是的，你绝对可以，现在和在可预见的未来。你看，Docker不运行Docker特定的镜像：它运行符合OCI标准的容器。只要Docker继续使用这种格式，Kubernetes将继续接受它们。

我仍然可以用Docker打包我的生产应用程序吗？

是的，原因与上一个问题相同。与Docker打包的应用程序将继续运行-那里没有变化。因此，您仍然可以使用您了解和喜爱的工具构建和测试容器。您不需要更改CI/CD 管道或切换到其他镜像注册，Docker 制作的镜像将继续像始终一样在群集中工作。

我需要改变什么？

现在什么都没有如果您的群集使用 Docker 作为运行时，则升级到 v1.20 后将获得弃用警告。但这一变化是Kubernetes社区发出的一个明确信号，表明他们想采取的方向。是时候开始规划未来了。

变革何时发生？

该计划是在2021年底将所有Docker依赖关系完全删除v1.23。

当Kubernetes离开时，会发生什么？

届时，Kubernetes 集群管理员将被迫切换到符合 CRI 标准的容器运行时。

如果你是一个最终用户，没有很多变化给你。除非你运行某种节点自定义，否则你可能不必做任何特别的事情。仅测试您的应用程序与新的容器运行时配合使用。

这些是升级到 v1.23 后会导致问题或中断的一些事情：

  • 使用Docker特定的日志记录和监视。即，从日志中解析 Docker 消息或投票 Docker API。
  • 使用Docker优化。
  • 运行依赖docker CLI 的脚本。
  • 运行docker命令在特权吊舱。例如：构建镜像。有关替代解决方案，请参阅卡尼科等项目。docker build
  • 使用docker工人设置。
  • 运行窗口容器。容器确实在 Windows 中工作， 但它的支持水平还没有达到 Docker 的。目标是通过集装箱版本 1.20为 Windows 提供稳定的容器释放。
  • 如果您在 AWS EKS、Google GKE 或 Azure AKS 等云提供商上使用托管集群，请在 Docker 支持消失之前检查您的集群是否使用了支持的运行时。有些云供应商落后几个版本，因此您可能有更多的时间来计划。因此，请咨询您的提供商。举个例子，谷歌云宣布，他们正在改变默认运行时从Docker到容器的所有新创建的工人节点，但你仍然可以选择Docker。

如果您运行自己的集群：除了检查上述要点外，您还需要评估移动到与 CRI 完全兼容的另一个容器运行时。Kubernetes文档详细解释了这些步骤：

  • 切换到容器
  • 切换到CRI-O 或者，如果你想继续使用Docker过去的版本1.23，按照cri-dockerd项目，它计划保持Docker作为一个可行的运行时选择。

结论

Kubernetes正在成长，但这种变化并不需要是一次创伤性的经历。大多数用户不必采取任何行动。对于那些这样做的人，还有时间测试和计划。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

实验名称

关联规则挖掘Apriori算法的实现

实验目的

1.掌握频繁项目集的生成原理

2.掌握关联规则挖掘的原理

3.掌握在weka中进行关联规则挖掘的具体流程。

实验内容

1.根据给定的事务数据库，支持数阈值2和置信度阈值0.7，编写代码生成频繁项目集及对应的关联规则。

2.利用weka工具对天气数据、美国国会议员投票信息、超市购物篮数据进行关联规则挖掘，并分析挖掘结果

实验步骤及结果

一.根据给定的事务数据库，支持数阈值2和置信度阈值0.7，编写代码生成频繁项目集及对应的关联规则。

新建java项目 Apriori.java

1.事务数据库、支持数、置信度的定义

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
java复制代码package rule;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Apriori {
	private final static int SUPPORT = 2;
	private final static String ITEM_SPLIT = ";";
	private final static String CON = "->";
	private final static double CONFIDENCE = 0.7;
	private final static List<String> transList = new ArrayList<String>();
	static {
		transList.add("1;2;5;");
		transList.add("2;4;");
		transList.add("2;3;");
		transList.add("1;2;4;");
		transList.add("1;3;");
		transList.add("2;3;");
		transList.add("1;3;");
		transList.add("1;2;3;5;");
		transList.add("1;2;3;");
	}

2.频繁项目集的生成过程，其中调用了方法getItem1FC( ),生成L1，递归调用getCandidateCollection()进行连接、剪枝生成C2、C3……，最后生成L2，L3……

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
java复制代码// 生成频繁项目集
	public Map<String, Integer> getFC() {
		// 声明哈希表，用来存放键值对，即项目和支持数对，所有的频繁集
		Map<String, Integer> frequentCollectionMap = new HashMap<String, Integer>();
		frequentCollectionMap.putAll(getItem1FC());
		Map<String, Integer> itemkFcMap = new HashMap<String, Integer>();
		itemkFcMap.putAll(getItem1FC());
		while (itemkFcMap != null && itemkFcMap.size() != 0) {
			Map<String, Integer> candidateCollection = getCandidateCollection(itemkFcMap);
			Set<String> ccKeySet = candidateCollection.keySet();

			// 对候选集项进行累加计数
			for (String trans : transList) {
				for (String candidate : ccKeySet) {
					boolean flag = true;// 用来判断交易中是否出现该候选项
					String[] candidateItems = candidate.split(ITEM_SPLIT);
					for (String candidateItem : candidateItems) {
						if (trans.indexOf(candidateItem + ITEM_SPLIT) == -1) {
							flag = false;
							break;
						}
					}
					if (flag) {
						Integer count = candidateCollection.get(candidate);
						candidateCollection.put(candidate, count + 1);
					}
				}
			}

			// 从候选集中找到符合支持度的频繁集项
			itemkFcMap.clear();
			for (String candidate : ccKeySet) {
				Integer count = candidateCollection.get(candidate);
				if (count >= SUPPORT) {
					itemkFcMap.put(candidate, count);
				}
			}
			frequentCollectionMap.putAll(itemkFcMap);
		}
		return frequentCollectionMap;
	}

3.根据Lk 进行连接、剪枝生成Ck+1(剪枝指对连接生成的c，判断它的k-子集是否属于Lk,不属于则剪枝去掉该c)

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
45
46
47
48
49
50
java复制代码private Map<String, Integer> getCandidateCollection(Map<String, Integer> itemkFcMap) {
		Map<String, Integer> candidateCollection = new HashMap<String, Integer>();
		Set<String> itemkSet1 = itemkFcMap.keySet();
		Set<String> itemkSet2 = itemkFcMap.keySet();
		for (String itemk1 : itemkSet1) {
			for (String itemk2 : itemkSet2) {
				String[] tmp1 = itemk1.split(ITEM_SPLIT);// 进行连接
				String[] tmp2 = itemk2.split(ITEM_SPLIT);
				String c = "";
				if (tmp1.length == 1) {
					if (tmp1[0].compareTo(tmp2[0]) < 0) {
						c = tmp1[0] + ITEM_SPLIT + tmp2[0] + ITEM_SPLIT;
					}
				} else {
					boolean flag = true;
					for (int i = 0; i < tmp1.length - 1; i++) {
						if (!tmp1[i].equals(tmp2[i])) {
							flag = false;
							break;
						}
					}
					if (flag && (tmp1[tmp1.length - 1].compareTo(tmp2[tmp2.length - 1]) < 0)) {
						c = itemk1 + tmp2[tmp2.length - 1] + ITEM_SPLIT;
					}
				}
				boolean hasInfrequentSubSet = false;// 进行剪枝
				if (!c.equals("")) {
					String[] tmpC = c.split(ITEM_SPLIT);
					for (int i = 0; i < tmpC.length; i++) {
						String subC = "";
						for (int j = 0; j < tmpC.length; j++) {
							if (i != j) {
								subC = subC + tmpC[j] + ITEM_SPLIT;
							}
						}
						if (itemkFcMap.get(subC) == null) {
							hasInfrequentSubSet = true;
							break;
						}
					}
				} else {
					hasInfrequentSubSet = true;
				}
				if (!hasInfrequentSubSet) {
					candidateCollection.put(c, 0);
				}
			}
		}
		return candidateCollection;
	}

4.L1的生成过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码private Map<String, Integer> getItem1FC() {
		Map<String, Integer> sItem1FcMap = new HashMap<String, Integer>();// 存放候选1项集
		Map<String, Integer> rItem1FcMap = new HashMap<String, Integer>();// 存放频繁1项集
		for (String trans : transList) {
			String[] items = trans.split(ITEM_SPLIT);
			for (String item : items) {
				Integer count = sItem1FcMap.get(item + ITEM_SPLIT);
				if (count == null) {
					sItem1FcMap.put(item + ITEM_SPLIT, 1);
				} else {
					sItem1FcMap.put(item + ITEM_SPLIT, count + 1);
				}
			}
		}
		Set<String> keySet = sItem1FcMap.keySet();
		for (String key : keySet) {
			Integer count = sItem1FcMap.get(key);
			if (count >= SUPPORT) {
				rItem1FcMap.put(key, count);
			}
		}
		return rItem1FcMap;
	}

5. 生成关联规则的过程

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
java复制代码public Map<String, Double> getRelationRules(Map<String, Integer> frequentCollectionMap) {
		Map<String, Double> relationRules = new HashMap<String, Double>();
		Set<String> keySet = frequentCollectionMap.keySet();
		for (String key : keySet) {
			double countAll = frequentCollectionMap.get(key);
			String[] keyItems = key.split(ITEM_SPLIT);
			if (keyItems.length > 1) {
				List<String> source = new ArrayList<String>();
				Collections.addAll(source, keyItems);
				List<List<String>> result = new ArrayList<List<String>>();
				buildSubSet(source, result);// 获得source的所有非空子集
				for (List<String> itemList : result) {
					if (itemList.size() < source.size()) {// 只处理真子集
						List<String> otherList = new ArrayList<String>();
						for (String sourceItem : source) {
							if (!itemList.contains(sourceItem)) {
								otherList.add(sourceItem);
							}
						}
						String reasonStr = "";// 前置
						String resultStr = "";// 结果
						for (String item : itemList) {
							reasonStr = reasonStr + item + ITEM_SPLIT;
						}
						for (String item : otherList) {
							resultStr = resultStr + item + ITEM_SPLIT;
						}
						double countReason = frequentCollectionMap.get(reasonStr);
						double itemConfidence = countAll / countReason;// 计算置信度
						if (itemConfidence >= CONFIDENCE) {
							String rule = reasonStr + CON + resultStr;
							relationRules.put(rule, itemConfidence);
						}
					}
				}
			}
		}
		return relationRules;
	}

6.对频繁项目集的所有子集生成关联规则

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
java复制代码private void buildSubSet(List<String> sourceSet, List<List<String>> result) {
		// 仅有一个元素时，递归终止。此时非空子集仅为其自身，所以直接添加到result中
		if (sourceSet.size() == 1) {
			List<String> set = new ArrayList<String>();
			set.add(sourceSet.get(0));
			result.add(set);
		} else if (sourceSet.size() > 1) {
			// 当有n个元素时，递归求出前n-1个子集，在于result中
			buildSubSet(sourceSet.subList(0, sourceSet.size() - 1), result);
			int size = result.size();// 求出此时result的长度,用于后面的追加第n个元素时计数
			// 把第n个元素加入到集合中
			List<String> single = new ArrayList<String>();
			single.add(sourceSet.get(sourceSet.size() - 1));
			result.add(single);
			// 在保留前面的n-1子集的情况下，把第n个元素分别加到前n个子集中，并把新的集加入到result中;
			// 为保留原有n-1的子集，所以需要先对其进行复制
			List<String> clone;
			for (int i = 0; i < size; i++) {
				clone = new ArrayList<String>();
				for (String str : result.get(i)) {
					clone.add(str);
					clone.add(sourceSet.get(sourceSet.size() - 1));
					result.add(clone);
				}
			}
		}

	}

7.主函数，调用getFC()输出频繁项目集，调用getCandidateCollection()生成存在强关联规则的项目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码public static void main(String[] args) {
		Apriori apriori = new Apriori();
		Map<String, Integer> frequentCollectionMap = apriori.getFC();
		System.out.println("--------------频繁项目集"+"--------------");
		Set<String> fcKeySet = frequentCollectionMap.keySet();
		for (String fcKey:fcKeySet){
			System.out.println(fcKey+" : "+frequentCollectionMap.get(fcKey));
		}
		Map<String, Double> relationRulesMap = apriori.getRelationRules(frequentCollectionMap);
		System.out.println("--------------存在强关联规则如下"+"--------------");
		Set<String> rrKeySet=relationRulesMap.keySet();
		for(String rrKey:rrKeySet){
			System.out.println(rrKey+" : "+relationRulesMap.get(rrKey));
		}
	}
}

运行结果：

image.png

二.利用weka工具对天气数据、美国国会议员投票信息、超市购物篮数据进行关联规则挖掘，并分析挖掘结果

<1>

image.png

image.png

选择Apriori

image.png

设置好各项参数

image.png

image.png

设置完成后点击start运行

image.png

image.png

Run information //实验运行信息

Scheme: weka.associations.Apriori //所选的关联规则挖掘方案：Apriori算法

-N 10 -T 0 -C 0.9 -D 0.05 -U 1.0 -M 0. 1 -S -1.0 -c -1

//各参数依次表示：

I - 输出项集，若设为false则该值缺省;

N 10 - 规则数为10;

T 0 – 度量单位选为置信度，(T1-提升度，T2杠杆率，T3确信度);

C 0.9 – 度量的最小值为0.9;

D 0.05 - 递减迭代值为0.05;

U 1.0 - 最小支持度上界为1.0;

M 0.1 - 最小支持度下届设为0.1;

S -1.0 - 重要程度为-1.0;

c -1 - 类索引为-1输出项集设为真

Relation:weather.symbolic //数据的名称weather.symbolic

Instances: 14 //数据的记录数 14

Attributes:5 //属性数目 5以及各属性名称

Apriori // Apriori算法运行结果

Minimum support: 0. 1 5 (2 instances) //最小支持度0.15，即最少需要2个实例

Minimum metric : 0.9 //最小度量<置信度>: 0.9

Number of cycles performed: 1 7 //进行了17轮搜索

Generated sets of large itemsets: //生成的频繁项集

Size of set of large itemsets L(1): 12 //频繁1项集：12个

Size of set of large itemsets L( 2 ): 47 //频繁2项集：47个

Size of set of large itemsets L( 3 ): 39 //频繁3项集：39个

Size of set of large itemsets L( 4 ): 6 //频繁4项集：6个

Best rules found: //最佳关联规则

1. outlook=overcast 4 ==> play=yes 4 conf:(1) lift:(1.56) lev:(0.1) [1] conv:(1.43)

//规则采用“前件 num.1 ==>结论 num.2”的形式表示，前件后面的数字表示有多少个实例满足前件，结论后的数字表示有多少个实例满足整个规则，这就是规则的”支持度“。

conf：置信度 lift：提升度 lev：杠杠率 conv：确信度

设置参数 outputItemSets 为 true，再次运行 Apriori 算法，会生成各频繁项目集及他们的支

持数如下：

image.png

<2>加载 vote.arff 数据集，该数据集中各属性含义如下：

image.png

切换至 Associate 标签页，选择 Apriori 算法，保持默认选项，单击 start 按钮，

结果如下：

image.png

参数解释如<1>一致

<3>加载 supermarket.arff 数据集

image.png

运行 Apriori 算法，结果如下：

image.png

解析如下：

第一条规则：饼干+冷冻食品+水果+高总额 ==> 面包和蛋糕

第二条规则：烘烤所需+饼干+水果+高总额 ==> 面包和蛋糕

第三条规则：烘烤所需+冷冻食品+水果+高总额 ==> 面包和蛋糕

第四条规则：饼干+水果+蔬菜+高总额 ==> 面包和蛋糕

第五条规则：聚会零食+水果+高总额 ==> 面包和蛋糕

第六条规则：饼干+冷冻食品+蔬菜+高总额 ==> 面包和蛋糕

第七条规则：烘烤所需+饼干+蔬菜+高总额 ==> 面包和蛋糕

第八条规则：饼干+水果+高总额 ==> 面包和蛋糕

第九条规则：冷冻食品+水果+蔬菜+高总额 ==> 面包和蛋糕

第十条规则：冷冻食品+水果+高总额 ==> 面包和蛋糕

可以发现

  1. 购买饼干或冷冻食品 ，会购买水果或蔬菜 （水果 8 条规则，蔬菜 4条规则）
  1. 购买饼干、冷冻食品 、水果、蔬菜，会购买面包、蛋糕（多条）
  1. 购买上述食品的，采购量会很大（金额高）（9条）
  1. 采购量会很大（金额高）的，一般会购买面包、蛋糕（10条规则都包含这两项）

总结：

Apriori算法需要完全的标称型数据，如果有数值型属性，必须先进行离散化。关联规则挖掘发现大量数据中项集之间有趣的关联或者相互联系。关联规则挖掘的一个典型例子就是购物篮分析，该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析出顾客的购买习惯，通过了解哪些商品频繁地被顾客同时买入，能够帮助零售商制定合理的营销策略。其可以揭示数据中隐藏的关联模式，帮助人们进行市场运作，决策支持等。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

字符串是 Java 中特殊的类，使用方法像一般的基本数据类型，被广泛应用在 Java 编程中。Java 没有内置的字符串类型，而是在标准 Java 类库中提供了一个 String 类来创建和操作字符串。

在 Java 中定义一个字符串最简单的方法是用双引号把它包围起来。这种用双引号括起来的一串字符实际上都是 String 对象，如字符串“Hello”在编译后即成为 String 对象。因此也可以通过创建 String 类的实例来定义字符串。

不论使用哪种形式创建字符串，字符串对象一旦被创建，其值是不能改变的，但可以使用其他变量重新赋值的方式进行更改。

想了解更多更详细的Java基础知识可以看以下的视频学习哦~

全新的Java300集课程来啦！java零基础小白自学Java必备优质教程，让学习成为一种享受

一、直接定义字符串

直接定义字符串是指使用双引号表示字符串中的内容，例如“Hello Java”、“Java 编程”等。具体方法是用字符串常量直接初始化一个 String 对象，示例如下：

1
2
3
ini复制代码String str = "Hello Java";
String str;
str = "Hello Java";

举例说明：

1
2
3
4
5
6
7
ini复制代码String str = "我是一只小小鸟"; // 结果：我是一只小小鸟
String word;
word = "I am a bird"; // 结果：I am a bird
word = "<h1>to fly</h1>"; // 结果：<h1>to fly</h1>
word = "Let's say that it's true"; // 结果：Let's say that it's true
System.out.println(word);
word = "北京\上海\广州"; // 结果：北京\上海\广州

二、使用 String 类定义

String 类的构造方法有多种重载形式，每种形式都可以定义字符串。下面介绍最常用的几种形式。

1. String()

初始化一个新创建的 String 对象，表示一个空字符序列。

2. String(String original)

初始化一个新创建的 String 对象，使其表示一个与参数相同的字符序列。换句话说，新创建的字符串是该参数字符串的副本。例如：

1
2
ini复制代码String str1 = new String("Hello Java");
String str2 = new String(str1);

这里 str1 和 str2 的值是相等的。

3. String(char[ ]value)

分配一个新的字符串，将参数中的字符数组元素全部变为字符串。该字符数组的内容已被复制，后续对字符数组的修改不会影响新创建的字符串。例如：

1
2
3
arduino复制代码char a[] = {'H','e','l','l','0'};
String sChar = new String(a);
a[1] = 's';

上述 sChar 变量的值是字符串“Hello”。 即使在创建字符串之后，对 a 数组中的第 2 个元素进行了修改，但未影响 sChar 的值。

4. String(char[] value,int offset,int count)

分配一个新的 String，它包含来自该字符数组参数一个子数组的字符。offset 参数是子数组第一个字符的索引，count 参数指定子数组的长度。该子数组的内容已被赋值，后续对字符数组的修改不会影响新创建的字符串。例如：

1
2
3
arduino复制代码char a[]={'H','e','l','l','o'};
String sChar=new String(a,1,4);
a[1]='s';

上述 sChar 变量的值是字符串“ello”。该构造方法使用字符数组中的部分连续元素来创建字符串对象。offset 参数指定起始索引值，count 指定截取元素的个数。创建字符串对象后，即使在后面修改了 a 数组中第 2 个元素的值，对 sChar 的值也没有任何影响。

三、Java学习视频

【Java300集】全新的Java300集来啦！java零基础小白自学Java必备优质教程

花2万多买的Java教程全套，现在分享给大家，入门到精通！Java300集_Java程序开发就业教程

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%