从 numpy 数组中有效地采样以相同数字终止的连续整数序列？

Question

假设我有以下 numpy 数组：

Space = np.arange(7)

问题： 我怎样才能从 Space 生成一组 N 个样本，使得：

每个样本仅由递增或递减的连续数字组成
采样是通过替换完成的，因此样本不需要单调增加或减少。
每个样本以 6 或 0 结尾，并且
样本的长度没有限制（但是，一旦选择了 6 或 0，每个样本就会终止）。

本质上我是通过 numpy 采样创建一个马尔可夫奖励过程（可能有一个更有效的数据包，但我不确定它会是什么。）例如，如果 N = 3，一个可能的采样集看起来像这样。

Sample = [[1,0],[4, 3, 4, 5, 6],[4, 3, 2, 1, 2, 1, 0]]

我可以用一些不太优雅的东西来完成这个：

N = len(Space)
Set = []
for i in range(3):
    X = np.random.randint(N)
    if (X == 0) | (X==6):
        Set.append(X)
    else:
        Sample = []
        while (X !=0) & (X != 6):
            Next = np.array([X-1, X+1])
            X = np.random.choice(Next)
            Sample.append(X)
        Set.append(Sample)
return(Set)

但我想知道还有什么 efficient/pythonic 方法可以进行这种类型的采样，也许没有那么多循环？或者如果有更好的 python 库来处理这类事情？谢谢

Answer 1

Numpy 在这里似乎没什么用，我只是使用标准的 random 模块。主要原因是 random 像该算法一样处理单个值时速度更快，除非需要，否则似乎不需要引入额外的依赖项。

from random import randint, choice

def bounded_path(lo, hi):
    # r covers the interior space
    r = range(lo+1, hi)
    n = randint(lo, hi)
    result = [n]
    while n in r:
        n += choice((-1, 1))
        result.append(n)
    return result

似乎对我来说是对的，例如评估以上 10 次，我得到：

[0]
[4, 3, 4, 3, 2, 1, 0]
[5, 6]
[2, 3, 4, 3, 4, 5, 4, 3, 4, 3, 2, 1, 0]
[1, 0]
[1, 0]
[4, 3, 4, 3, 4, 3, 2, 3, 2, 1, 0]
[3, 2, 3, 2, 1, 0]
[6]
[4, 5, 4, 3, 4, 3, 2, 1, 0]

刚刚做了随机数生成的快速基准比较：

def rng_np(X):
    for _ in range(10):
        X = np.random.choice(np.array([X-1,X+1]))
    return X

def rng_py(X):
    for _ in range(10):
        X += choice((-1, +1))
    return X

Numpy 版本慢了大约 30 倍。 Numpy 必须做很多额外的工作，每次迭代构建一个 Python 数组，转换为 Numpy 数组，切换到 choice 以允许花哨的矢量化。 Python 知道 vanilla 版本中的 (-1, +1) 是常量，所以它只构建一次（例如 dis 有助于查看内部情况）。

您可能可以通过使用更大的数字块来到达某个地方，但我怀疑它会更快。保持起点的一致性似乎很尴尬，但如果你真的很小心，你可能会做一些事情！ Numpy 在每次调用都经过大约 10 个值的矢量化时开始收支平衡，并且当您拥有超过 100 个值时真正闪耀。

从 numpy 数组中有效地采样以相同数字终止的连续整数序列？

efficiently sample sequences of consecutive integers that terminate in the same number from a numpy array?

python

random

numpy

markov-chains

sampling