GraphSampling/Alia_Sample.py at master · chriszhao13/GraphSampling · GitHub

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import random

import numpy as np

# @author: Chris 2023/02/14
# 总结： 1. 别名表 2. 两次投掷
# 1. Get PDF Table
prob_num = 4
transform_prob = []
for i in range(prob_num):
    transform_prob.append(random.random())
print("归一化前： ", transform_prob)
norm_const = sum(transform_prob)

normalized_prob = [round(float(u_prob) / norm_const, 2) for u_prob in transform_prob]

print("归一化后：", normalized_prob, sum(normalized_prob))

# 2. *N and bucket in Big or small

length = prob_num

accept, alias = [0] * length, [0] * length

small, big = [], []

transform_N = np.array(normalized_prob) * length

print("归一化 * N 后：", transform_N)

for i, pro in enumerate(transform_N):
    if pro < 1.0:
        small.append(i)
    else:
        big.append(i)

print("small: ", small)
print("big: ", big)

# 3. 补齐

print("Start_________________________")
i = 0
while small and big:
    # 各出一个元素
    i = i + 1
    print("**************************")
    print("epoch : ", i)
    small_idx, large_idx = small.pop(), big.pop()
    # 小的 概率为 prob对应位置的 值
    accept[small_idx] = transform_N[small_idx]
    # 大的 索引放入
    alias[small_idx] = large_idx
    # 大的补 小的
    transform_N[large_idx] = transform_N[large_idx] - (1 - transform_N[small_idx])

    # 如果大的还是大于1 就放回大的 小于1 就放到小的

    if transform_N[large_idx] < 1.:
        small.append(large_idx)
    else:
        big.append(large_idx)
    print("small_id: ", small_idx)
    print("large_id: ", large_idx)
    print("accept: ", accept)
    print("alias: ", alias)
    print("transpose: ", transform_N)

while big:
    large_idx = big.pop()
    accept[large_idx] = 1
while small:
    small_idx = small.pop()
    accept[small_idx] = 1


def alias_sample(accept, alias):
    N = len(accept)
    # 生成随机索引 整数 1 到 N
    i = int(np.random.random() * N)
    # 生成0-1随机数
    r = np.random.random()
    if r < accept[i]:
        return i
    else:
        return alias[i]


# 模拟 10000 次
# 结果抽样分布 近似 原始分布！！！！！
all_sample = {}

for i in range(10000):
    sample = alias_sample(accept, alias)
    if sample not in all_sample:
        all_sample[sample] = 0
    all_sample[sample] += 1

k = list(range(4))

v = [all_sample[key]  for key in k]
x = np.array(v) / sum(v)
import matplotlib.pyplot as plt

plt.title("PDF")
plt.bar(k, x)
plt.show()