西维蜀黍

【Java】源码 - BitSet

什么是BitSet?

BitSet类实现了一个按需增长的位向量。位Set的每一个组件都有一个boolean值。用非负的整数将BitSet的位编入索引。可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作,可以使用一个 BitSet修改另一个 BitSet的内容。

默认情况下,set 中所有位的初始值都是false。

每个位 set 都有一个当前大小,也就是该位 set 当前所用空间的位数。注意,这个大小与位 set 的实现有关,所以它可能随实现的不同而更改。位 set 的长度与位 set 的逻辑长度有关,并且是与实现无关而定义的。

BitSet的索引范围从 0 到 nbits-1 。

  ...


【Algorithm】动态规划 - 背包问题

主要分类

0-1背包

每个物品只能取一次

Leetcode:

  • Leetcode 474. Ones and Zeroes(01背包)

爆搜解法

用 4 个 bit 分别标识 4 种物品,取还是不取。

贪心法 - 错误解

所有的贪心,都是错误的!!!

反例:

取价值最高

m=2, A = [1, 1, 2], V = [2, 2, 3] •

贪心答案:3,正确答案:4

取重量最轻

m=2, A = [1, 1, 2], V = [1, 1, 3]

贪心答案:2,正确答案

取单位价值最高

m=3, A = [1, 1, 3], V = [2, 2, 5]

贪心答案:4,正确答案:5

爆搜算法的局限

  ...


【Linux】磁盘管理

df

df命令参数功能:检查文件系统的磁盘空间占用情况。可以利用该命令来获取硬盘被占用了多少空间,目前还剩下多少空间等信息。

语法:

$ df [-ahikHTm] [目录或文件名]

选项与参数:

  • -a :列出所有的文件系统,包括系统特有的 /proc 等文件系统;
  • -k :以 KBytes 的容量显示各文件系统;
  • -m :以 MBytes 的容量显示各文件系统;
  • -h :以人们较易阅读的 GBytes, MBytes, KBytes 等格式自行显示;
  • -H :以 M=1000K 取代 M=1024K 的进位方式;
  • -T :显示文件系统类型, 连同该 partition 的 filesystem 名称 (例如 ext3) 也列出;
  • -i :不用硬盘容量,而以 inode 的数量来显示

列出系统内所有的文件系统

$ df
Filesystem      1K-blocks      Used Available Use% Mounted on
/dev/hdc2         9920624   3823112   5585444  41% /
/dev/hdc3         4956316    141376   4559108   4% /home
/dev/hdc1          101086     11126     84741  12% /boot
tmpfs              371332         0    371332   0% /dev/shm

在 Linux 底下如果 df 没有加任何选项,那么默认会将系统内所有的 (不含特殊内存内的文件系统与 swap) 都以 1 Kbytes 的容量来列出来!

  ...


【Python】线程 - 协程(Coroutine)

协程(Coroutine)

协程,又称微线程,纤程。英文名Coroutine,这其实是corporate routine的缩写,直接翻译为协同的例程。

协程的概念很早就提出来了,但直到最近几年才在某些语言(如Lua)中得到广泛应用。

子程序,或者称为函数,在所有语言中都是层级调用,比如A调用B,B在执行过程中又调用了C,C执行完毕返回,B执行完毕返回,最后是A执行完毕。

所以子程序调用是通过栈实现的,一个线程就是执行一个子程序。

子程序调用总是一个入口,一次返回,调用顺序是明确的。而协程的调用和子程序不同。

协程看上去也是子程序,但执行过程中,在子程序内部可中断,然后转而执行别的子程序,在适当的时候再返回来接着执行。

注意,在一个子程序中中断,去执行其他子程序,不是函数调用,有点类似CPU的中断。比如子程序A、B:

def A():
    print '1'
    print '2'
    print '3'

def B():
    print 'x'
    print 'y'
    print 'z'

假设由协程执行,在执行A的过程中,可以随时中断,去执行B,B也可能在执行过程中中断再去执行A,结果可能是:

1
2
x
y
3
z

但是在A中是没有调用B的,所以协程的调用比函数调用理解起来要难一些。

看起来A、B的执行有点像多线程,但协程的特点在于是一个线程执行,那和多线程比,协程有何优势?

最大的优势就是协程极高的执行效率。因为子程序切换不是线程切换,而是由程序自身控制,因此,没有线程切换的开销,和多线程比,线程数量越多,协程的性能优势就越明显。

第二大优势就是不需要多线程的锁机制,因为只有一个线程,也不存在同时写变量冲突,在协程中控制共享资源不加锁,只需要判断状态就好了,所以执行效率比多线程高很多。

因为协程是一个线程执行,那怎么利用多核CPU呢?最简单的方法是多进程+协程,既充分利用多核,又充分发挥协程的高效率,可获得极高的性能。


总结来说,协程由于由程序主动控制切换,没有线程切换的开销,所以执行效率极高。对于I/O密集型任务非常适用,如果是CPU密集型,推荐多进程+协程的方式。

  ...


【Python】Python Global Interpreter Lock (GIL)

Python Global Interpreter Lock (GIL)

The Python Global Interpreter Lock or GIL, in simple words, is a mutex (or a lock) that allows only one thread to hold the control of the Python interpreter.

This means that only one thread can be in a state of execution at any point in time. The impact of the GIL isn’t visible to developers who execute single-threaded programs, but it can be a performance bottleneck in CPU-bound and multi-threaded code.

  ...


【Python】线程 - Python 的单线程

Python 中的伪多线程

实验

如果你不幸拥有一个多核CPU,你肯定在想,多核应该可以同时执行多个线程。

如果写一个死循环的话,会出现什么情况呢?

打开Mac OS X的Activity Monitor,或者Windows的Task Manager,都可以监控某个进程的CPU使用率。

我们可以监控到一个死循环线程会100%占用一个CPU。

如果有两个死循环线程,在多核CPU中,可以监控到会占用200%的CPU,也就是占用两个CPU核心。

要想把N核CPU的核心全部跑满,就必须启动N个死循环线程。

  ...


【Python】Python 几种常用的测试框架

常见的测试框架

1 Unittest

unittest是Python内置的标准类库。它的API跟Java的JUnit、.net的NUnit,C++的CppUnit很相似。

通过继承unittest.TestCase来创建一个测试用例。

具体请参考文档

举个例:

import unittest

def fun(x):
    return x + 1

class MyTest(unittest.TestCase):
    def test(self):
        self.assertEqual(fun(3), 4)
  ...


【Distributed System】高并发(High Concurrency)

Design Levels

Consistency Models

Scalability

  • vertical scalability
  • horizential scalability
  ...


【Architecture】中台概念

中台

提到中台,最常听到的一个词就是「能力」。可能是因为能力这个词足够简单,又有着足够的包容度与宽度。

企业的能力可能包含多个维度,常见的例如计算能力,技术能力,业务能力,数据能力,AI能力,运营能力,研发能力……其中大部分的能力还可以继续细化和二次展开,从而形成一张多维度的企业能力网。

可以说,中台就是企业所有可以被「多前台产品团队」复用能力的载体。

根据中台的类型,可以分为以下几种:

  • 数据中台
  • 业务中台
    • 中台就是微服务业务平台,像最常见的用户中心,订单中心,人们都叫它“业务中台”。
  • 技术中台
    • 中台就是技术平台,像微服务开发框架、Devops平台、PaaS平台,容器云之类的,人们都叫它“技术中台”。
  • 组织中台
    • 中台应该是组织的事情,在释放潜能:类似于企业内部资源调度中心和内部创新孵化组织,人们叫它**“组织中台”**。
  ...


【Algorithm】算法思想 - 分治算法(Divide and Conquer)

分治算法

基本概念

在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)……

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算。n=2时,只要作一次比较即可排好序。n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

基本思想及策略

分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

  ...