跳至主要内容

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

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 中获取 获得容器

kubernetes cloud controller manager

kubernetes cloud controller manager Table of Contents 1. 什么是 cloud controller manager(ccm) 2. 能用 ccm 干什么 2.1. 现有的 ccm 2.1.1. In Tree 2.1.2. Out of Tree 3. 如何实现一个 ccm 4. ccm 背后的秘密 4.1. Out of Tree ccm 如何工作 5. 参考链接 本文所有代码基于 1.16.0-alpha.2 commit: bdde11a664 所以引用文档版本为 1.15.0 1  什么是 cloud controller manager(ccm) 在说 ccm 之前要了解一个 ccm 的前身 – cloud provider cloud provider 是为了 k8s 更加容易在公有云环境下而提出的一个方案 比如在 aws azure 等环境下可以让 k8s 的资源与云厂商的资源进行匹配 具体的演进路线等可以阅读  这篇文章 2  能用 ccm 干什么 在思索 ccm 可以做什么时,要思考一个问题:kubernetes 的核心价值在于哪里? 云主机厂商的本质上是在售卖计算资源与服务,而 k8s 的价值是在于管理与调度容器 正如 k8s 描述的一样: Production-Grade Container Scheduling and Management k8s 更加关心容器的调度与管理,其他的资源也都是为了容器而服务的 那么有什么资源对于 k8s 来说是可以被替代的? 负载均衡、路由、主机 k8s 不关心主机是实际在东京还是西雅图,也不关心负载均衡具体是如何实现的 它只需要主机上的 kubelet 在正常运行,可以通过负载均衡访问到暴露的服务 而这些恰恰是云厂商最为关心的事情,主机的配置、主机的位置、负载均衡的实现、路由如何到达 这时候再来看 ccm 的接口 LoadBalancer() (LoadBalancer, bool) Instances() (Instances, bool) Zones() (Zones, bool) Clusters() (Clusters, bool) Routes(