数量级
常见延迟
服务端有常见的10k问题，即当输入数量级达到10k的级别是，会对程序有着相当大的考验
L1 cache reference ......................... 0.5 ns
Branch mispredict ............................ 5 ns
L2 cache reference ........................... 7 ns
Mutex lock/unlock ........................... 25 ns
Main memory reference ...................... 100 ns
Compress 1K bytes with Zippy ............. 3,000 ns = 3 µs
Send 2K bytes over 1 Gbps network ....... 20,000 ns = 20 µs
SSD random read ........................ 150,000 ns = 150 µs
Read 1 MB sequentially from memory ..... 250,000 ns = 250 µs
Round trip within same datacenter ...... 500,000 ns = 0.5 ms
Read 1 MB sequentially from SSD* ..... 1,000,000 ns = 1 ms #Assuming ~1GB/sec SSD
Disk seek ........................... 10,000,000 ns = 10 ms
Read 1 MB sequentially from disk .... 20,000,000 ns = 20 ms
Send packet CA->Netherlands->CA .... 150,000,000 ns = 150 ms
棋盘上的谷粒
国际象棋有8x8个格子，传说国际象棋是由一位印度数学家发明的。国王十分感谢这位数学家，于是就请他自己说出想要得到什么奖赏。这位数学家想了一分钟后就提出请求——把1粒米放在棋盘的第1格里，2粒米放在第2格，4粒米放在第3格，8粒米放在第4格，依次类推，每个方格中的米粒数量都是之前方格中的米粒数量的2倍。国王欣然应允，诧异于数学家竟然只想要这么一点的赏赐。
那么实际结果:2^64 - 1, (64位无符号2进制数每一位都是1)
一粒谷子大约:6.4799e-5(kg)
总重量大约：16 * 6.4799 后面加上10个0(吨)
CPU频次
假设一台现代电脑CPU主频3.1Ghz，那么CPU持续工作一年，大约3 * 10^9 * 86400 * 365 = 9.4608e+16, 要达到2^64，需要大约195台电脑
N的阶层
20! < 2 ^ 64 < 21!
复利的力量
如果每天进步%1，那么多少天能够大于2^64呢？
如果每天进步%5，%10呢？
math.log(2 ** 64, 1.01) ≈ 4458
math.log(2 ** 64, 1.05) ≈ 909
math.log(2 ** 64, 1.1) ≈ 465
整数表示
计算机中参与运算的数都是用二进制表示的，也叫位数组bit-array
内存表示是有endian的，所以符号为不一定是最“左边”
正数表示
正数和零的表示法与其二进制写法相同，只是左边要补符号位0
8位二进制表示数字时:
例如5的二进制是 = 101
可以表示为 0000 0101
解析时：
最左边0表示非负数
000 0101 = 5
加上符号位 = +5
负数表示(补码)
负数的表示法，首先是将其绝对值安位取反，然后+1
8位二进制表示数字时:
如上，-5的绝对值二进制是 = 0000 0101
安位取反 = 1111 1010
+1之后 = 1111 1011
解析时：
最左边1表示负数
安位取反 = 000 0100
+1之后 = 000 0101
加上符号位-5
同样的内容，如果当成unsigned int解析 = 251
2147483647
面对这样的数字存在10种人，第一种能像圆周率一样背下来，第二种就是一脸懵逼。那为什么它很重要呢，这个数字是32位有符号int能存储的最大值，即2^31 - 1。 范围是[-2^31, 2^31 - 1], 其中0占据了正数的一个位置，所以正数少一个，负数多一个。
- 这里的10种人，是2进制表示法
2^31 - 1 = 2147483647, 这是32-bit整数最大能表示的数字
位运算
# 0s 和 1s 分别表示只由 0 或 1 构成的二进制数字
x ^ 0s = x
x ^ 1s = ~x
x ^ x = 0
x ^ (~x) = 1s
a ^ b = c; a ^ c = b; b ^ c = a; #swap
x & 0s = 0
x & 1s = 1
x & x = x
x | 0s = x
x | 1s = 1s
x | x = x
n & (n - 1) 消掉最低位的一个1
n & (-n) 得到最低位的那个1 # -n = ~n + 1
最大公因数
# 欧几里得算法计算最大公约数
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
我们来找出 48 和 18 的最大公约数：
- 将 48 除以 18，余数是 12。
- 将 18 除以 12，余数是 6。
- 将 12 除以 6，余数是 0。
因为余数现在是 0，所以最大公约数是最后一个非零的余数，即 6。
可以用GCD来简化分子和分母分数表示，比如6/8, (6/gcd)/(8/gcd) = 3/4
最小公倍数
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
return a * b // gcd(a, b)
48 和 18 的最大公约数=6
- 48 的倍数有：48, 96, 144, 192, …
- 18 的倍数有：18, 36, 54, 72, 90, 108, 126, 144, …
最小公倍数 = 48 * 18 / 6 = 144
贝祖等式
# ax + by = gcd(a, b)
def xgcd(a, b):
if b == 0:
return a, 1, 0
gcd, x1, y1 = xgcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
质数
# 埃拉托斯特尼筛法
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
prime = [True for i in range(n)]
count = n - 2 # 去掉0和1
for i in range(2, int(n ** 0.5) + 1): # 乘法的对称性, [1x10 2x5 5x2 10x1]
if prime[i]:
for j in range(i * i, n, i):
# 所有>1的自然数都可以分写成质数的乘积, 对于 k * i (k < i)的部分已经被标记过,
# 例如7x7的[2x7, 3x7, 4x7=2x14, 5x7, 6x7=2x21]分别被2，3，5标记过
if prime[j]:
prime[j] = False
count -= 1
return count
此外，偶数是不用判断的，可以直接跳过
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
prime = [True for i in range(n)] #保留偶数空间，使代码更清晰些
count = n // 2 - 1 # 去掉偶数 和 1
for i in range(3, int(n ** 0.5) + 1, 2):
if prime[i]:
for j in range(i * i, n, 2 * i): #step = 2倍的i, 质数 x 质数 = 奇数(2除外)
if prime[j]:
prime[j] = False
count -= 1
return count + 1 # 加上2
进制转换
class Solution:
def convertToBase7(self, num: int) -> str:
if num == 0:
return "0"
res = ""
sign = "" if num > 0 else "-"
num = abs(num)
while num > 0:
d = num % 7
num = num // 7
res = str(d) + res
return sign + res
概率
权重概率
# 前缀和 + 二分查找
import random
class Solution:
def __init__(self, w: List[int]):
self.prefix = []
cur = 0
for x in w:
cur += x
self.prefix.append(cur)
def pickIndex(self) -> int:
t = random.randint(1, self.prefix[-1])
return self.lower_bound(t)
def lower_bound(self, t:int) -> int:
left = 0
right = len(self.prefix)
while left < right:
mid = left + (right - left) // 2
if self.prefix[mid] < t:
left = mid + 1
else:
right = mid
return left
水库采样
总数量n，要求选择k个，每个被选中的概率是k / n, k = 1时是个特例
做法:
- 先选择
k个 - 第
k+1个，人为控制k/(k+1)为选中概率，并随机替换掉上面k中的一个 - 第
k+m个，人为控制k/(k+m)为选中概率，并随机替换掉上面k中的一个, 直到结束
证明:
对于已经选中的K个，它被M替换掉的概率:
$ P(替换) = P(第m个被选中) * P(选中的m恰好替换了k中的它) = \frac{k}{k + m} \times \frac{1}{k} $
$ P(替换) = \frac{1}{k + m} $
$ P(存在) = 1 - P(替换) = \frac{k + m - 1}{k + m} $
对于选中的K, 它存在的概率就是从来没有被替换过，m = 1, 2, 3, 4
$ P = \frac{k}{k + 1} \times \frac{k + 1}{k + 2} \times \frac{k + 2}{k + 3} … \frac{n - 1}{n} = \frac{k}{n}$
对于未先选中的第m个:
$ P(m被选中) = \frac{k}{k + m} $
$ P(m’存在) = 1 - P(替换) = \frac{k + m - 1}{k + m} \hspace{1em}(m > m’)$
它存在的概率是，m被选中并且m之后的都没有替换掉m
$ P(m) = \frac{k}{k + m} \times \frac{k + m}{k + m + 1} \times \frac{k + m + 1}{k + m + 2} … \frac{n - 1}{n} = \frac{k}{n} $
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import random
class Solution:
def __init__(self, head: Optional[ListNode]):
self.head = head
def getRandom(self) -> int:
node = self.head
res = node
i = 1
while node.next is not None:
if (random.randint(0, i) == 0): # 1/2, 1/3, 1/4 ...
res = node.next
i += 1
node = node.next
return res.val
拒绝采样
拒绝采样（Rejection Sampling）是一种从复杂分布中生成样本的统计方法，特别是在目标分布难以直接采样时使用。利用一个简单的分布来生成候选样本，然后根据某个接受概率来决定是否接受这些候选样本
# 40 ~ 48 都被拒绝了，如果拒绝的数量太多，效率就非常低下了
class Solution:
def rand10(self):
"""
:rtype: int
"""
res = 40
while res >= 40:
res = 7 * (rand7() - 1) + rand7() - 1
return res % 10 + 1
–End–