跳至主要内容

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 Contents1. 环境信息2. 修改配置文件在 lsf 上启用 docker3. 验证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_DESCRIPTION="Ubuntu 18.04.2 LTS" 4 部署常见问题 1.badmin reconfig 出现 …

k8s 源码阅读 -- eviction

Table of Contents1. 前言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/
主要看该目录下的两个文件 evictionmanager.go helpers.go
pkg/kubelet/eviction/evictionmanager.go
Start 是 evict manager 的入口
这里是一个死循环
循环中的主要函数是 synchronize 用来清理 pod、同步信息。这个就是今天的主角
先看一下 synchronize 的参数 diskInfoProvider podFunc
diskInfoProvider 是一个接口,用来提供磁盘的信息,作为是否发生驱逐的依据。实际函数在 pkg/kubelet/stats/ 下
synchronize 中仅用到了 HasDedicatedImageFs
podFunc 用来获取一个待检查的 pod 列表,实际函数在 pkg/kubelet/kubeletpods.go
首先检查 imagesfs, 数据从 cadvisor 中获取
获得容器信息和 kubelet 总计状态
summaryProvider 的实际函数在 /pkg/kubelet/server/stats/summary.go
开始监视当前的系统状态
监视这些数据 Node.Memory al…

kubernetes cloud controller manager

kubernetes cloud controller manager Table of Contents1. 什么是 cloud controller manager(ccm)2. 能用 ccm 干什么2.1. 现有的 ccm2.1.1. In Tree2.1.2. Out of Tree3. 如何实现一个 ccm4. 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() (Routes, bool) ProviderName() string HasClusterID() bool 这样就…