跳至主要内容

Python 中的随机数

python 中的随机数
代码参考 /python/cpython/Lib/random.py
/moudles/_randommodule.c
python version: 3.7

random.randint 与 random.randrange

python 中 randint 与 randrange 这两个函数是很常用的函数
所以来看一下,python 中是如何实现的
randint 本质上是 randrange(a, a+1),所以只要来看 randrange 就可以了
randrange(self, start, stop=None, step=1, _int=int)
_int 用来尝试 将 start stop step 强制转换成 int
randrange 中用来处理数据格式与进行异常的抛出
然后返回 istart + istep*self._randbelow(n)

_randbelow

_randbelow(self, n, int=int, maxsize=1<<BPF, type=type,Method=_MethodType, BuiltinMethod=_BuiltinMethodType)
当 radom 函数没有被重写的时候,或者实现了新的的 getrandbits 函数时候,会使用新的函数来生成随机数
k = n.bit_length()
r = getrandbits(k)       
while r >= n:
    r = getrandbits(k)
return r
BPF=53; python 中 float 包含的字节数为 53 所以 maxsize 是将 1 向左移动 53 位即 2 的 53 次幂
9007199254740992
random 函数被重写,但是没有新的 getrandbits 函数的时候,只能使用 random 来实现
rem = maxsize % n
limit = (maxsize - rem) / maxsize
r = random()
while r >= limit:
    r = random()
return int(r*maxsize) % n

getrandbits

当 k <= 32 的时候
return PyLong_FromUnsignedLong(genrand_int32(self) >> (32 - k));
当 k > 32 的时候
words = (k - 1) / 32 + 1;
wordarray = (uint32_t *)PyMem_Malloc(words * 4);
if (wordarray == NULL) {
    PyErr_NoMemory();
    return NULL;
}
#if PY_LITTLE_ENDIAN
for (i = 0; i < words; i++, k -= 32)
#else
for (i = words - 1; i >= 0; i--, k -= 32)
#endif
{
    r = genrand_int32(self);
    if (k < 32)
        r >>= (32 - k);  /* Drop least significant bits */
    wordarray[i] = r;
}

result = _PyLong_FromByteArray((unsigned char *)wordarray, words * 4,
                               PY_LITTLE_ENDIAN, 0 /* unsigned */);
PyMem_Free(wordarray);
return result;
genrand_int32
genrand_int32(RandomObject *self)
{
    uint32_t y;
    static const uint32_t mag01[2] = {0x0U, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */
    uint32_t *mt;

    mt = self->state;
    if (self->index >= N) { /* generate N words at one time */
        int kk;

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];

        self->index = 0;
     }

    y = mt[self->index++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680U;
    y ^= (y << 15) & 0xefc60000U;
    y ^= (y >> 18);
    return y;
}
`
上面的代码就是梅森旋转算法的具体实现,有时间单独写一篇关于梅森旋转算法的 blog 好了

random.choice

 def choice(self, seq):
    """Choose a random element from a non-empty sequence."""
    try:
        i = self._randbelow(len(seq))
    except ValueError:
        raise IndexError('Cannot choose from an empty sequence') from None
    return seq[i]
这样看来 choice 也是使用 _randbelow 来生成一个数字,再返回

random.choices

choices 是 python3.6 中新加入的函数
 def choices(self, population, weights=None, *, cum_weights=None, k=1):
    """Return a k sized list of population elements chosen with replacement.

    If the relative weights or cumulative weights are not specified,
    the selections are made with equal probability.

    """
    random = self.random
    if cum_weights is None:
        if weights is None:
            _int = int
            total = len(population)
            return [population[_int(random() * total)] for i in range(k)]
        cum_weights = list(_itertools.accumulate(weights))
    elif weights is not None:
        raise TypeError('Cannot specify both weights and cumulative weights')
    if len(cum_weights) != len(population):
        raise ValueError('The number of weights does not match the population')
    bisect = _bisect.bisect
    total = cum_weights[-1]
    return [population[bisect(cum_weights, random() * total)] for i in range(k)]

random

static PyObject *
random_random(RandomObject *self)
{
uint32_t a=genrand_int32(self)>>5, b=genrand_int32(self)>>6;
return PyFloat_FromDouble((a*67108864.0+b)*(1.0/9007199254740992.0));
}

bisect

bisect 模块是一个专门使用二分查找进行列表查找的算法,前提是列表有序;
这里用来使累积权重转换成一个随机的 index
所以,choices 在使用的时候可能会在返回的列表中有同一个元素
如果不想在返回的列表中有相同的元素可以使用:sample

sample

 def sample(self, population, k):
    if isinstance(population, _Set):
        population = tuple(population)
    if not isinstance(population, _Sequence):
        raise TypeError("Population must be a sequence or set.  For dicts, use list(d).")
    randbelow = self._randbelow
    n = len(population)
    if not 0 <= k <= n:
        raise ValueError("Sample larger than population or is negative")
    result = [None] * k
    setsize = 21        # size of a small set minus size of an empty list
    if k > 5:
        setsize += 4 ** _ceil(_log(k * 3, 4)) # table size for big sets
    if n <= setsize:
        # An n-length list is smaller than a k-length set
        pool = list(population)
        for i in range(k):         # invariant:  non-selected at [0,n-i)
            j = randbelow(n-i)
            result[i] = pool[j]
            pool[j] = pool[n-i-1]   # move non-selected item into vacancy
    else:
        selected = set()
        selected_add = selected.add
        for i in range(k):
            j = randbelow(n)
            while j in selected:
                j = randbelow(n)
            selected_add(j)
            result[i] = population[j]
    return result

评论

发表评论

此博客中的热门博文

在 LSF 中使用 docker 运行任务

LSF + Docker Table of Contents 1. 环境信息 2. 修改配置文件在 lsf 上启用 docker 3. 验证 4. 部署常见问题 5. 部署参考链接 1  环境信息 docker 18.09.5 Kernel Version: 3.10.0-862.11.6.el7.x86_64 lsf 10.1.0.6 OS CentOs 7.6.1810 2  修改配置文件在 lsf 上启用 docker 1.conf/lsf.conf 添加/修改 LSF_PROCESS_TRACKING=Y LSF_LINUX_CGROUP_ACCT=Y LSB_RESOURCE_ENFORCE="cpu memory" 2.conf/lsf.shared 添加 docker Boolean () () (Docker container) 3.conf/lsf.cluster 添加 $your-host-name ! ! 1 3.5 () () (docker) 4./conf/lsbatch/$clustername/configdir/lsb.applications 添加 Begin Application NAME = app1 CONTAINER = docker[image(ubuntu:latest) options(--rm --network=host --ipc=host -v /etc/passwd:/etc/passwd -v /etc/group:/etc/group) starter(root)] DESCRIPTION = Test Docker Application Profile 1 End Application 5.badmin reconfig 验证是否可用 3  验证 在非 root 用户下, bsub -app app1 -I cat /etc/lsb-release DISTRIB_ID=Ubuntu DISTRIB_RELEASE=18.04 DISTRIB_CODENAME=bionic DISTRIB_DES

Python 中的 UUID

python 中的 uuid 代码参考 cpython/Lib/uuid.py 版本 3.7 什么是 UUID UUID 的全称是 Universal Unique Identifier,中文名是 通用唯一标识符; wikipedia 上 UUID 的定义是 a 128-bit number used to identify information in computer systems UUID 需要满足两个条件: 128 bit 具有标识别计算机系统的能力 UUID 的规则 格式 将 16 个 8 位字节表示成 32 个十六进制数 按照 8-4-4-4-12 的格式加上 4 个连字符 “-‘ 版本 UUID 应该是下面的这种格式 xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx 其中 M 开始的 4 位表示版本,N 开始的 4 位表示变种 Name                        Length(bytes)    Length(hex digits)                       Contents time_low                         4                             8                  integer giving the low 32 bits of the time time_mid                         2                             4                  integer giving the middle 16 bits of the time| time_hi_and_version      2                              4                  4-bit “version” in the most significant bits,                                                                                               fol

k8s 源码阅读 -- eviction

Table of Contents 1. 前言 2. 资料 3. 代码详解 3.1. 代码参考 3.2. 详细 1  前言 在某些情况下 k8s 会出现 evicted 的 pod, 然而这并不在  pod 的生命周期 中.这就是 k8s 的驱逐机制。 当机器的一些资源(内存、磁盘)过小时,为了保证 node 不会受到影响,会将 pod 驱逐至其他的机器上 2  资料 可以在  这里看到相关资料 来看一下代码中,驱逐策略是怎样实现的 3  代码详解 3.1  代码参考 kubernetes release-1.10 3.2  详细 pkg/kubelet/apis/kubeletconfig/v1beta/default.go 定义了这几个默认值作为阈值 pkg/kubelet/kubelet.go kubelte 初始化了 eviction manager 在 runtime 相关模块被加载时,eviction manager 被加载进来 开始了 evict 相关的控制循环 接下来是 evict 真正工作的代码 代码目录是 pkg/kubelet/eviction/ 主要看该目录下的两个文件 eviction manager.go  helpers.go pkg/kubelet/eviction/eviction manager.go Start 是 evict manager 的入口 这里是一个死循环 循环中的主要函数是 synchronize 用来清理 pod、同步信息。这个就是今天的主角 先看一下 synchronize 的参数 diskInfoProvider podFunc diskInfoProvider 是一个接口,用来提供磁盘的信息,作为是否发生驱逐的依据。实际函数在  pkg/kubelet/stats/  下 synchronize 中仅用到了 HasDedicatedImageFs podFunc 用来获取一个待检查的 pod 列表,实际函数在 pkg/kubelet/kubelet pods.go 首先检查 imagesfs, 数据从 cadvisor 中获取 获得容器