极客算法

算法 - 数理与概率Math

2024-07-26

数量级

常见延迟

服务端有常见的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占据了正数的一个位置,所以正数少一个,负数多一个。

  1. 这里的10种人,是2进制表示法
  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 的最大公约数:

  1. 将 48 除以 18,余数是 12。
  2. 将 18 除以 12,余数是 6。
  3. 将 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时是个特例

做法:

  1. 先选择k
  2. k+1个,人为控制k/(k+1)为选中概率,并随机替换掉上面k中的一个
  3. 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–


评论

内容:
其他: