西维蜀黍

【Network】IPv4 地址

  ...


【Algorithm】算法思想 - 二分法(Dichotomy)

二分法题型一

二分位置 之 OOXX,一般会给你一个数组,让你找数组中第一个/最后一个满足某个条件的位置:OOOOOOO…OOXX….XXXXXX。

  • Leetcode - 278 First Bad Version
  • Lintcode - 159 Find Minimum in Rotated Sorted Array
  • Leetcode - 74 Search a 2D Matrix
  • Lintcode - 61 Search for a Range
  ...


【Markdown】Markdown 使用中 HTML

  ...


【Java】运算符 - 乘法除法问题

移位实现特殊乘除法运算

当一个数乘以或者除以 2 的整数倍时,比如:

a = a * 4;
b = b / 4;

可以优化为:

a = a << 2;
b = b >> 2;

说明:

除以2 = 右移1位 乘以2 = 左移1位 除以4 = 右移2位 乘以4 = 左移2位 除以8 = 右移3位 乘以8 = 左移3位 … …


System.out.println(66 /64);  //1
System.out.println(66 >> 6); //1
  ...


【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个死循环线程。

  ...